Transcript What is Boolean Algebra?

The Laws of Logic:
Boolean Algebra
A State High Math Club Presentation
START==TRUE
What is Boolean Algebra?
• Two values
– True and False - Logic + Set Theory
– 1 and 0 - Computers + Probability
– High and Low – Digital Electronics
AND - Basic
•
•
•
•
Notation - AND ^ &&
(A AND B) returns true iff A and B are both true
Numerically: A * B
Identity - 1
– 0 AND 1 = 0
– 1 AND 1 = 1
• Annihilator - 0
– 0 AND 0 = 0
– 1 AND 0 = 0
AND - Representations
OR (Inclusive or) - Basic
• Notation - OR v ||
• (A OR B) returns true if either (or both) of A
and B are true
• Numerically: A + B - A * B
– Probability: P(A or B) = P(A)+P(B)-P(A AND
B)
• “And/Or” Construction
• Identity - 0
• Annihilator - 1
OR - Representations
NOT - Basic
• Notation NOT ¬ ~ !
• Unary - only takes one argument
– Others are called binary
• Returns the opposite of its argument
• Analogous to negative sign
NOT - Representations
XOR (Exclusive or) - Derived
• Notation XOR ^ +
• (A XOR B) returns true iff exactly one of A and B
is true
– Can also be considered “not equals”
– “Either/or” construction
– A XOR B = (A ^ ~B) v (~A ^ B)
• Numerically: A+B (mod 2)
– Also A+B – 2*(A*B) – Same formula in probability
• A XOR 1 = NOT(A)
• A XOR 0 = A
XOR - Representations
Equivalence - Derived
• Notation ≡ ==
• Returns true iff A=B
Material Implication - Derived
• Notation x–>y
• Linguistically “If X, then Y”
– X is called the antecedent; y is called the consequent
• False ONLY when x is true and y is false
• NOT(X) OR Y
– More intuitively NOT(X AND NOT(Y))
• Why is x->y true when x is false???
– This means that “If two is odd, then two is even” is a
true statement!
Tautologies:
The Theorems of Boolean Algebra
• Called laws
• Proven with either
truth tables or
derivations
– Truth table – true iff
last column is all 1s
(i.e. true for all input
values)
• Example: Proof of
X ^ ~X == 0
X ~X X^~X X^~X== 0
1
0
0
1
0
1
0
1
De Morgan’s Laws:
Distributing a NOT
• ¬(xVy)=(¬x)^(¬y)
• ¬(x^y)=(¬x)V(¬y)
• Proofs?
X
1
1
0
0
Y
1
0
1
0
(¬x)v(¬y) ¬(x^y)
0
0
1
1
1
1
1
1
X Y (¬x)^(¬y) ¬(xvy)
1 1
0
0
1 0
0
0
0 1
0
0
0 0
1
1
Important Laws
• AND and OR are:
– Distributive over each other
– Associative
– Commutative
•
•
•
•
~~X = X
X^~X==0
Xv~X==1
De Morgan’s Laws
A Derivation
• (w V x) V (y V z)
= ((w V x) V y) V z
= (w V (x V y)) V z
= (w V (y V x)) V z
= ((w V y) V x) V z
= (w V y) V (x V z)
• Why is this valid?
Applications:
Logic + Deduction
• Propositional Calculus – gives valid forms of
arguments
– Arguments are valid iff they are laws of boolean
algebra
– Tends to use “->” a lot
• Examples
– (P ^ (P->Q)) -> Q – Modus Ponens
– (~Q ^ (P->Q)) -> ~P – Modus Tollens
– ((P->Q) ^ (Q->R)) -> (P->R) –
Hypothetical Syllogism
Modus Ponens Proof
P Q P->Q (P ^ (P->Q))
1 1
1
1
(P ^ (P->Q)) -> Q
1
1 0
0
0
1
0 1
1
0
1
0 0
1
0
1
Modus Tollens Proof
P Q P->Q (~Q ^ (P->Q)) (~Q ^ (P->Q)) -> ~P
1 1
1
0
1
1 0
0
0
1
0 1
1
0
1
0 0
1
1
1
Hypothetical Syllogism Proof
P
1
1
1
1
0
0
0
0
Q
1
1
0
0
1
1
0
0
R
1
0
1
0
1
0
1
0
P->Q
1
1
0
0
1
1
1
1
Q->R P->Q ^ Q->R P->R
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
Applications:
Computer Curcuits
• Everything in a computer is either a 1 or 0
(called a bit, or binary unit)
– 1 is high voltage; 0 is low voltage
– Why?
• Calculations are done with AND, OR, and NOT
logic gates
– Sound familiar?
How Do Computers Add?
• We want to add two numbers, which are
sequences of bits
– We add one place value (two bits) at a time
• Input: The two bits, A and B
• Output: sum bit (the actual place value)
and carry bit (if we need to carry a 2)
• How can we make this circuit?
Adding
• Make a truth table and translate it into a circuit
diagram
A
B
Sum
Carry
1
1
0
1
1
0
1
0
0
1
1
0
0
0
0
0
Adding
• Sum = A XOR B
• Carry = A AND B
What about the carry bit?
• We forgot we might need to add a carry bit
as well
• So we really have three inputs: A,B, and
Cin (carry in)
• Still two outputs:
– Cout (carry out)
– Sum
Take Two
•How do we make this
circuit diagram?
A
1
1
1
1
0
0
0
0
B
1
1
0
0
1
1
0
0
Cin
1
0
1
0
1
0
1
0
S
1
0
0
1
0
1
1
0
Cout
1
1
1
0
1
0
0
0
Full 1-bit Adder
How about more bits?
How many basic gates?
• We use AND, OR, and NOT as basic
gates
– Wouldn’t it be nice to have ONE basic gate?
– Can mass-produce a single circuit; don’t have
to worry about which (tiny and impossible to
see) circuit is which
NAND – Sheffer Stroke
• Notation NAND | ↑
• A NAND B = NOT (A
AND B)
• Can be used to make
AND, OR, and NOT
gates
– How?
NAND as a Universal Gate
• NOT(A) = A NAND A
• A AND B = NOT(A NAND B) = (A NAND
B) NAND (A NAND B)
• A OR B = NOT(A) NAND NOT(B) by
Demorgan’s Law = (A NAND A) NAND (B
NAND B)
• A -> B = NOT(A) OR B = A NAND NOT(B)
= A NAND (B NAND B)
NOR – Pierce Arrow
• Notation NOR ↓
• A NOR B = NOT(A OR B)
• Can be used to make AND,OR, and NOT
gates
– How?
NOR as a Universal Gate
• NOT(A) = A NOR A
• A OR B = NOT(A OR B) = (A NOR B) NOR (A
NOR B)
• A AND B = NOT(A) NOR NOT(B) by
Demorgan’s Law = (A NOR A) NOR (B NOR B)
• A->B = NOT(A) OR B = (NOT(A) NOR B) NOR
(NOT(A) NOR B) =
((A NOR A) NOR B) NOR ((A NOR A) NOR B)
An Everyday Example:
Search Engines
• Google uses boolean algebra on your search
terms
– Automatically uses AND (i.e. whitespace = AND)
• boolean algebra -> Pages with BOTH ‘boolean’ and ‘algebra’
in them
– Use OR for logical OR
• Boolean OR algebra -> Pages with EITHER ‘boolean’ or
‘algebra’ in them
– Use - for NOT
• Boolean –Algebra ->Pages WITH ‘boolean’ but WITHOUT
‘algebra’
END==1