15-110 Spring 2011
Class Notes:  Boolean Logic

• Basics
• Primitives:  true (1) or false (0)
• Variables:  can be either true or false
• Operators:  and, or, not  (all other operators can be expressed as combinations of these)
• Expressions:  Composed of primitives, variables, and operators
• Truth Tables:  Tables listing all possible variable values and their corresponding expression values.
• Satisfiability:  An expression is satisfiable if it is true for at least one combination of variable values.
• Tautology:  An expression is a tautology if it is true for every possible combination of variable values.
• Equivalence:  Two expressions are equivalent if they have the same truth value for every possible combination of variable values.
  
  
• and
• A and B:  both A and B are true
  

  A B A and B false false false false true false true false false true true true

  A B A and B 0 0 0 0 1 0 1 0 0 1 1 1



• or
• A or B:  either and/or both A and B are true
  

  A B A or B false false false false true true true false true true true true

  A B A or B 0 0 0 0 1 1 1 0 1 1 1 1

  
  
• not
• not A:  A is false
  

  A not A false true true false

  A not A 0 1 1 0

  
  
• Another example, with 2 variables:
  

  A B not A false false true false true true true false false true true false

  A B not A 0 0 1 0 1 1 1 0 0 1 1 0

  
  
• More Boolean Operators
• All boolean operators can be expressed as combinations of and/or/not
  

  Operator	Meaning	Rewritten using and/or/not
  A xor B	Exactly one of A or B is true	(A and not B) or (B and not A)
  A -> B	A implies B	not A or B
  A = B	A is equivalent to B	(A and B) or (not A and not B)

• Complex Boolean Expressions and Helper Columns
• Use "helper columns" to construct complex boolean expressions in small steps
• Example:   (A and B) or (not A and not B)
  

  A	B	A and B	not A and not B	(A and B) or (not A and not B)
  0	0	0	1	1
  0	1	0	0	0
  1	0	0	0	0
  1	1	1	0	1

  
  
• Labeled helper columns may help with large expressions
• Example (same as above):
  

  A	B	C1: A and B	C2: not A and not B	C3: C1 or C2
  0	0	0	1	1
  0	1	0	0	0
  1	0	0	0	0
  1	1	1	0	1



• Truth Tables with 3 Variables
• List rows in "binary counting order"  (000, 001, 010, 011, 100, 101, 110, 111)
• Example:  Write the truth table for the expression (A and (B or not C))
  

  A	B	C	B or not C	A and (B or not C)
  0	0	0	1	0
  0	0	1	0	0
  0	1	0	1	0
  0	1	1	1	0
  1	0	0	1	1
  1	0	1	0	0
  1	1	0	1	1
  1	1	1	1	1

  
  
• Tautology with Truth Tables
• Tautology:  An expression is a tautology if it is true for every possible combination of variable values.
• Example:  Prove one of DeMorgan's Laws:   not (A or B) = (not A) and (not B)
  

  A	B	A or B	C1: not (A or B)	not A	not B	C2: not A and not B	C1 = C2
  0	0	0	1	1	1	1	1
  0	1	1	0	1	0	0	1
  1	0	1	0	0	1	0	1
  1	1	1	0	0	0	0	1



• Note:  The other DeMorgan's Law is:  not (A and B) = (not A) or (not B)
  (Can you prove it?)
  


• Satisfiability with Truth Tables
• Satisfiability:  An expression is satisfiable if it is true for at least one combination of variable values.
• Example:   Find a truth assignment that satisfies this expression:  (A and (B or not C)) and (not C and (not A or B))

  A	B	C	B or not C	C1: A and (B or not C)	(not A or B)	C2: not C and (not A or B)	C1 and C2
  0	0	0	1	0	1	1	0
  0	0	1	0	0	1	0	0
  0	1	0	1	0	1	1	0
  0	1	1	1	0	1	0	0
  1	0	0	1	1	0	0	0
  1	0	1	0	0	0	0	0
  1	1	0	1	1	1	1	1
  1	1	1	1	1	1	0	0

• Answer:
       A is true
       B is true
       C is false