Chapter 1, Part I

Propositional Logic

With Question/Answer Animations

Chapter Summary
● Propositional Logic
● Predicate Logic
● Proofs
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Propositional Logic
Overview
● The Language of Propositions
● Connectives, Truth Values, Truth Tables
● Applications
● Translating English Sentences, System Specifications etc.
● Logical Equivalences
● Important Equivalences, Showing Equivalence, Satisfiability

2
Proposition:
A declarative sentence that is either true
or false.

3
Examples of propositions:
a) The Moon is made of green cheese.
b) Trenton is the capital of New Jersey.
c) Toronto is the capital of Canada.
d) 1 + 0 = 1
e) 0 + 0 = 2

4
Examples that are not propositions.
a) Sit down!
b) What time is it?
c) x + 1 = 2
d) x + y = z

5
Constructing Propositions
●Propositional Variables: p, q, r, s, …
●The proposition that is always true: T
●The proposition that is always false: F.

6
Compound Propositions:
● constructed from logical connectives and other
propositions
● Negation ¬
● Conjunction ∧

● Disjunction ∨
● Implication →
● Biconditional ↔

7
Negation
● The negation of p is denoted by ¬p and has this truth table:

p ¬p
T F
F T

● Example:
● p : “The earth is round.”
● ¬p : “It is not the case that the earth is round.”
or simply “The earth is not round.”
8
Conjunction
● The conjunction of p and q: p ∧ q

p q p∧q
T T T
T F F
F T F
● Example: F F F

● p: “I am at home.”
● q:“It is raining.”
● p ∧q : “I am at home and it is raining.”
9
Disjunction
● The disjunction of p and q: p ∨q

p q p∨q
T T T
T F T
F T T
● Example: F F F
● p: “I am at home.”
● q: “It is raining.”
● p ∨q: “I am at home or it is raining.”
10
Exclusive or (Xor)
● In p ⊕ q , one of p and q must be true, but not both!
● “Soup or salad comes with this entrée,” we do not expect
to be able to get both soup and salad.
● The truth table for ⊕ is:

p q p ⊕q

T T F
T F T
F T T
F F F

11
Implication
● If p and q are propositions;
● p →q is a conditional statement or implication which is read as “if p,
then q ”

p q p →q

T T T

T F F

F T T

F F T

12
Implication
● In p →q ,
● p is the hypothesis (antecedent or premise)
● q is the conclusion (or consequence).
● Example:
● p: “I am at home.” and q:“It is raining.” then;
● p →q denotes “If I am at home then it is raining.”

13
Understanding Implication
● The “meaning” of p →q depends only on the truth
values of p and q.
● there does not need to be any connection between the
antecedent (p) or the consequent (q).

14
Understanding Implication
● The “meaning” of p →q depends only on the truth
values of p and q.
● These implications are perfectly fine..Does it make
sense to you?..
● “If the moon is made of green cheese, then I
have more money than Bill Gates. ”
● “If 1 + 1 = 3, then your grandma wears combat
boots.”

15
Understanding Implication (cont)
● One way to view the logical conditional is to think of
an obligation or contract.
● “If I am elected, then I will lower taxes.”
● If the politician is elected and does not lower taxes, then the
voters can say that he or she has broken the campaign pledge.
● “If you get 100% on the final, then you will get an A.”
● Something similar holds for the professor.

16
Different Ways of Expressing p →q
if p, then q p implies q
if p, q p only if q
q unless ¬p q when p
q if p
q whenever p p is sufficient for q
q follows from p q is necessary for p

p—>q: q is a necessary condition for p

p—>q: p is a sufficient condition for q

17
Necessary vs Sufficient conditions
● Necessary condition:
● a—>b: b is a necessary condition for a
● which means; if not b, then not a
● equivalently; if a, then b

18
Necessary vs Sufficient conditions
● Necessary condition:
● a—>b: if not b, then not a
● => b is a necessary condition for a
● equivalently; if a, then b

● Example: A necessary condition for getting A in BBM205 is that a student

