What is the difference between RELATION “AND” and “OR” in TAX_QUERY?

tax_query is a 2-dimensional array, each sub-array can be considered to be a taxonomy query, typical its of the form:

array(
  'taxonomy' => 'people',
  'field' => 'slug',
  'terms' => 'bob'
)

(e.g. posts in with the term with slug ‘bob’, of the ‘people’ taxonomy).

The fact that tax_query is a two dimensional array means that you can have multiple taxonomy queries. In this case you may want to return posts which match all taxonomy queries (relation => 'AND' ) or posts which match at least one taxonomy query (relation => 'OR' ).

As the codex:
states

This construct allows you to query multiple taxonomies by using the relation parameter in the first (outer) array to describe the boolean relationship between the taxonomy queries.

For example:

$args = array(
    'post_type' => 'post',
    'tax_query' => array(
        'relation' => 'AND', //Must satisfy all taxonomy queries
        array(
            'taxonomy' => 'movie_genre',
            'field' => 'slug',
            'terms' => 'action'
        ),
        array(
            'taxonomy' => 'actor',
            'field' => 'id',
            'terms' => array( 103, 115, 206 ),
            'operator' => 'NOT IN'
        )
    )
);
$query = new WP_Query( $args );

returns all posts with move_genre term with slug ‘action’ AND does not have the actor terms with IDs 103,115,206.

On the other hand (notice relation change):

$args = array(
    'post_type' => 'post',
    'tax_query' => array(
        'relation' => 'OR',//Must satisfy at least one taxonomy query
        array(
            'taxonomy' => 'movie_genre',
            'field' => 'slug',
            'terms' => 'action'
        ),
        array(
            'taxonomy' => 'actor',
            'field' => 'id',
            'terms' => array( 103, 115, 206 ),
            'operator' => 'NOT IN'
        )
    )
);
$query = new WP_Query( $args );

returns all posts with either have move_genre term with slug ‘action’ OR do not have the actor terms with IDs 103,115,206 (or satisfy both).