EE369: Discrete Math

Propositional Logic

1
1

Outline
• Logic
• Propositional Logic
• Well formed formula
• Truth table
• Tautology & Contradiction
• Proof System for Propositional Logic
• Deduction method
• Formalizing English arguments
• Text book chapters 1.1 and 1.2
2
2
 Logics
To define a logic, answer three questions:
1. What are the models?
2. What are the formulas?
3. Which formulas are true in which
models?
A logic is a formal system relating
syntax (formulas) and
semantics (models of the world).
3
3

Propositional Logic: Models

• A statement or a proposition is a sentence that
is either true or false. Represented as upper
cap letters of the alphabet.
– “She is very talented”
– “There are life forms on other planets in the
universe”
– Q: “Today is Tuesday”

• Statement letters can be combined into new

statements using logical connectives of
– conjunction (AND, Ù)
– disjunction (OR, Ú)
– implication (®)
– equivalence («)
– negation (¢ or ¬)
4
4
 Propositional Logic: Formulas
• Truth tables define how each of the
connectives operate on truth values.
• Truth table for implication (®)
• Equivalence connective A « B is
shorthand for (A ® B) Ù (B ® A)
• Truth table for equivalence («)
• Binary & unary connective

5
5

When is a formula true in a model?

• Each Boolean connective has a truth table
e.g. P Q PÚQ P Q PÙQ
T T T T T T
T F T T F F
F T T F T F
F F F F F F
P ¬P
T F
F T
6
6
 What about the other connectives?

P Q P®Q P Q P«Q
T T T T T T
T F F T F F
F T T F T F
F F T F F T

“P is the same as Q”
Tricky cases

7
7

Abstract: What about new connectives?

☺
P Q P☺Q
T T T
T F T
F T F
F F T

Truth tables define the connective

8
8
 Connective Truth Table Summary

9
9

Connectives in English

10
10
 Example formulas and non-formulas
• “If the rain continues, then the river will
flood.” Express by implication.
• A: the rain continues
B: the river floods
• If A, then B: ---- A ® B
• If the river floods, did the rain continue?

A B A®B
T T T

F T T
F F T
11
11

Example formulas and non-formulas

• “A good diet is a necessary condition for
a healthy cat.” Express by implication.
• C: the cat has a good diet
D: the cat is healthy

“B is a necessary condition for A”: A ® B

Thus D ® C

12
12
 Example formulas and non-formulas
• “Julie likes butter but hates cream.”
Negate this.
• A: Julie likes butter
B: Julie hates cream
“A but B” ---- A Ù B

Need (A Ù B)’

13
13

Example formulas and non-formulas

• “Julie likes butter but hates cream.”
Negate this.
• Negation:
A B A Ù B (A Ù B)’ A’ B’ A’ÚB’
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

14
14
 Example formulas and non-formulas
• “Julie likes butter but hates cream.”
Negate this.
A B A Ù B (A Ù B)’ A’ B’ A’ÚB’
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
• A’: Julie does not like butter
B’: Julie does not hate (likes) cream
Julie does not like butter or likes cream
15
15

Additional Negation Examples

1. The processor is fast but the printer is slow
1. Either the processor is slow or the printer is fast

2. The processor is fast or else the printer is slow

2. The processor is slow and the printer is fast

3. If the processor is fast then the printer is slow

3. If the processor is fast but so is the printer

16
16
 Formulas & Precedence
• Well-formed formula: A valid string with
statement letters, connectives, and
parentheses
– (((AÙB))) Ù D
– (A¢®B) Ù(C¢ÚA)

• Non-WFF
– (A¢®®B))) Ù Ù(C¢ÚA)

17
17

Formulas & Precedence

• Precedence
– AÚB®C º (AÚB)®C OR AÚ(B®C)?

• Rules:
1. Innermost parenthesis () first
2. Negation ‘
3. Ù ,Ú
4. ®
5. «

18
18
 Formulas & Precedence

• Main connective: Last connective to be

applied in a WFF
– (A¢®B) Ù(C¢ÚA) Ù
– (AÚB)®C ®
– (((A¢®B) Ù(C¢))ÚA) Ú

