Transcript propositional logic

PROPOSITIONAL LOGIC
Most of the definitions of formal logic have been developed so that they agree
with the natural or intuitive logic. But the need to put it scientifically is to
avoid ambiguity.
Sentences considered in propositional logic are not arbitrary sentences but
are the ones that are either true or false, but not both. This kind of sentences
are called propositions. By reading a sentence and basing your conclusion
directly from the facts mentioned in the sentence only, you can conclude the
truth or falsity of the statement.
Examples:
•If x is a real number such that x < -2 or x > -2, then x 2 > 4. Therefore, if
x  4 , then x  2 and x  2
•Grass is green
•2 + 5 = 5
•x + 3 = 3
•x +3 > 5
kavita hatwal fall 2002 Math 231
• A statement is a sentence that is either true or false, but not both.
• Statements:
– It is raining.
– I am carrying an umbrella.
•
Non-statements:
– a. (Question): Why are you late?
– b. (Command): Open the door.
– c. (Wish): If only I had studied a little
harder…
– d. (Something Vague): x + y = 4.
kavita hatwal fall 2002 Math 231
Elements of Propositional Logic
Simple sentences.
A simple statement is one that does not contain any other statement as a part.
We will use the lower-case letters, p, q, r, ..., as symbols for simple statements.
If p or q, then r
Therefore, if not r, then not p and not q.
Page 2, example 1.1..1
If Jane is a math major or Jane is a computer science major, then
Jane will take Math 150.
Jane is a computer science major.
Therefore, Jane will take Math 150.
Page 15, #1, 2, 4
kavita hatwal fall 2002 Math 231
COMPOUND STATEMENTS:
A compound statement is one with two or more simple statements as parts
or what we will call components. A component of a compound is any whole
statement that is part of a larger statement; components may themselves be
compounds.
Simple sentences which are true or false are basic propositions. Larger and
more complex sentences are constructed from basic propositions by
combining them with connectives. Thus propositions and connectives are
the basic elements of propositional logic. Though there are many
connectives, we are going to use the following five basic connectives here:
NOT
AND
OR
IF_THEN
IF and ONLY IF
 or ~




kavita hatwal fall 2002 Math 231
Logical Operators
• Binary operators
– Conjunction – “and”.
– Disjunction – “or”.
• Unary operator
– Negation – “not”.
• Other operators
– XOR – “exclusive or”
– NAND – “not both”
– NOR – “neither”
kavita hatwal fall 2002 Math 231
p  q is read as p and q and is called the conjunction of p and q
p  q is read as p or q and is called the disjunction of p and q.
In compound statements each simple statement can be seen as individual terms just
like in algebra. Just like in algebra, where when there are more than one operators
involved, there is an order of operation, there is an order of operation in compound

statements which include ~ and
and 
that
Order of operation  or ~ has the higher precedence than  and 
But can be overridden with the use of parenthesis.
So the order of operation in propositional logic can be summed as
The last one can lead to ambiguity.
()
~ or

 and 
kavita hatwal fall 2002 Math 231
Examples
Translating from english to Symbols
• Basic statements
– p = “It is raining.”
– q = “I am carrying an umbrella.”
• Compound statements
– p  q = “It is raining and I am carrying an umbrella.”
– p  q = “ It is raining or I am carrying an umbrella.”
– p = “It is not raining.”
kavita hatwal fall 2002 Math 231
Translating from english to Symbols:
Let p = “It is hot”
q = “It is sunny”
Queen’s english
Logic translation
but
but is opposite of and
but and and mean the
same thing
neither nor
Not this or that one,
none
not this and not that
one.
So it is not hot but sunny is written as
Queen’s english
Logic translation
~ pq
but
it is not hot but It is sunny
not p and q->
neither
nor
It is neither hot nor sunny
It is not hot and it is not sunny
~ p ~ q
kavita hatwal fall 2002 Math 231
Inequalities and
 
