From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fac41,9a0ff0bffdf63657 X-Google-Attributes: gidfac41,public X-Google-Thread: f43e6,9a0ff0bffdf63657 X-Google-Attributes: gidf43e6,public X-Google-Thread: 1108a1,9a0ff0bffdf63657 X-Google-Attributes: gid1108a1,public X-Google-Thread: 103376,4b06f8f15f01a568 X-Google-Attributes: gid103376,public From: doylep@ecf.toronto.edu (Patrick Doyle) Subject: Re: Software landmines (loops) Date: 1998/09/04 Message-ID: #1/1 X-Deja-AN: 387858090 X-Nntp-Posting-Host: spark23.ecf Sender: news@ecf.toronto.edu (News Administrator) References: <35EDC648.76F03F32@draper.com> <35EEF597.A1119EF4@draper.com> Organization: University of Toronto, Engineering Computing Facility Newsgroups: comp.lang.eiffel,comp.object,comp.software-eng,comp.lang.ada Date: 1998-09-04T00:00:00+00:00 List-Id: In article <35EEF597.A1119EF4@draper.com>, Tim McDermott wrote: > >Patrick Doyle wrote: > >> If you want to talk about how many possible boolean expressions there >> are with n terms, that's 2^(2^n). There are 2^n assignments for the >> variables, and any combination of those assignments could make >> the expression true. > >There are 4 possible 1-term boolean expressions? Could you list them?Perhaps >this is a terminology problem. By 3-term, I don't mean 3 variables used as often >as you like, I mean 3 occurances of any variable and 2 operators (again >neglecting negation). >I am counting "A & (!A)" as a 2-term expression. Ok, I understand now. As for the 4 possible 1-term boolean expressions, you have A, !A, True (which could be written A + !A) and False (which could be written A * !A). If you want to get rid of the trivial True and False ones, the number is still O(2^(2^n)) (actually being 2^(2^n) - 2). >> A + B + C >> A & B + C >> A &(B + C) >> A + B & C >> (A + B)& C >> A & B & C >> >> However, these aren't really 6 distinct expressions. The third >> and fifth are the same, as are the second and fourth. > >Hmmm. With A and B false and C true, the second expresion is true, while the >fourth is false. The third and fifth expressions differ when A is false and B >and C are true. (assuming '&' has higher precedence than '+') Oh, I was neglecting the variable names. The second expression can be rewritten as C + B & A which, neglecting the letters, is the same as A + B & C. If you don't neglect the letters, then these are not the only possible expressions. There would also be: A & C + B (A + C)& B It's easier to enumerate them if you consider the possibilities with prefix notation. There will be two operators followed by three variables, like this: &+BCA If the operators are the same, the order of the variables doesn't matter. So, there are two of those; one for & and one for +. If the ops are different, then the order of the first two variables doesn't matter, but the third does. That gives 2 operator combinations and 3 distinct variable combinations, for a total of 6 possibilities. Altogether, then, there are eight such expressions. As for what you said about this being hard, I'd agree that counting theory is hard; but I don't see the relevance of that to understanding a loop. -PD -- -- Patrick Doyle doylep@ecf.toronto.edu