COMP2022|2922
Models of Computation
Lesson 2a: Propositional Logic Equivalences and Consequences
Presented by
Sasha Rubin
School of Computer Science
Formulas that “mean the same thing” are called equivalent. We now study common equivalences, also called laws.
1/16
Equivalences
Recall that although the formulas (A ∧ B) and (B ∧ A) are syntactically different formulas, they mean the same thing.
Let’s make this idea precise.
Definition
Two formulas F and G are (logically) equivalent if they are assigned the same truth value under every assignment. This is written F ≡ G.
2/16
Equivalences
Are the following pairs of formulas equivalent?
1. p and q?
2. (p→q) and (q→p)?
3. (p→q) and (¬q→¬p)? 4. (p∨¬p) and (q∨¬q)?
3/16
Some Equivalences
For all formulas F, G, H: (Idempotent Laws)
(Commutative Laws)
(Associative Laws)
(Distributive Laws)
(de Morgan’s Laws)
(Double Negation Law) (Validity Law)
(Unsatisfiability Law)
F ≡ (F ∧ F )
F ≡ (F ∨ F ) (F ∧ G) ≡ (G ∧ F ) (F ∨ G) ≡ (G ∨ F )
(F ∧ (G ∧ H)) ≡ ((F ∧ G) ∧ H)
(F ∨(G∨H))≡((F ∨G)∨H)
(F ∧ (G ∨ H)) ≡ ((F ∧ G) ∨ (F ∧ H)) (F ∨(G∧H))≡((F ∨G)∧(F ∨H))
¬(F ∧ G) ≡ (¬F ∨ ¬G) ¬(F ∨G) ≡ (¬F ∧¬G)
¬¬F ≡ F
(⊤ ∨ F ) ≡ ⊤
(⊤ ∧ F ) ≡ F
(⊥ ∨ F ) ≡ F
(⊥ ∧ F ) ≡ ⊥ 4/16
Equivalences
Which equivalence can be used to justify that the following two statements, logically speaking, say the same thing?
1. There are fires outside Sydney and the air in Sydney is polluted.
2. The air in Sydney is polluted and there are fires outside Sydney.
A = “There are fires outside Sydney” B = “The air in Sydney is polluted”
By the Law of Commutativity of ∧, we know that (A ∧ B) is equivalent to (B ∧ A).
5/16
Equivalences
There are a number of ways to verify an equivalence.
1. Use truth tables.
2. Deduce it from other equivalences (using the fact that ≡ is transitive).
6/16
Equivalences
Verify the following equivalence:
(p→q) ≡ (¬q→¬p) … using truth tables
7/16
Equivalences
Verify the following equivalence:
(p→q) ≡ (¬q→¬p)
… using deduction from other equivalences
(p → q) ≡ (¬p ∨ q) ≡ (q ∨ ¬p)
≡ (¬¬q ∨ ¬p) ≡ (¬q → ¬p)
Definition of → Commutative Law for ∨ Double Negation Law Definition of →
Aside. What justifies the use of Double Negation inside the formula?
– Fact. If F is a subformula of H, and F ≡ G, then H is equivalent to formulas that result by substituting an occurrence of F in H by G. This is called the Substitution Rule.
7/16
Equivalences: applications (1)
– Equivalences can be used to rewrite a formula into an equivalent one having a special structure, called a normal form.
– You will see normal forms in the tutorials/assignments.
8/16
Equivalences: applications (2)
– We defined the syntax of propositional formulas to only use the connectives ∧, ∨ and ¬.
– Other connectives like → were defined in terms of these ones.
– Could we have made a different choice of connectives when
defining the syntax? . . . Yes!
Fact. Every propositional formula is equivalent to a formula which
only contains the operators ¬ and ∧.
– e.g., (¬p ∨ q) is equivalent to ¬(p ∧ ¬q).
Fact. Every propositional formula is equivalent to a formula which only contains the operators ¬ and →.
– e.g., (p ∧ q) is equivalent to ¬(p → ¬q).
9/16
Logic allows us to formalise what it means for an argument (”if these facts are true, then that fact must be true”) to be correct. This is done with an idea called logical consequence.
10/16
Logical consequence
Definition
Say that F is a logical consequence of {E1, · · · , Ek}, if every assignment that makes all of the formulas Ei (for 1 ≤ i ≤ k) true also makes F true. We write this as
{ E 1 , · · · , E k } |= F
11/16
Logical consequence
Example
Use truth tables to determine whether {p, (p → q)} |= q.
12/16
Logical consequence
Example
Use truth tables to determine whether { ( p → r ) , ( q → r ) , ( p ∨ q ) } |= r .
13/16
Logical consequence
Example
Use truth tables to determine whether {(p → q)} |= (q → p).
14/16
Logical consequence: Application
– Logic is used to study correct argumentation and reasoning.
– This is useful for coding, reasoning about the world, mathematics, etc.
Example
Why is the following argument correct?
1. Ifx=5thenz=4
2. x = 5
3. Conclude z = 4
The reason is that it is a particular instance of the fact that
{(p→q),p} |= q
15/16
Logical consequence: Application
Example
Why is the following argument correct? 1. Ifx=5thenz=4
2. Ifx<1thenz=4
3. Eitherx=5orx<1
4. Conclude z = 4
The reason is that it is a particular instance of the fact that
{ ( p → r ) , ( q → r ) , ( p ∨ q ) } |= r
16/16