notation
x  a x < a or x = a
a xb
a  x and x  b
p = “0 < x”
q = “x < 3”
r = “x = 3”
Write the following inequalities symbolically
x 3
0 x 3
0 x 3
kavita hatwal fall 2002 Math 231
RECAP
simple statements
compound statements
TRUTH VALUES
Each simple statement comprising a compound statement is a statement in its
own right, that is it has a truth value, that is it can be true or false but not both.
The truth values of each individual statements affect the truth value of the
compound statement of which they are part of.
NEGATION
If p is a statement variable, the negation of p is “not p” or “It is not
the case that p” and is denoted as ~p. It has opposite truth values as p.
Wherever p is true, ~p is false and vice versa. The truth values for negation
summarized in a truth table are
p
T
F
~p
F
T
kavita hatwal fall 2002 Math 231
If p and q are statement variables, the conjunction of p and q is “p and q”
denoted p  q. It is true when, and only when, both p and q are true. If either
p or q is false, or if both are false, p  q is false. The truth values for and
summarized in a truth table are
p
T
T
F
F
q
T
F
T
F
p q
T
F
F
F
kavita hatwal fall 2002 Math 231
If p and q are statement variables, the disjunction of p and q is “p or q” denoted
p  q. It is true when at least one of p or q is true and is false only when both p
and q are false. The truth values for p or q summarized in a truth table are
p
T
T
F
F
q
T
F
T
F
p q
T
T
T
F
kavita hatwal fall 2002 Math 231
A statement form or (propositional form) is an expression made up of statement
variables (such as p, q and r) and logical connectives (such as ~ and
and
) that becomes a statement when actual statements are substituted for the
component statement variable. The truth table for a given statement form displays
the truth values that correspond to the different combinations of truth values for the
variables.
The general rule for constructing truth tables is:
1. List all the variables mentioned in the statement in separate columns and
then list all the combinations of truth values for them.
2. Add columns for operations mentioned in the statement with all the
combinations of truth values for them starting from inside out the
parenthesis if there exist any.
3. Evaluate the final result
XOR
Construct truth table for
•
~(p  q) work from inside out.
• p  (p  q)
kavita hatwal fall 2002 Math 231
LOGICAL EQUIVALENCE:
•Two statements are said to be logically equivalent if and only if, they’ve identical
truth values for each possible substitution of statements for their statement
variables.
•Two statements are said to be logically equivalent if and only if, when the same
statement variables are used to represent identical component statements, their
forms are logically equivalent.
It is denoted as
PQ
•Construct the truth table for P
•Construct the truth table for Q using the same statement variables for identical
component statements.
•Check each combination of truth values of the statement variables to see
whether the truth value of P is the same as the truth value of Q.
a. If in each row the truth value of P is the same as the truth value of Q,
then P and Q are logically equivalent.
b. If in some row the truth value of P is different from the truth value of
Q, then P and Q are not logically equivalent.
page 9, example 1.1.6, 1.17
kavita hatwal fall 2002 Math 231
• (p  q)  (p  q)  (p  q)  (p  q)
p
q
(p  q)  (p  q)
(p  q)  (p  q)
T
T
T
T
T
F
F
F
F
T
F
F
F
F
T
T
kavita hatwal fall 2002 Math 231
De Morgan’s law
•~(p  q)  ~p ~q the negation of and is logically equivalent to the or of the
negated components
•~(p  q)  ~p  ~q the negation of oris logically equivalent to the and of the
negated components
Page 11 examples and cautionary example
kavita hatwal fall 2002 Math 231
Tautology and Contradiction
A tautology is a logical expression that is true regardless of the values of its
variables. Thus, for a tautology, the value of the expression is TRUE in every row
of the truth table. The column of a tautology in a truth table contains only T's.
P  ~P
p  q  ( p  q)
A proposition which is always false is called a contradiction. The column of a
contradiction in a truth table contains only F's. for example P  ~P
p  q  (p  q)
If t is a tautology and c is a contradiction, then
p t  p
Page 14 blue box
kavita hatwal fall 2002 Math 231
and
pc  c
Conditional statements
If p and q are statement variables, the conditional of q by p is “if p then q” or
“p implies q” and is denoted by p  q. It is false when p is true and q is false.
A conditional statement is vacuously true or true by default if its
hypothesis is false.
ORDER of PRECEDENCE
()
~ or

 and 

