Understanding Boolean Expressions

[Steven D'Aprano]

On Tue, 16 Apr 2013 15:19:25 -0700, Bruce McGoveran wrote:

> Hello.  I am new to this group.  I've done a search for the topic about
> which I'm posting, and while I have found some threads that are
> relevant, I haven't found anything exactly on point that I can
> understand.  So, I'm taking the liberty of asking about something that
> may be obvious to many readers of this group.
> 
> The relevant Python documentation reference is: 
> http://docs.python.org/2/reference/expressions.html#boolean-operations.
> 
> I'm trying to make sense of the rules of or_test, and_test, and not_test
> that appear in this section.  While I understand the substance of the
> text in this section, it is the grammar definitions themselves that
> confuse me.  For example, I am not clear how an or_test can be an
> and_test.

In this case, you could have saved us some time by copying and pasting 
the relevant three lines:

or_test  ::=  and_test | or_test "or" and_test
and_test ::=  not_test | and_test "and" not_test
not_test ::=  comparison | "not" not_test


I agree that this is not entirely the most obvious wording, but it makes 
a sort of sense if you follow it through carefully. Unfortunately, to 
really understand the grammar, you have to follow through the entire 
thing. But translated into English, the above three rules might read like 
this:

An expression which we call an or_test can be either:

1) an and_test; or

2) another or_test, followed by the literal string "or", followed by an 
and_test.

An expression which we call an and_test can be either:

3) a not_test; or

4) another and_test, followed by the literal string "and", followed by 
another not_test.

An expression which we call a not_test can be either:

5) a comparison; or

6) the literal string "not", followed by another not_test.

An expression which we call a comparison can be:

... a bunch more different alternatives, going through bitwise 
comparisons, then arithmetic operators, then other expressions, and so 
on, until finally you reach the simplest expressions possible, names and 
constant literals.

So in a sense, an "or_test" does not JUST mean it's a test with an "or" 
in it. The thing called an or_test is an and_test *or* a test with an 
"or" in it; an and_test is a not_test *or* a test with an "and" in it; a 
not_test is a comparison *or* a test with a "not" in it; a comparison 
is ... and so forth, until you run out of expressions and end up with a 
simple atom like a name or a constant.

So paradoxically, that means that "x or y" counts as an and_test 
(obviously!) but also as an or_test, since every and_test also counts as 
an or_test. Here's some crappy ASCII art of a Venn diagram with a couple 
of examples shown: (best viewed in a fixed-width font):


+---------------------------------+
|  or_tests                       |
|                  "x or y"       |
|    +----------------------+     |
|    |  and_tests           |     |
|    |            "x and y" |     |
|    |    +-------------+   |     |
|    |    |  not_tests  |   |     |
|    |    |             |   |     |
|    |    |     "not x" |   |     |
|    |    +-------------+   |     |
|    +----------------------+     |
+---------------------------------+


Inside the "not_test" box, not shown, are other boxes relating to other 
expressions, and ending deep down with boxes labelled "names" and 
"literals". (Or so I expect, since I haven't followed the maze of twisty 
grammar rules, all alike, to the very end.)


Of course, in practice we wouldn't normally call an expression such as 
"x and y" as an or_test, even though strictly speaking the grammar says 
it is. We would call it by the smallest box it is contained within, 
namely "and_test".

An analogy: normally, we would refer to Python's creator Guido van Rossum 
as a "man", not a "mammal", but since all men are mammals, it wouldn't be 
wrong to call him such. But not all mammals are men, and not all or_tests 
are and_tests. "x or y" is an or_test, obviously, but not an and_test.

Does this help explain it?


> Perhaps an example will help put my confusion into more concrete terms. 
> Suppose I write the expression if x or y in my code.  I presume this is
> an example of an or_test.  Beyond that, though, I'm not sure whether
> this maps to an and_test (the first option on the right-hand side of the
> rule) or to the or_test "or" and_test option (the second on the
> right-hand side of the rule).

"x or y" maps to the second option. The "x" matches and_test, which then 
matches not_test, which then matches comparison, which ... blah blah 
blah ... which finally matches a plain name. The "or" matches the literal 
string "or" in the grammar rule. Then the "y" matches and_test, which ... 
finally matches a plain name.

Of course, this is NOT necessarily what Python does every time it parses 
a piece of code! It's just a description of the grammar.



-- 
Steven