completes all the assignments. This can be expressed in two ways:
● if a student does not complete all the assignments, then he/she can
not get an A in BBM205
● (Contrapositive) if a student gets an A in BBM205, then he/she
completes all the assignments.
● Completing all the assignments is a necessary condition for getting A.

19
Necessary vs Sufficient conditions
● Sufficient condition:
● a—>b: a is a sufficient condition for b
● => if a is satisfied, then b is guaranteed

20
Necessary vs Sufficient conditions
● Sufficient condition:
● a—>b: a is a sufficient condition for b
● => if a is satisfied, then b is guaranteed

● Example: A sufficient condition for getting A in

BBM205 is that a student gets A from every piece of
graded work. This can be expressed as:
● if a student gets A from every piece of graded
work, then he/she gets an A in BBM205.
21
Converse, Contrapositive, and Inverse
●Given p →q :
● ¬ p → ¬ q : inverse of p →q
● q →p : converse of p →q
● ¬q → ¬ p : contrapositive of p →q

22
Converse, Contrapositive, and Inverse
● From p →q we can form new conditional statements .
● ¬p→¬q is the inverse of p →q
● q →p is the converse of p →q
● ¬q → ¬ p is the contrapositive of p →q

Example: Find the converse, inverse, and contrapositive of

“It raining is a sufficient condition for my not going to
town.”
Solution:
Original: “__________________________________”

inverse:
converse:
contrapositive:
23
Converse, Contrapositive, and Inverse
● From p →q we can form new conditional statements .
● ¬p→¬q is the inverse of p →q
● q →p is the converse of p →q
● ¬q → ¬ p is the contrapositive of p →q

Example: Find the converse, inverse, and contrapositive of

“It raining is a sufficient condition for my not going to
town.”
Solution:
Original: “If it is raining, then I will not go to town.”

inverse:
converse:
contrapositive:
24
Converse, Contrapositive, and Inverse
● From p →q we can form new conditional statements .
● ¬p→¬q is the inverse of p →q
● q →p is the converse of p →q
● ¬q → ¬ p is the contrapositive of p →q

Example: Find the converse, inverse, and contrapositive of

“It raining is a sufficient condition for my not going to
town.”
Solution:
Original: “If it is raining, then I will not go to town.”

inverse: If it is not raining, then I will go to town.

converse: If I do not go to town, then it is raining.
contrapositive: If I go to town, then it is not raining.
25
Biconditional
● If p and q are propositions, then;
● biconditional proposition p ↔q: “p if and only if q .”

p q p ↔q
T T T
T F F
F T F
F F T

● Example:
● p:“I am at home.” and q:“It is raining.”
● p ↔q:“I am at home if and only if it is raining.”
26
Expressing the Biconditional
● Some alternative ways “p if and only if q” is
expressed in English:

● p is necessary and sufficient for q

● if p then q , and conversely
● p iff q

27
Truth Tables
For Compound Propositions
● Construction of a truth table:
● Rows
● Need a row for every possible combination of values for
the atomic propositions.
● Columns
● Need a column for the compound proposition (usually at
far right)
● Need a column for the truth value of each expression that
occurs in the compound proposition as it is built up.
● This includes the atomic propositions

28
Example Truth Table
● Construct a truth table for
p q r ¬r p∨q p ∨ q → ¬r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
F T T F T F
F T F T T T
F F T F F T
F F F T F T

29
Equivalent Propositions
● Two propositions are equivalent if they always have
the same truth value.
● Example: Show using a truth table that the
conditional (implication) is equivalent to the
contrapositive.
Solution:
p q ¬p ¬q p →q ¬q → ¬ p
T T F F T T
T F F T F F
F T T F T T
F F T T T T 30
Using a Truth Table to Show Non-
Equivalence
Example: Show using truth tables that neither the
converse nor inverse of an implication are not
equivalent to the implication.
Solution:
p q ¬p ¬q p →q ¬ p →¬ q q→p

T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T

31
Problem
● How many rows are there in a truth table with n
propositional variables?

Solution: 2n

● This means that with n propositional variables, we can

construct 2n distinct (i.e., not equivalent) propositions.