p
T
T
F
F
q
T
F
F
F
p
T
F
T
T
q
kavita hatwal fall 2002 Math 231
“If it is raining, then I am carrying an umbrella.”
This statement is true
•when I am carrying an umbrella (whether or not it is raining), and
•when it is not raining (whether or not I am carrying an umbrella).
“IF you earn >=$25K, THEN you must file a tax return.”
What if I earn <$25K? Do I violate the tax law when I file/do-not-file a tax
return?
kavita hatwal fall 2002 Math 231
p  q ~ p  q
“If p then q” is logically equivalent to “not p or q”.
The negation of a conditional statement. The negation of “if p then q” is logically
equivalent to “p and not q”.
The negation of a conditional statement does not start with an if …then…
~ (p  q)  p ~ q
The contrapositive of a conditional statement of the form “if p then q” is
if ~ q then ~ p
Symbolically the contrapositive of
p  q is ~ q ~ p
A conditional statement is logically equivalent to its contrapositive.
kavita hatwal fall 2002 Math 231
Converse and inverse of a conditional statement.
contrapositive
converse
inverse
If ~q then ~p
If q then p
If ~p then ~q
~ q ~ p
q p
~ p ~ q
Converse and inverse of a conditional statement are not logically equivalent to
the statement but the converse and inverse of a statement are logically
equivalent to each other.
kavita hatwal fall 2002 Math 231
DEFINITION
ONLY IF
If p and q are statements,
p only if q means “if not q then not p”
Or, equivalently,
“if p then q”
Converting Only if to If-Then:
BICONDITIONAL
The biconditional of p and q is “p if and only if q” and is denoted by p  q . It is
true if both p and q have the same truth values and is false when if p and q have
opposite truth values.
Another way of looking at p iff q is “p if q” and “p only if q”
p  q  (~ p  q)  (~ q  p)
kavita hatwal fall 2002 Math 231
Necesssary and sufficient conditions:
If r and s are statements:
r is a sufficient condition for s means “if r then s”
r is a necessary condition for s means “if not r then not s”
r is a necessary condition for s also means “if s then r”
r is a necessary and sufficient condition for s also means
“r if and only if s”
kavita hatwal fall 2002 Math 231
Argument Forms
• Incorporated Doug Jones's notes on this section with some
of mine and some fetched from www
kavita hatwal fall 2002 Math 231
An argument form is called valid if whenever all the hypothesis are true, the
conclusion is also true
Any argument form in which it IS possible to have true premises and a false
conclusion at the same time is invalid.
kavita hatwal fall 2002 Math 231
Syllogistic Logic
A syllogism is an argument consisting of two premises and one
conclusion.
The first premise is the major premise
The second premise is the minor premise
A modus ponens argument is a syllogism of the form
"If p then q. We have p, therefore q."
p  q
p
q
So if is a [( p  q)  p]  q tautology, then this is a valid argument form
If the sum of digits is divisible by 3, then a number is
divisible by 3. The sum of 123 = 6, so 123 is divisible by 3.
kavita hatwal fall 2002 Math 231
A modus tollens argument is a syllogism of the form
"If p then q. We have not q, therefore not p."
pq
~q
~ p
This is the contra-positive of the modus ponens
If the sum of digits is divisible by 3, then a number is
divisible by 3.
The sum 124 = 7 is not divisible by 3, so 124 is not
divisible by 3
kavita hatwal fall 2002 Math 231
Invalid syllogisms
Reason by Inverse
If Doug teaches at Sylvania, then he works for PCC. Doug
does not teach at Sylvania, therefore he does not work for
PCC.
The inverse of a conditional need not be true.
Reason by Converse
If Doug teaches at Sylvania, then he works for PCC. Doug
works for PCC, therefore he teaches at Sylvania.
The converse of a conditional need not be true
kavita hatwal fall 2002 Math 231
Probabilistic Syllogism
If a person is an American, then he is probably not a
member of Congress. This person is a member of
Congress. Therefore he probably is not an American.
This seems like a contra-positive: not (not member of
Congress) therefore not an American.
But the notion of probability is not part of Boolean logic: a
statement is a declaration that something either is true or is
false, but is never probably true or probably false. Analysis
of probabilistic statements requires Bayesian logic, rather
than Boolean logic.
kavita hatwal fall 2002 Math 231
Inferential Logic
Disjunctions are valid argument forms
"p, therefore p or q".
Alice is a woman, therefore Alice is a woman or a brain-eating
serial killer
This is generalization
kavita hatwal fall 2002 Math 231
Conjunctions imply the component statements
"p and q, therefore p"
Alice is a woman and a PCC student, therefore Alice is a woman.
This is specialization
Elimination is a valid form
"p or q. Not q, therefore p"
Alice is a woman or a brain-eating serial killer. Alice is not a serial
killer, therefore Alice is a woman
Transitivity is a valid form
"if p then q. If q then r. p, therefore r."
If Doug teaches at Sylvania, then he works for PCC. If you work for
PCC then you participate in PERS. Therefore Doug participates in
PERS.
kavita hatwal fall 2002 Math 231
Division into cases in a valid form
"p or q.
If p then r.
If q then r.
Therefore r."
Doug either robbed a bank or stole a car. If you rob a bank you go to
jail. If you steal a car you go to jail. Therefore Doug will go to jail.
Contradiction is a valid form
If you can show that "p is false" leads to a contradiction then p is true and
vice versa
kavita hatwal fall 2002 Math 231
Arguments and Truth
Valid arguments need not true.
If Doug is a teacher then Doug smokes.
Doug is a teacher,
therefore Doug smokes.
This is valid modus ponens, but the major premise is
false, so the conclusion is valid but untrue
Invalid arguments need not be false
If Doug is a teacher, then Doug teaches Math.
Doug teaches Math,
therefore Doug is a teacher.
This is a converse error, but the conclusion is true
kavita hatwal fall 2002 Math 231
A more Complex Deduction
``And now we come to the great question as to the reason why. Robbery has
not been the object of this murder, for nothing was taken. Was it politics, or
was it a woman? That is the question confronting me. I was inclined from
the first to the latter supposition. Political assassins are only too glad to do
their work and fly. This murder had, on the contrary, been done most
deliberately and the perpetrator had left his tracks all over the room,
showing he had been there all the time.'' - A. Conan Doyle, A Study in
Scarlet
Reference: http://www.cs.sunysb.edu/~skiena/113/lectures/lecture4/lecture4.html
What did Sherlock Holmes conclude?
kavita hatwal fall 2002 Math 231
Propositions and Premises
We can break the story into the following propositions:
Holmes identifies the following premises defined on these propositions:
p: It was robbery.
q: Nothing was taken.
r: It was politics.
s: It was a woman.
t: The assassin left immediately.
u: The assassin left tracks all over the room.
p  (r  s)
q
q  ~
p
u  ~ t
r  t
kavita hatwal fall 2002 Math 231
q  ~ p
q
 ~ p
