Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #43707 > unrolled thread

Understanding Boolean Expressions

Back to article view | Back to comp.lang.python

Contents

  Understanding Boolean Expressions Bruce McGoveran <bruce.mcgoveran@gmail.com> - 2013-04-16 15:19 -0700
    Re: Understanding Boolean Expressions Walter Hurry <walterhurry@lavabit.com> - 2013-04-16 22:32 +0000
    Re: Understanding Boolean Expressions Dave Angel <davea@davea.name> - 2013-04-16 18:57 -0400
    Re: Understanding Boolean Expressions "Rhodri James" <rhodri@wildebst.demon.co.uk> - 2013-04-17 00:28 +0100
    Re: Understanding Boolean Expressions Terry Jan Reedy <tjreedy@udel.edu> - 2013-04-16 21:23 -0400
    Re: Understanding Boolean Expressions Bruce McGoveran <bruce.mcgoveran@gmail.com> - 2013-04-16 19:29 -0700
    Re: Understanding Boolean Expressions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-17 08:14 +0000
      Re: Understanding Boolean Expressions Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-04-17 11:47 +0300
        Re: Understanding Boolean Expressions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-17 09:20 +0000
          Re: Understanding Boolean Expressions Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-04-17 12:32 +0300

#43707 — Understanding Boolean Expressions

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.  Moreover, if I follow the chain of non-terminal references, I move from or_test, to and_test, to not_test, to comparison.  And when I look at the definition for comparison, I seem to be into bitwise comparisons.  I cannot explain this.

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).  

If people can offer some thoughts to put me in the right direction (or out of my misery), I would appreciate it.

Thank you in advance.

[toc] | [next] | [standalone]

#43709

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.  Moreover, if I follow the chain of non-terminal references, I
> move from or_test, to and_test, to not_test, to comparison.  And when I
> look at the definition for comparison, I seem to be into bitwise
> comparisons.  I cannot explain this.
> 
> 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).
> 
> If people can offer some thoughts to put me in the right direction (or
> out of my misery), I would appreciate it.

$ python
Python 2.7.3 (default, Jan 15 2013, 02:26:36) 
[GCC 4.2.1 20070831 patched [FreeBSD]] on freebsd9
Type "help", "copyright", "credits" or "license" for more information.
>>> not True
False
>>> not False
True
>>> True or False
True
>>> True and False
False
>>> x = 2
>>> not (x == 2)
False
>>> not (x == 3)
True
>>> x == 2
True
>>> x == 3
False
>>>

[toc] | [prev] | [next] | [standalone]

#43711

On 04/16/2013 06:19 PM, 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.  Moreover, if I follow the chain of non-terminal references, I move from or_test, to and_test, to not_test, to comparison.  And when I look at the definition for comparison, I seem to be into bitwise comparisons.  I cannot explain this.
>
> 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).
>
> If people can offer some thoughts to put me in the right direction (or out of my misery), I would appreciate it.
>

It's been decades since I really had to understand a complete grammar. 
But in some ways, a fragment like you're referencing is even harder. The 
trick is to take those names "and_test" as rather arbitrary.  There's no 
token meaning "an expression containing 4 or's, 2 and's, and 1 not"  So 
sometimes the terms used are rather silly looking.

The point is you can combine 'not', 'and', 'or', and comparison 
operators like ==, >=  etc.  in some complex ways.  The grammar just 
says which of these is legal, and doesn't help you figure out the 
semantics, which is usually much more important to you and me.

First, nearly all objects have a 'truth' value, for which I use the 
terms 'true' and 'false'.  For numbers, nonzero values are true, and 
zero values are false.  For collections, nonempty collections are true 
and empty ones are false.  And so on.  So if x is an int, and if you say:
     if x:

You're checking the 'truth' of x, and it'll execute the if clause for 
nonzero integers, for example.

If you have an arbitrary object 'x', it is not necessarily of type bool. 
  But if you compare it to another one,  x==y   the result is a bool, 
either True or False.  Likewise if you apply the unary 'not' to an 
object;  the result will be either True or False.

But if you combine two expressions with 'or' the result is NOT 
necessarily of type bool.  If the first expression is true, then the 
second expression isn't even examined.  If the first expression is 
false, the second expression is the result.

'and' has the reverse meaning.  And more complex expressions can be 
understood by breaking them into steps, according to operator precedence 
and parentheses.

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#43714