19
19

Example of Truth Table for a WFF

• Compound WFF (A¢®B) Ù(C¢ÚA)
P Q P®Q
T T T
T F F
F T T
F F T

• # rows in a truth table with n statement

letters = ?

20
20
 Truth Table Scale

21
21

Tautologies and Contradictions

• A tautology is a formula that is true in
every model. (also called a theorem)
– for example, (A Ú ¬A) is a tautology
– What about (AÚB)Ú(A¢ÚB¢)?
– Look at tautological equivalences on pg. 8
of text

• A contradiction is a formula that is false

in every model.
– for example, (A Ù ¬A) is a contradiction

22
22
 De Morgan’s Laws
• (AÚB)¢ = A¢ÙB¢
• Negate “The couch is either new or
comfortable.”
• (AÙB)¢ = A¢ÚB¢
• Negate “The book is thick and boring.”

23
23

De Morgan’s by Truth Table

• (AÙB)¢ = A¢ÚB¢

A B A Ù B (A Ù B)’ A’ B’ A’ÚB’
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

24
24
 1.1 Objectives and Summary
• You can now:
– Construct truth tables from WFF’s
– Define tautologies and contradictions

• Summary:
– WFFs are symbolic representations of
statements
• “Julie likes milk but not cream.” : AÙB
– Truth values for compound WFF’s depend
on inputs and connectives
• # of rows = 2^n
25
25

A Proof System
• A proof system is a syntactic system for
finding formulas implied by the hypotheses
– “syntactic” means manipulating syntax
• i.e. manipulating formulas rather than models.
– P1ÙP2Ù … Pn®Q is a tautology

• A proof is a sequence of formulas, where

each formulas in the sequence is either
– a hypothesis
– a formula justified by previous formulas and a
proof rule
• The sequence “proves” the last formula
26
26
 Example proof rule

P
modus ponens (mp)
P®Q
________________
Q
Given the formulas above the line, we can
add the formula below the line to the
proof.

27
27

Example proof
• Hypotheses: C, B, B ® (C ® A)
• Conclusion: A

1. B premise
2. B ® (C ® A) premise
3. C®A 1, 2, mp
4. C premise
5. A 3, 4, mp

28
28
 Proof rules: Equivalence rules (Table 1.12)
Expression Equivalent Rule name Abbr.

PÚQ QÚP Commutative comm

PÙQ QÙP
(P Ú Q) Ú R P Ú (Q Ú R ) Associative ass
(P Ù Q) Ù R P Ù (Q Ù R )
¬(P Ú Q) ¬P Ù ¬Q De Morgan dm
¬(P Ù Q) ¬P Ú ¬Q
P®Q ¬P Ú Q Implication imp

¬(¬ P) P Double Neg. dn

P«Q (P ® Q) Ù Equivalence equ

(Q ® P)
29
29

Proof Rules: Inference Rules (Table 1.13)

From Can Rule name Abbr.

derive
P, P ® Q Q Modus ponens mp
P ® Q, ¬Q ¬P Modus tollens mt
P, Q PÙQ Conjunction con
PÙQ P, Q Simplification sim
P PÚQ Addition add

30
30
 An Example Proof
[(AÚB¢)®C] Ù (C®D) Ù A ® D
(P1ÙP2Ù … Pn®Q is a tautology)

1. (AÚB¢)®C Hyp/premise
2. C®D Hyp/premise
3. A Hyp/premise
4. AÚB¢ 3, add
5. C 1,4, mp
6. D 2,5,mp

31
31

Deduction Method in Proofs

• When proving P ® Q…
– add P to premises and prove Q.

• Repeat to prove P ® (Q ® R)
– add P and Q to premises and prove R.

• To prove: P1 Ù P2 Ù… Pn® (R® S),

prove: P1 Ù P2 Ù… Pn Ù R ® S

32
32
 Deduction Example
