CSM2127: Discrete Mathematics
Propositional Logic
Presented By:
Professor Dr. Md. Rakib Hassan
Department of Computer Science and Mathematics
Email: [email protected]
Applications of Propositional Logic
❖Translating English to Propositional Logic
❖System Specifications
❖Logic Puzzles
❖Logic Circuits
❖Others
2
Translating English Sentences
❖Steps to convert an English sentence to a statement
in propositional logic
o Identify atomic propositions and represent using
propositional variables.
o Determine appropriate logical connectives
❖“If I go to university or to the bank, I will not go
shopping.”
o p: I go to university
If p or q then not r.
o q: I go to the bank
o r: I will go shopping
3
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.”
4
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 From previous lecture
❖ q whenever p
❖ p is sufficient for q
❖ q follows from p
❖ q is necessary for p
❖ a necessary condition for p is q
❖ a sufficient condition for q is p
PROF. DR. MD. RAKIB HASSAN 5
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 𝑝, 𝑞, and 𝑟 represent respectively “You can access
the internet from campus,” “You are a computer science major,” and
“You are a freshman.”
𝑝 → (𝑞 ∨ ¬𝑟 )
6
System Specifications
❖System and Software engineers take requirements in English
and express them in a precise specification language based on
logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when the file system is
full”
Solution: One possible solution: Let 𝑝 denote “The automated
reply can be sent” and 𝑞 denote “The file system is full.”
𝑞 → ¬𝑝
7
Consistent System Specifications
Definition: A list of propositions is consistent if it is possible to assign truth
values to the proposition variables so that each proposition is true.
Exercise: Are these specifications consistent?
o “The diagnostic message is stored in the buffer or it is retransmitted.”
o “The diagnostic message is not stored in the buffer.”
o “If the diagnostic message is stored in the buffer, then it is retransmitted.”
8
Consistent System Specifications
Definition: A list of propositions is consistent if it is possible to assign truth
values to the proposition variables so that each proposition is true.
Exercise: Are these specifications consistent?
o “The diagnostic message is stored in the buffer or it is retransmitted.”
o “The diagnostic message is not stored in the buffer.”
o “If the diagnostic message is stored in the buffer, then it is retransmitted.”
Solution: Let 𝑝 denote “The diagnostic message is stored in the buffer.” Let
𝑞 denote “The diagnostic message is retransmitted” The specification can
be written as: 𝑝 ∨ 𝑞, ¬𝑝, 𝑝 → 𝑞. When 𝑝 is false and 𝑞 is true all three
statements are true. So, the specification is consistent.
o What if “The diagnostic message is not retransmitted” is added.
Solution: Now we are adding ¬q and there is no satisfying assignment. So, the
specification is not consistent.
9
Logic Circuits
❖ Electronic circuits; each input/output signal can be viewed as a 0 or 1.
o 0 represents False
o 1 represents True
❖ Complicated circuits are constructed from three basic circuits called gates.
o The inverter (NOT gate) takes an input bit and produces the negation of that bit.
o The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits.
o The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits.
❖ More complicated digital circuits can be constructed by combining these basic circuits to
produce the desired output given the input signals by building a circuit for each piece of the
output expression and then combining them. For example:
10
Exercise
❖ Whenever the system software is being upgraded, users cannot access the
file system. If users can access the file system, then they can save new files.
If users cannot save new files, then the system software is not being
upgraded.
o Are these system specifications consistent?
11
Tautologies, Contradictions, and Contingencies
❖ A tautology is a proposition which is always true.
o Example: p ∨¬p
❖ A contradiction is a proposition which is always false.
o Example: p ∧¬p
❖ A contingency is a proposition which is neither a tautology nor a
contradiction, such as 𝑝
𝑝 ¬p p ∨¬p p ∧¬p
T F T F
F T T F
12
Logically Equivalent
❖ Two compound propositions p and q are logically equivalent if 𝑝 𝑞 is a
tautology.
❖ We write this as 𝑝 ⇔ 𝑞 or as 𝑝 ≡ 𝑞 where p and 𝑞 are compound
propositions.
❖ Two compound propositions 𝑝 and 𝑞 are equivalent if and only if the
columns in a truth table giving their truth values agree.
❖ This truth table shows that ¬𝑝 ∨ 𝑞 is equivalent to 𝑝 → 𝑞.
𝑝 𝑞 ¬𝑝 ¬𝑝 ∨ 𝑞 𝑝→𝑞
T T F T T
T F F F F
F T T T T
F F T T T
13
De Morgan’s Laws
Augustus De Morgan
1806-1871
This truth table shows that De Morgan’s Second Law holds.
𝑝 𝑞 ¬𝑝 ¬𝑞 (𝑝 ∨ 𝑞) ¬(𝑝 ∨ 𝑞) ¬𝑝 ∧ ¬𝑞
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
14
Equivalence Name
𝑝∧𝑇 ≡𝑝
Identity laws
𝑝∨𝐹 ≡𝑝
𝑝∨𝑇 ≡𝑇
Domination laws
𝑝∧𝐹 ≡𝐹
𝑝∨𝑝 ≡𝑝
Idempotent laws
𝑝∧𝑝 ≡𝑝
¬(¬𝑝) ≡ 𝑝 Double negation law
Logical 𝑝∨𝑞 ≡𝑞∨𝑝
Commutative laws
𝑝∧𝑞 ≡ 𝑞∧𝑝
Equivalences (𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟)
Associative laws
(𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
Distributive laws
𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
De Morgan’s laws
¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝
Absorption laws
𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝
𝑝 ∨ ¬𝑝 ≡ 𝑇
Negation laws
𝑝 ∧ ¬𝑝 ≡ 𝐹
15
More Logical Equivalences
Logical Equivalences Involving Logical Equivalences Involving
Conditional Statements Biconditional Statements
16
Constructing New Logical Equivalences
❖ We can show that two expressions are logically equivalent by
developing a series of logically equivalent statements.
❖ To prove that 𝐴 ≡ 𝐵, we produce a series of equivalences beginning
with 𝐴 and ending with 𝐵.
𝐴≡𝐵
𝐴𝑛 ≡ 𝐵
❖ Keep in mind that whenever a proposition (represented by a
propositional variable) occurs in the equivalences listed earlier, it
may be replaced by an arbitrarily complex compound proposition.
17
Equivalence Proofs
Example: Show that ¬(𝑝 → 𝑞) and 𝑝 ∧ ¬𝑞 are logically
equivalent.
Solution:
18
Equivalence Proofs
Example: Show that ¬(𝑝 ∨ (¬𝑝 ∧ 𝑞)) and ¬𝑝 ∧ ¬𝑞 are logically
equivalent by developing a series of logical equivalences.
Solution:
19
Equivalence Proofs
Example: Show that (𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) is a tautology.
Solution:
20
Exercise
❖ Determine whether (¬𝑝 ∧ (𝑝 → 𝑞)) → ¬𝑞 is a tautology.
❖ Show that (𝑝 ∨ 𝑞) ∧ (¬𝑝 ∨ 𝑟) → (𝑞 ∨ 𝑟) is a tautology.
❖ Show that 𝑝 𝑞 and (𝑝 ∧ 𝑞) ∨ (¬𝑝 ∧ ¬𝑞) are logically equivalent using
truth tables and logical equivalences.
❖ Show that 𝑝 → 𝑞 and ¬𝑞 → ¬𝑝 are logically equivalent using truth tables
and logical equivalences.
21
Propositional Satisfiability
❖A compound proposition is satisfiable if there is an assignment
of truth values to its variables that make it true.
❖When no such assignments exist, the compound proposition is
unsatisfiable.
❖A compound proposition is unsatisfiable if and only if its
negation is a tautology.
❖A truth table can be used to determine whether a compound
proposition is satisfiable, or equivalently, whether its negation
is a tautology.
22
Questions on Propositional Satisfiability
Example: Determine the satisfiability of the following compound
propositions:
Solution: Satisfiable. Assign T to p, q, and r.
Solution: Satisfiable. Assign T to p and F to q.
Solution: Not satisfiable. Check each possible assignment of truth values to
the propositional variables and none will make the proposition true.
23
Exercise
❖ Determine whether the following compound proposition is satisfiable:
(𝑝 → 𝑞) ∧ (𝑝 → ¬𝑞) ∧ (¬𝑝 → 𝑞) ∧ (¬𝑝 → ¬𝑞)
24
25
