L7.pdf

CMPUT 272 (Stewart)

University of Alberta

Lecture 7

Reading: Epp 3.4 Rules of inference and formal proofs in predicate logic To prove that X logically implies Y , show that every interpretation that makes X true also makes Y true by giving: an informal argument or a formal proof using rules of inference and logical equivalences.

1

Valid Rules of Inference for Quantifiers [Epp 3.4, Grimaldi 2.5] 1. Universal Instantiation (Specification) ∀x ∈ D, P (x) ∴ P (a)

where a is any particular element of D

2. Universal Generalization P (a) ∴ ∀x ∈ D, P (x)

where a is an arbitrary element of D

3. Existential Instantiation (Specification) ∃x ∈ D such that P (x) ∴ P (a) for some a in D 4. Existential Generalization P (a) where a is an element of D ∴ ∃x ∈ D such that P (x) 5. Universal Modus Ponens ∀x ∈ D, (P (x) → Q(x)) P (a) where a is an element of D ∴ Q(a) 6. Universal Modus Tollens ∀x ∈ D, (P (x) → Q(x)) ∼ Q(a) where a is an element of D ∴ ∼ P (a) 7. Universal Transitivity ∀x ∈ D, (P (x) → Q(x)) ∀x ∈ D, (Q(x) → R(x)) ∴ ∀x ∈ D, (P (x) → R(x)) 2

Proofs in Predicate Logic Example: The domain of all variables is D. ∀x, (P (x) ∨ ∼ Q(x)) ∀x, (P (x) → R(x)) ∀x, (∼ Q(x) → R(x)) ∴ ∀x, R(x)

1.

∀x, (P (x) ∨ ∼ Q(x))

Premise

2.

∀x, (P (x) → R(x))

Premise

3.

∀x, (∼ Q(x) → R(x))

Premise

4.

P (a) ∨ ∼ Q(a)

1, Universal Instantiation a is an arbitrary element of the domain (↑ needed later for step 8)

5.

P (a) → R(a)

2, Universal Instantiation

6.

∼ Q(a) → R(a)

3, Universal Instantiation

7.

R(a)

4, 5, 6, Proof by Division into Cases

8. ∴ ∀x, R(x)

7, Universal Generalization

3

Example: The domain of all variables is D. ∃x such that (C(x)∧ ∼ B(x)) ∀x, (C(x) → P (x)) ∴ ∃x such that (P (x)∧ ∼ B(x))

1.

∃x such that (C(x)∧ ∼ B(x))

Premise

2.

∀x, (C(x) → P (x))

Premise

3.

C(a)∧ ∼ B(a)

1, EI

4.

C(a)

3, Specialization

5.

P (a)

2, 4, Universal Modus Ponens

6.

∼ B(a)

3, Specialization

7.

P (a)∧ ∼ B(a)

5, 6, Conjunction

8. ∴ ∃x such that (P (x)∧ ∼ B(x))

7, EG

4

Example: The domain of all variables is D. ∀x, (P (x) ∨ Q(x)) ∀x, ((∼ P (x) ∧ Q(x)) → R(x)) ∴ ∀x, (∼ R(x) → P (x))

1.

∀x, (P (x) ∨ Q(x))

Premise

2.

∀x, ((∼ P (x) ∧ Q(x)) → R(x))

Premise

3.

∼ R(a)

Assume for Hypothetical Reasoning, a is arbitrary (needed later for step 13)

4.

∼ (∼ P (a) ∧ Q(a))

2, 3, Universal Modus Tollens

5.

∼∼ P (a)∨ ∼ Q(a)

4, De Morgan’s law

6.

P (a)∨ ∼ Q(a)

5, Double Negation

7.

P (a) ∨ Q(a)

1, Universal Instantiation

8.

(P (a) ∨ Q(a)) ∧ (P (a)∨ ∼ Q(a))

6, 7, Conjunction

9.

P (a) ∨ (Q(a)∧ ∼ Q(a))

8, Distributive law

10.

P (a) ∨ c

9, Negation law

11.

P (a)

10, Identity law

∼ R(a) → P (a)

3-11, Hypothetical Reasoning

13. ∴ ∀x, (∼ R(x) → P (x))

12, Universal Generalization

12.

5

Logic and Theoretical Computer Science Reading: Mathematics for Computer Science MIT (2010) Readings Chapter 1.5, Epp 6.4 The problem SAT: Is a given propositional logic statement form satisfiable? • decidable, that is, there is an algorithm that gives a yes/no answer: – compute the truth table – check if there is a T in at least one row • But there are 2n rows in the truth table for a statement form with n variables. – 2100 is a 31 digit number – At 1 microsecond / row, it would take 400 trillion centuries to compute a truth table with 2100 rows • Is there a more efficient algorithm? – No one knows! – SAT plays an important role the theory of NP-completeness – P (polynomial) ⊆ NP (nondeterministic polynomial) – Is P = NP? ($1, 000, 000 prize: Clay Mathematics Institute Cambridge MA) – SAT solvers can solve any NP problem (though not in polynomial time) Another problem: Is a given predicate logic statement satisfiable? • undecidable: there cannot exist an algorithm that gives a yes/no answer. • related to the Entscheidungsproblem: Is a given predicate logic statement true under all interpretations? which was posed by Hilbert in 1928 and shown to be undecidable by Turing and Church in 1936. • related to the halting problem 6

Example: Transforming an instance of exam scheduling to a SAT instance The problem: Given integers n and k, and a set of conflicts: C = {(i, j) | where 1 ≤ i < j ≤ n and exam i cannot be scheduled at the same time as exam j}, can n exams be scheduled in k timeslots such that no conflicting exams are scheduled in the same timeslot? We construct a statement form in propositional logic that is satisfiable if and only if the answer to the exam scheduling problem is yes. There are nk variables: xij where 1 ≤ i ≤ n and 1 ≤ j ≤ k. Variable xij means “Exam i is scheduled in timeslot j.” The statement form is the conjunction of the following subformulas: Each exam is scheduled into a timeslot: x11 ∨ x12 ∨ · · · ∨ x1k x21 ∨ x22 ∨ · · · ∨ x2k .. . xn1 ∨ xn2 ∨ · · · ∨ xnk No exam is scheduled in two timeslots: ∼ (x1i ∧ x1j ) ∼ (x2i ∧ x2j ) for all 1 ≤ i < j ≤ k .. . ∼ (xni ∧ xnj ) No conflicting exams are scheduled in the same timeslot: ∼ (xi1 ∧ xj1 ) ∼ (xi2 ∧ xj2 ) for all (i, j) ∈ C .. . ∼ (xik ∧ xjk )

7