• To prove: P1 Ù P2 Ù… Pn® (R® S),
prove: P1 Ù P2 Ù… Pn Ù R ® S
• [A ®(B ®C)] Ù(A ÚD’) ÙB ®(D ®C)
1. A ®(B ®C) Hyp/premise
2. A ÚD’ Hyp/premise
3. B Hyp/premise
4. D Hyp/premise (Deduction)
5. D’ ÚA 2,comm
6. D ®A 5,imp
7. A 4,6,mp
8. B ®C 1,7,mp
9. C 3,8,mp
33
33

Review from 1/24/2017: Logics

• Logics are models, formulas, and
definitions that represent the world
– Statements: A; B; C; “Today is Thursday”
– Connectors: ®, Ú, Ù, ‘, ¬, «
– Well-formed formulas (WFF)

• Truth tables define the logic

– 2^n rows for n input statements
– Can show equivalence (De Morgan’s)
– Implication can be tricky

34
34
 Connectives in English

35
35

Review from 1/24/2017: Implication

• “If the rain continues, then the river will
flood.” Express by implication.
• A: the rain continues
B: the river floods
• If A, then B: ---- A ® B
• If the river floods, did the rain continue?
A B A®B
T T T
T F F
F T T
F F T
36
36
 Review from 1/24/2017: Negation
• “Julie likes butter but hates cream.”
Negate this.
• A: Julie likes butter
B: Julie hates cream
“A but B” ---- A Ù B

Need (A Ù B)’ « (A’ÚB’) – De Morgan’s

• “Julie hates butter or likes cream”

37
37

Review from 1/24/2017: Negation

• Negate “Cucumbers are green and seedy:”
1. Cucumbers are not green and not seedy
2. Cucumbers are not green or not seedy
3. Cucumbers are green and not seedy
– Which answer(s) are valid negations?
• “The carton is sealed or the milk is sour”
1. The milk is not sour or the carton is not sealed
2. The carton is not sealed and also the milk is not
sour
3. If the carton is not sealed, then the milk will be
sour
38
38
 Review from 1/24/2017: Definitions
• A tautology is a formula that is true in
every model. (also called a theorem)
– for example, (A Ú ¬A) is a tautology

• A contradiction is a formula that is false

in every model.
– for example, (A Ù ¬A) is a contradiction

• De Morgan’s
– (AÚB)¢ = A¢ÙB¢
– (AÙB)¢ = A¢ÚB¢
39
39

Review from 1/24/2017: Prop. Proofs

• A proof system is a syntactic system for
finding formulas implied by the hypotheses
– Show that P1ÙP2Ù … Pn®Q is a tautology

• A proof is a sequence of formulas, where

each formulas in the sequence is either
– a hypothesis
– a formula justified by previous formulas and a
proof rule

• The sequence “proves” the last formula

40
40
 Review from 1/24/2017: The Proposition
• P1ÙP2Ù … Pn®Q
– P1… Pn are hypotheses or predicates
– Q is the conclusion
– If P1… Pn are true, show that Q is true
• Syntactic manipulation to form tautology

• Example proposition:
– If Bob is hungry, then he will eat. Bob is
hungry. Therefore, he will eat.
• (H®E) Ù H ® E

41
41

Review from 1/24/2017: Modus Ponens

P
modus ponens (mp)
P®Q
________________
Q
– If Bob is hungry, then he will eat. Bob is
hungry. Therefore, he will eat.
• (H®E) Ù H ® E

42
42
 Review: Formal Proof
• If Bob is hungry, then he will eat. Bob is
hungry. Therefore, he will eat.
– (H®E) Ù H ® E

1.(H®E) hypothesis
2.H hypothesis
3.E 1,2,modus ponens

43
43

Proof rules: Equivalence rules (Table 1.12)

Expression Equivalent Rule name Abbr.

PÚQ QÚP Commutative comm

PÙQ QÙP
(P Ú Q) Ú R P Ú (Q Ú R ) Associative ass
(P Ù Q) Ù R P Ù (Q Ù R )
¬(P Ú Q) ¬P Ù ¬Q De Morgan dm
¬(P Ù Q) ¬P Ú ¬Q
P®Q ¬P Ú Q Implication imp

¬(¬ P) P Double Neg. dn

