Propositional Logic
===================

Logic deals with statements that are either true or false.
Proposition -- any statement that has one truth value, true or false.

They do not need to be true to reason about them. Some propositions:
   Starbucks sells coffee in Seattle.
   Metallica plays easy listening music.
   Brandi Carlile will win a grammy in 2025.
             (True or false, we just don't know which!)

Are these statements true or false? 
Questions and commands are not propositions:
   Do I own any dogs?
   Finish your programming assignment.

When dealing with logic abstractly, we won't pay much attention to what
the particular propositions mean.  We will give them abbreviated names
(lower-case letters) to represent them and reason about them using their
abbreviations.  So, "p" could represent the proposition "My car is white"
and "q" could represent the proposition "My car is a Ferrari".

Propositions which are logical expressions use logical operators such as
AND, OR (inclusive OR, one or both), NOT. Many different symbols
typically represent these operator.

Let p, q represent propositions, p and q are propositional variables.

Recursive definition of logical expressions:
Basis -- Propositional variables, logical constants (true, false)
	 are logical expressions.
Recursive -- If p and q are logical expressions, then so are
         p AND q, p OR q, NOT p.


We can use logical operators to create complex statements.
We can negate statements, i.e., change their truth value.
For example, NOT p is "My car is not white" .
If p is "Today is Tuesday" and q is "It is raining" then p OR q is
"Today is Tuesday or it is raining" .
p and q is "Today is Tuesday and it is raining" .

Operator precedence
high         C++
 |    NOT    !     negation
 |    AND    &&    conjunction
 |    OR     ||    disjunction
 |    -->          implication, means if ... then 
 |    <-->         equivalence, biconditional, means if and only if (iff) 
 v    
low

Other notation used:
             _
NOT p,  ~p,  p
p AND q,  p /\ q
p OR q,  p \/ q

For any particular operator, we can define it using a truth table that says
what the value is for any possible combination of inputs. If there are 2
variables, there are 4 possible values. If there are 3 variables, there are
8 possible values.

The following tables show results of basic logical operations.
A zero represents false, one represents true.

 p | q | p AND q | p OR q | NOT p
---+---+---------+--------+-------
 0 | 0 |    0    |   0    |  1
 0 | 1 |    0    |   1    |   
 1 | 0 |    0    |   1    |  0
 1 | 1 |    1    |   1    |   

 p | q | p --> q  which is same as  NOT p OR q    p | q | NOT p | NOT p OR q
---+---+---------                                ---+---+-------+------------
 0 | 0 |    1                                     0 | 0 |  1    |       1
 0 | 1 |    1                                     0 | 1 |  1    |       1
 1 | 0 |    0                                     1 | 0 |  0    |       0
 1 | 1 |    1                                     1 | 1 |  0    |       1

 p | q | p <--> q  which is same as p-->q AND q-->p
---+---+--------- 
 0 | 0 |    1    
 0 | 1 |    0   
 1 | 0 |    0  
 1 | 1 |    1 

 p | q | p (+) q   exclusive OR, XOR (actually plus in a little circle)
---+---+--------- 
 0 | 0 |    0    
 0 | 1 |    1   
 1 | 0 |    1  
 1 | 1 |    0 

Logical expressions are equivalent if they have the same truth values under all
conditions. You can prove expressions are equivalent using truth tables. 
In a truth table, the number of rows comes from all combinations of truth
values for each variable.

Show that p <--> q  is the same as p-->q AND q-->p .

 p | q | p --> q | q --> p | p --> q AND q --> p  
---+---+---------+---------+--------------------
 0 | 0 |    1    |   1     |          1    
 0 | 1 |    1    |   0     |          0   
 1 | 0 |    0    |   1     |          0  
 1 | 1 |    1    |   1     |          1 


Tautology:  logical expression whose value is true under all situations
E.g., true OR p

Contradiction:  logical expression whose value is false under all situations
E.g., false AND p

In most discrete math texts, there are many logical equivalences.
Some are clear such as the commutative laws, e.g., p OR q is the same as q OR p
Two useful laws are DeMorgan's laws. (For the rest, see Boolean algebra notes.)

DeMorgan's law: complement of the product is the sum of the complements
                complement of the sum is the product of the complements

NOT (p AND q) <--> NOT p OR NOT q
NOT (p OR q) <--> NOT p AND NOT q