[techtalk] Boolean logic (was: This talk of N-ary trees and other things...)

[jenn at simegen.com]

Nancy Corbett wrote:


> One time someone told me to study Logic...but not just any logic, some
> specific type of logic.  I can no longer remember what it's called.  Maybe
> you know. I can see how it would help me to cover all my bases when
> writing programs.  It involves mapping out truth tables for problems like:

Boolean logic. You *CANNOT* write anything that involves an 'if' or a
'while' or any other logic evaluation test without it.


Here's the basic operators for boolean logic:


AND

(Is the following statement true? : It is raining AND the roof is wet)

Raining   Roof    Statement-as-a-whole
   T        T           T
   T        F           F
   F        T           F
   F        F           F


OR

It is raining OR the roof is wet

Raining   Roof    Statement-as-a-whole
   T        T           T
   T        F           T
   F        T           T
   F        F           F


IF-THEN (also called implies, not often used in programming)

IF it is raining THEN the roof is wet

Raining   Roof    Statement-as-a-whole
    T        T        T
    T        F        F
    F        T        T    (or at least, you can't prove it to be false)
    F        F        T    (ditto)


XOR (exclusive or - one or the other but not both)

It is raining XOR the roof is wet


Raining   Roof    Statement-as-a-whole
    T        T        F
    T        F        T
    F        T        T
    F        F        F


NOT

It is NOT raining

Raining      Statement-as-a-whole
    T               F
    F               T



To solve a problem, you reduce each factoid to a true/false statement,
such as 'Mr Smith is a knight'.

So...

IF Smith-knight THEN Smith-tells-truth.

IF Smith-tells-truth THEN Mrs-Smith-tells-lies

IF Mrs-Smith-tells-lies THEN Mr-Smith-is-not-a-knight

..... and so on. Until you hit false statements, or
self-contradictions like that one.

This particular puzzle can also be solved by either propositional or
predicate calculus, which are also on my recommended learn-list. :)



Jenn V.
-- 
     "Do you ever wonder if there's a whole section of geek culture
             you miss out on by being a geek?" - Dancer.

jenn at simegen.com     Jenn Vesperman     http://www.simegen.com/~jenn/