P«Q (P ® Q) Ù Equivalence equ

(Q ® P)
44
44
 Proof Rules: Inference Rules (Table 1.13)

From Can Rule name Abbr.

derive
P, P ® Q Q Modus ponens mp
P ® Q, ¬Q ¬P Modus tollens mt
P, Q PÙQ Conjunction con
PÙQ P, Q Simplification sim
P PÚQ Addition add

45
45

Prop. Logic Proof: Example 1

46
46
 Prop. Logic Proof: Example 2

47
47

Prop. Logic Proof: Example 3

48
48
 Prop. Logic Proof: Example 4

49
49

Prop. Logic Proof: Example 5

50
50
 Formalizing English Arguments
To formalize an English argument:
1. Find the minimal statements in the
argument and symbolize them with
propositional letters A, B, …
2. Convert English connectives to
propositional ones.
3. Give a proof of the conclusion using
the premises.

51
51

Examples
Jack went to fetch a pail of water. Jack
fetches a pail of water only if Jack works
hard. Jack works hard only when Jack is
paid. Therefore Jack was paid.

52
52
 Minimal True/False Statements
Jack went to fetch a pail of water. Jack
fetches a pail of water only if Jack works
hard. Jack works hard only if Jack is
paid. Therefore Jack was paid.
A = Jack fetches a pail of water
B = Jack works hard
C = Jack is paid

A. A only if B. B only if C. Therefore C.

53
53

Eliminating connectives
A. A only if B. B only if C. Therefore C.
becomes
Hypotheses: A, A ® B, B ® C.
Conclusion: C.

Easy to prove that these hypotheses give

this conclusion using rule mp.

54
54
 Examples — a bad argument
Jack went to fetch a pail of water. Jack
fetches a pail of water if Jack works
hard. Jack works hard if Jack is paid.
Therefore Jack was paid.
Hypotheses: A, B ® A, C ® B.
Conclusion: C.
Hypotheses do not entail conclusion…to
show this, give a model that makes the
conclusion false.
– A=T, B=T, C=F
55
55

Another example
Fish can walk. Fish can walk only if
elephants can fly. Elephants can fly only
if eggplants can talk. Therefore,
eggplants can talk.
Is this a valid argument?

56
56
 Another example
Fish can walk. Fish can walk only if
elephants can fly. Elephants can fly only
if eggplants can talk. Therefore,
eggplants can talk.

A: Fish can walk

B: Elephants can fly
C: Eggplants can talk

57
57

Another example
A. A only if B. B only if C. Therefore, C.

A: Fish can walk

B: Elephants can fly
C: Eggplants can talk

Hypothesis: A, A ® B, B ® C
Conclusion: C

58
58
 Formalizing: Example 1
• If chicken is on the menu, then don’t
order fish, but you should have either
fish or salad. So if chicken is on the
menu, have salad.

59
59

Formalizing: Example 2
• The crop is good, but there is not
enough water. If there is a lot of rain or
not a lot of sun, then there is enough
water. Therefore the crop is good and
there is a lot of sun.

60
60
 Formalizing w/ Proof: Example 1
• If the program is efficient, then it
executes quickly. Either the program is
efficient, or it has a bug. However, the
program does not execute quickly.
Therefore it has a bug.

61
61

Formalizing w/ Proof: Example 2

• If Jane is more popular, then she will be
elected. If Jane is more popular, then
Craig will resign. Therefore if Jane is
more popular, she will be elected and
Craig will resign.

62
62
 Formalizing w/ Proof: Example 3
• It is not the case that if electric rates go
up, then usage will go down, nor is it true
that either new power plants will be built
or bills will not be late. Therefore usage
will not go down and bills will be late.

63
63

Examples where propositional logic fails

Every positive number is greater than zero. Five is a
positive number. Therefore, five is greater than zero.
Minimal statements?
A = Every positive number is greater than zero.
B = Five is a positive number.
C = Five is greater than zero.

Hypotheses: A, B. Conclusion: C.
Conclusion not entailed (consider A = B = T, C = F)
Our logic does not model the
internal structure of the propositions
64
64