32
Precedence of Logical Operators
Operator Precedence
¬ 1
∧ 2
∨
3
→ 4
↔
5

p ∨ q → ¬r is equivalent to (p ∨ q) → ¬r

If the intended meaning is p ∨ (q → ¬r )

then parentheses must be used.

33
Applications of
Propositional Logic
Section 1.2
Applications of Propositional Logic:
Summary
● Translating English to Propositional Logic
● System Specifications
● Boolean Searching
● Logic Puzzles
● Logic Circuits

35
Translating English Sentences
● Steps to convert an English sentence to a statement in
propositional logic
● Identify atomic propositions and represent using
propositional variables.
● Determine appropriate logical connectives

36
Example:
“If I go to Harry’s or to the country, I will not go
shopping.”
● p: I go to Harry’s
● q: I go to the country.
● r: I will go shopping.

37
Example:
“If I go to Harry’s or to the country, I will not go
shopping.”
● p: I go to Harry’s
● q: I go to the country.
● r: I will go shopping.

If p or q then not r.

38
Example:
“If I go to Harry’s or to the country, I will not go
shopping.”
● p: I go to Harry’s
● q: I go to the country.
● r: I will go shopping.

If p or q then not r.

39
Example
Problem: Translate the following sentence into propositional
logic:
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”

40
Example
Problem: Translate the following sentence into propositional logic:
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”

One Solution: Let a, c, and f represent respectively

a: “You can access the internet from campus,”
c: “You are a computer science major,” and
f: “You are a freshman.”
a→ (c ∨ ¬ f )
41
System Specifications
● System and Software engineers take requirements in
English and express them in a precise specification
language based on logic.
Example: “The automated reply cannot be sent when the file
system is full” (Express in propositional logic)

42
System Specifications
● System and Software engineers take requirements in
English and express them in a precise specification
language based on logic.
Example: “The automated reply cannot be sent when the file
system is full” (Express in propositional logic)
Solution: One possible solution:
p : “The automated reply can be sent”
q : “The file system is full.”
q→ ¬ p
43
Consistent System Specifications

A list of propositions is consistent if it is

possible to assign truth values to the proposition
variables so that each proposition is true.

44
Consistent System Specifications
Exercise: Are these specifications consistent?
●“The diagnostic message is stored in the buffer or it
is retransmitted.”
●“The diagnostic message is not stored in the buffer.”
●“If the diagnostic message is stored in the buffer,
then it is retransmitted.”

45
Consistent System Specifications
Exercise: Are these specifications consistent?
● “The diagnostic message is stored in the buffer or it is
retransmitted.”
● “The diagnostic message is not stored in the buffer.”
● “If the diagnostic message is stored in the buffer, then it is
retransmitted.”
Solution:
p: “The diagnostic message is stored in the buffer.”
q: “The diagnostic message is retransmitted”
The specification: p ∨ q, ¬p, p → q.
Can we assign truth values to p and q such that each three
proposition above becomes True?

46
Consistent System Specifications
Exercise: Are these specifications consistent?
● “The diagnostic message is stored in the buffer or it is
retransmitted.”
● “The diagnostic message is not stored in the buffer.”
● “If the diagnostic message is stored in the buffer, then it is
retransmitted.”
Solution:
p: “The diagnostic message is stored in the buffer.”
q: “The diagnostic message is retransmitted”
The specification: p ∨ q, ¬p, p → q.
Indeed! When p is F and q is T, all three statements are true.
So the specification is consistent.

47
Consistent System Specifications
Exercise: Are these specifications consistent?
● “The diagnostic message is stored in the buffer or it is retransmitted.”
● “The diagnostic message is not stored in the buffer.”
● “If the diagnostic message is stored in the buffer, then it is retransmitted.”

What if we add another specification, as follows:

● “The diagnostic message is not retransmitted.”

Solution: Now we are adding ¬q to the existing p ∨ q, ¬p, p → q.

There is no satisfying assignment that makes all specs true.
So the specification is not consistent.

48
Next
● Propositional Equivalences

49