p  (r  s)
~ p
 r  s
Complete the above to logically prove Sherlock Holmes right
kavita hatwal fall 2002 Math 231
Knights and Knaves
Reference:http://www.hku.hk/cgi-bin/philodep/knight/puzzle
A very special island is inhabited only by knights and knaves. Knights
always tell the truth, and knaves always lie. You meet five inhabitants:
Carl, Zeke, Joe, Peggy and Bart. Carl claims, `Peggy and I are both
knights or both knaves.' Zeke claims that at least one of the following is
true: that Carl is a knave or that Joe is a knight. Joe says, `Both I am a
knight and Bart is a knave.' Peggy says that it's not the case that Bart is a
knave. Bart tells you, `Neither I nor Carl are knaves.' So who is a knight
and who is a knave?
kavita hatwal fall 2002 Math 231
1.4
•Logic circuits
•In series
•Parallel
•Truth tables for circuits
•Similarity to conjunction and disjunction
•Digital logic circuits.
•0 and 1 versus T and F
•Black box
kavita hatwal fall 2002 Math 231
Logic circuits
• Logic circuits perform
operations on digital signals
– Implemented as electronic
circuits where signal
values are restricted to a
few discrete values
• In binary logic circuits there
are only two values, 0 and 1
• The general form of a logic
circuit is a switching network
•
P
Q
R
Reference:http://jjackson.eng.ua.edu/c
ourses/ece380/lectures/
kavita hatwal fall 2002 Math 231
S
Variables and functions
• The simplest binary element is a switch that has two states
• If the switch is controlled by x, we say the switch is open if x =0 and
closed if x =1
x = 0
x = 1
Two states of a switch
kavita hatwal fall 2002 Math 231
Variables and functions (AND)
• Consider the possibility of two switches controlling the state of the
light
• Using a series connection, the light will be on only if both switches are
closed
– L(x1, x2)= x1· x2
– L=1 iff (if and only if) x1 AND x2 are 1
Power
supply
S
S
x
x
1
2
“·” AND operator
x1 · x2 = x1 x 2
L
Light
The circuit implements
a logical AND function
The logical AND function (series connection)
kavita hatwal fall 2002 Math 231
Variables and functions (OR)
• Using a parallel connection, the light will be on only if either or both
switches are closed
– L(x1, x2)= x1+ x2
– L=1 if x1 OR x2 is 1 (or both)
S
x
Power
supply
“+” OR operator
1
S
x
L
Light
The circuit implements
a logical OR function
2
The logical OR function (parallel connection)
kavita hatwal fall 2002 Math 231
An efficient way to design more complicated circuits is to build them by
connecting less complicated black box circuits.
•Logic gates
•Not
•And
•Or
Gates can be combined in variety of ways leading to combinational circuits, one
whose output at any time is determined entirely by its input at that time without
regard to previous inputs.
•Never combine two input wires
•A single input wire can be split halfway and used as input for two separate gates
•An output wire can be used as input
•No output of a gate can eventually feed back into that gate
Page 47, 1.4.1, 1.4.2
Boolean expression corresponding to a circuit
1.4.3
kavita hatwal fall 2002 Math 231
kavita hatwal fall 2002 Math 231
Recognizer: is a circuit that outputs a 1 for exactly one particular combination of
input signals and outputs 0’s for all other combinations
•Constructing circuits for boolean expressions example 1.4.4, page 49
•Simplifying combinational circuits, page 52
•Equivalent circuits, example 1.4.6, page 53
•Designing a circuit for a given input output table example 1.4.5, page 51
INPUT
OUTPUT
P
Q
R
S
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
kavita hatwal fall 2002 Math 231
Predicates and Quantified statements
Subject and predicate:
Subject is the person being talked about and predicate is what is being talked
about the subject. The predicate is part of the sentence from which subject has
been removed.
Are these statements?
•“He is a college student”
•“x + y > 0”
No they aren’t but they can be made to be true in two ways
In logic, predicates can be obtained from a statement by removing the nouns.
“James is a student at PCC.”
The nouns are James and PCC.
Let P= is a student at PCC
Q = is a student at
Then both P and Q are predicate symbols.
x is a student at y is symbolized as P(x) and as Q(x,y) respectively, where x and
y are predicate variables that take values in appropriate sets.
kavita hatwal fall 2002 Math 231
A predicate is a sentence that contains a finite number of variables and becomes a
statement when specific values are substituted for the variables. The domain of a
predicate variable is the set of all values that may be substituted in place of the
variable.
If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all
elements of D that make P(x) true when substituted for x. The truth set of P(x) is
denoted as
{x  D | P( x)}
Let P(x) and Q(x) be predicates and suppose the common domain of x is D. The
notation P(x)  Q(x) means that every element in the truth set of P(x) is in the truth
set of Q(x). The notation P(x)  Q(x) means that P(x) and Q(x) have identical
truth sets.
Example 2.1.1 page 77
• Predicates are not propositions.
• They can be made propositions by
Substituting concrete value to the variable
quantify the variable using a quantifier.
kavita hatwal fall 2002 Math 231
Quantifiers  
 Universal Quantifier, for all
Al human beings are mortal.
 human beings x, x is mortal.
 x in S, x is mortal.
Let Q(x) be a predicate and D be the domain of x. A Universal Quantifier is a
statement of the form  x
D, Q(x). It is defined to be true iff Q(x) is true for
every x in D. It is defined to be false iff Q(x) is false for atleast one x in D. Such
an x if it exists is called a counterexample.

Example 2.1.2 page 78.
kavita hatwal fall 2002 Math 231
Existential Quantifier, there exists,

Let Q(x) be a predicate and D be the domain of x. A Existential Quantifier is a
statement of the form x
D such that Q(x). It is defined to be true iff Q(x)
is true for at least one x in D. It is defined to be false iff Q(x) is false for all x
in D.

Example 2.1.3, 2.1.4, 2.1.5, 2.1.6, 2.1.7 page 78-81.
Negation of Quantified statements
The negation of a statement of the form
x in D, Q(x)
Is logically equivalent to a statement of the form
x in D such that ~ Q(x)
Symbolically
~ (x  D, Q( x))  x  D such that ~ Q(x)
Example 2.1.8, 2.1.9 page 82.
kavita hatwal fall 2002 Math 231
The negation of a statement of the form
x in D such that Q(x)
Is logically equivalent to a statement of the form
x in D, ~ Q(x)
Symbolically
~ (x  D such that Q( x))  x  D such that ~ Q(x)
Example 2.1.10 - 2.1.12 page 84, 85.
Negations of UNIVERSAL CONDITIONAL statements
~ (x, if P(x) then Q(x))   x such that P(x and ~ Q(x))
1.
2.
Read the quantifier from left to right.
If there are more than one quantifiers, read from inside out.
Example 2.1.13 page 86.
kavita hatwal fall 2002 Math 231
• Multiply quantified universal statements
– x  S, y  T, P(x, y)
– The order does not matter.
• Multiply quantified existential statements
– x  S, y  T, P(x, y)
– The order does not matter.
kavita hatwal fall 2002 Math 231
• Mixed universal and existential statements
–
–
–
–
x  S, y  T, P(x, y)
y  T, x  S, P(x, y)
The order does matter.
What is the difference?
• Compare
– x  R, y  R, x + y = 0.
– y  R, x  R, x + y = 0.
kavita hatwal fall 2002 Math 231
• Negate the statement
x  R, y  R, z  R, x + y + z = 0.
• (x  R, y  R, z  R, x + y + z = 0)
 x  R, (y  R, z  R, x + y + z = 0)
 x  R, y  R, (z  R, x + y + z = 0)
 x  R, y  R, z  R, (x + y + z = 0)
 x  R, y  R, z  R, x + y + z  0
kavita hatwal fall 2002 Math 231
• A universal conditional statement is of the form
x  S, P(x)  Q(x).
• The converse is
x  S, Q(x)  P(x).
• The inverse is
x  S, P(x)  Q(x).
• The contrapositive is
x  S, Q(x)  P(x).
• Necessary and sufficient condition
kavita hatwal fall 2002 Math 231
Boolean Algebras
• A Boolean algebra is a set S that
– includes two elements 0 and 1,
– has two binary operations + and ,
– has one unary operation ,
which satisfy the following properties for
all a, b, c in S:
kavita hatwal fall 2002 Math 231
Boolean Algebras
• Commutativity
– a + b = b + a.
– a  b = b  a.
• Associativity
– (a + b) + c = a + (b + c).
– (a  b)  c = a  (b  c).
kavita hatwal fall 2002 Math 231
Boolean Algebras
• Distributivity
– a  (b + c) = (a  b) + (a  c)
– a + (b  c) = (a + b)  (a + c)
• Identity
– a + 0 = a.
– a  1 = a.
kavita hatwal fall 2002 Math 231
Boolean Algebras
• Complementation
– a + a = 1.
– a  a = 0.
kavita hatwal fall 2002 Math 231
Examples: Boolean Algebras
• Let U be a nonempty universal set. Let 0 be
 and 1 be U. Let + be  and  be . Let 
be complementation. Then U is a Boolean
algebra.
• Let U be a nonempty universal set. Let 0 be
U and 1 be . Let + be  and  be . Let 
be complementation. Then U is a Boolean
algebra.
kavita hatwal fall 2002 Math 231
Examples: Boolean Algebras
• Let S be the set of all statements. Let 0 be F
and 1 be T. Let + be  and  be . Let  be
negation. Let = be . Then S is a Boolean
algebra.
• Let S be the set of all statements. Let 0 be T
and 1 be F. Let + be  and  be . Let  be
negation. Let = be . Then S is a Boolean
algebra.
kavita hatwal fall 2002 Math 231
Derived Properties
• Theorem: Let S be a Boolean algebra and
let a, b in S. Then
–
–
–
–
–
–
a  a = a.
a + a = a.
a  0 = 0.
a + 1 = 1.
a  b = a if and only if a + b = b.
a  b = a + b if and only if a = b.
kavita hatwal fall 2002 Math 231
Derived Properties, continued
–
–
–
–
–
–
a  b = 0 and a + b = 1 if and only if a = b.
0 = 1.
1 = 0.
(a) = a.
(a  b) = a + b.
(a + b) = a  b.
kavita hatwal fall 2002 Math 231
Example: Boolean Algebra
• Let S = {1, 2, 3, 5, 6, 10, 15, 30}.
• Define
– a + b = gcd(a, b).
– a  b = lcm(a, b).
– a = 30/a.
• Verify the 10 basic properties.
• The 12 derived properties follow.
• Ref: http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties
kavita hatwal fall 2002 Math 231