On Tue, 16 Apr 2013 23:19:25 +0100, Bruce McGoveran
<bruce.mcgoveran@gmail.com> 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.  Moreover, if I follow the chain of non-terminal references, I  
> move from or_test, to and_test, to not_test, to comparison.  And when I  
> look at the definition for comparison, I seem to be into bitwise  
> comparisons.  I cannot explain this.
>
> 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).
>
> If people can offer some thoughts to put me in the right direction (or  
> out of my misery), I would appreciate it.

What the grammar rules are giving you is operator precedence -- "not" has  
higher precedence than "and", which is higher than "or".  As you follow  
the non-terminals back you go further through precedence chain:  
comparisons, then bitwise operators (*not* bitwise comparisons!), then  
shifts, then arithmetic operators, the unary operators, the power  
operator, and finally primaries.

-- 
Rhodri James *-* Wildebeest Herder to the Masses

[toc] | [prev] | [next] | [standalone]

#43722

[2nd try, quotation a bit messed up]

On 4/16/2013 6:19 PM, 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,


The substance is that 1) 'not' binds tighter than 'and' binds tigher 
than 'or' and 2) 'and' and 'or' both associate left to right in the 
normal manner so that 'a op b op c' == '(a op b) op c'.

 > it is the grammar definitions themselves that confuse me.

The techinical details reflect the fact that Python's grammar is ll(1) 
(top-down, parsed by recursive descent) rather than lr(1) (bottom-up). 
The latter (in lalr(1) form) is what yacc, etc use and might be more 
familiar to you.

 > For example, I am not clear how an or_test can be an and_test.

or_test  ::=  and_test | or_test "or" and_test

The second option expresses the associativity rule, but more is needed 
to get out of infinite regress. Substituting the second rule into second 
rule gives

or_test = (or_test 'or' and_test) 'or' and_test

and so on. At some point, one must replace or_test with and_test to get 
an 'or' of ands. Similarly, an and_test must resolve to an 'and' of nots.

 > Moreover, if I follow the chain of non-terminal references, I move
 > from or_test, to and_test, to nt_test, to comparison.  And when I
 > look at the definition for comparison, I seem to be into bitwise
 > comparisons.  I cannot explain this.

Eventually the chain takes one to primaries, which include things like 
literals and identifiers.

 > 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.

Yes.

 > 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).

The second. Then the or_test on the left also maps to an and_test. Each 
and_test eventually resolves to 'identifier', specifically 'x' and 'y'.

     --
     Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#43724

Thank you all for thoughts.  I'm just about to post another question about atoms and primaries.  If you have a moment to look it over, I would appreciate your thoughts.

Many thanks in advance.

On Tuesday, April 16, 2013 6:19:25 PM UTC-4, 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.  Moreover, if I follow the chain of non-terminal references, I move from or_test, to and_test, to not_test, to comparison.  And when I look at the definition for comparison, I seem to be into bitwise comparisons.  I cannot explain this.
> 
> 
> 
> 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).  
> 
> 
> 
> If people can offer some thoughts to put me in the right direction (or out of my misery), I would appreciate it.
> 
> 
> 
> Thank you in advance.

[toc] | [prev] | [next] | [standalone]

#43742

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

[toc] | [prev] | [next] | [standalone]

#43743

Steven D'Aprano writes:

> 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

I think you mean to say that "x and y" counts as an and_test and also
as an or_test.

[toc] | [prev] | [next] | [standalone]

#43748

On Wed, 17 Apr 2013 11:47:49 +0300, Jussi Piitulainen wrote:

> Steven D'Aprano writes:
> 
>> 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
> 
> I think you mean to say that "x and y" counts as an and_test and also as
> an or_test.

You may very well be right, but I'll be damned if I go back and read 
through my post trying to work out what I intended to say instead of what 
I actually said! 


:-)


And-or-or-and-or-or-or-and-and-or-ly y'rs,



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#43750

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:

> On Wed, 17 Apr 2013 11:47:49 +0300, Jussi Piitulainen wrote:
> 
> > Steven D'Aprano writes:
> > 
> >> 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
> > 
> > I think you mean to say that "x and y" counts as an and_test and also as
> > an or_test.
> 
> You may very well be right, but I'll be damned if I go back and read 
> through my post trying to work out what I intended to say instead of what 
> I actually said! 
> 
> :-)

The quote above is sufficient context for one who knows that "x or y"
is not an and_test. I'm hoping that pointing this little thing out
will help some potentially confused reader of your otherwise excellent
explanation see more quickly that this is really just a harmless typo.
(Unless it's me who's confused :)

The quote appeared just before your ASCII art.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web