Propositional Calculus - College of Computing & Informatics

Natural Deduction Formal Methods in Verification of Computer Systems Jeremy Johnson Outline 1. An example 1. Validity by truth table 2. Validity by proof 2. Whats a proof 1. Proof checker 3. Rules of natural deduction 4. Provable equivalence 5. Soundness and Completeness An Example If the train arrives late and there are no taxis at the station, then John is late for his meeting. John is not late for his meeting. The train did arrive late. Therefore, there were taxis at the station. If it is raining and Jane does not have here umbrella with her, then she will get wet. Jane is not wet. It is raining. Therefore, Jane has her umbrella with her.

An Example If the train arrives late and there are no taxis at the station, then John is late for his meeting. John is not late for his meeting. The train did arrive late. Therefore, there were taxis at the station. p = the train arrives late q = there are taxis at the station r = John is late for his meeting. [a sequent] An Example p = it is raining q = Jane has her umbrella r = Jane gets wet. If it is raining and Jane does not have here umbrella with her, then she will get wet. Jane is not wet. It is raining. Therefore, Jane has her umbrella with her. Validity by Truth Table p q

r q r pq (pq)r F F F T T F T F F

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

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

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

T T T F F F T Proof By applying rules of inference to a set of formulas, called premises, we derive additional formulas and may infer a conclusion from the premises A sequent is 1,,n Premises 1,,n Conclusion The sequent is valid if a proof for it can be found Proof A proof is a sequence of formulas that are

either premises or follow from the application of a rule to previous formulas Each formula must be labeled by its justification, i.e. the rule that was applied along with pointers to the formulas that the rule was applied to It is relatively straightforward to check to see if a proof is valid Validity by Deduction 1 premise 2 premise 3 premise 4 assumption

5 ,4 6 r 7 e 1,5 e 6,2 8 q 4-7 9 q e8 Rules of Natural Deduction Natural deduction uses a set of rules

formally introduced by Gentzen in 1934 The rules follow a natural way of reasoning about Introduction rules Introduce logical operators from premises Elimination rules Eliminate logical operators from premise producing a conclusion without the operator Conjunction Rules Introduction Rule i Elimination Rule e1

e2 Implication Rules Introduction Rule Assume and show i Elimination Rule (Modus Ponens) e Disjunction Rules Introduction Rule i1 i2

Elimination Rule (proof by case analysis) e Negation Rules Introduce the symbol ( to encode a contradiction Bottom elimination can prove anything e. Elimination Rule

e Negation Rules Introduction Rule leads to a contradiction i Double negation e Proof by Contradiction Derived Rule PBC Assume and derive a a contradiction

Derived rules can be used like the basic rules and serve as a short cut (macro) Sometimes used as a negation elimination rule instead of double negation Law of the Excluded Middle [derived rule LEM] 1 (p p) 2 3 4 5 6 7 8 9 assumption Assumption (p p)

p p p ,4 e 3,1 2-4 ,4 e 6,1 (p p) p p 1-7 e8 ProofLab The ProofLab tool from the Logic and Proofs course from the CMU online learning initiative allows you to experiment with natural deduction proofs ProofLab Provable Equivalence and are provably equivalent, , iff the sequents and are both valid Alternatively iff the sequent

is valid A valid sequent with no premises is a tautology De Morgans Law (P Q) P Q 1 (P Q) 2 3 premise assumption PQ 4 i1 2 e 1,3 5 P

6 Q 7 PQ 2-4 i2 6 8 e 1,7 9 -8 10 P Q i 5,9 De Morgans Law (P Q) P Q

1 P Q premise 2 e1 1 3 e2 1 4 assumption 5 P 6 7 assumption e 2,5

Q i2 6 8 e 3,7 9 e 4,5-6, 7-8 10 (P Q) i 4-9 Semantic Entailment If for all valuations (assignments of variables to truth values) for which all 1, ,n evaluate to true, also evaluates to true then the semantic entailment relation 1,,n holds Soundness and Completeness

1,,n holds iff 1,,n is valid In particular, , a tautology, is valid. I.E. is a tautology iff is provable Soundness you can not prove things that are not true in the truth table sense Completeness you can prove anything that is true in the truth table sense Proof Outline For soundness show, using a truth table, that each rule of inference implies the conclusion is true when the assumptions are true and use induction on the length of the proof to chain together inferences For completeness 1. Reduce to proving tautologies 2. Provide a proof for a sequent for each entry in the truth table for the conclusion using induction on the formula in the conclusion 3. Construct proof from the proofs for each row Illustrate Inductive Proof Prove if p q r p (q r) valid then p q r p (q r) 1 pqr

2 premise assumption 3 q assumption 4 5 pq r 2,3 e 1,5 6 7 qr p (q r)

i 3-5 i 2-6 Smaller Proof Remove last line 1 pqr 2 premise assumption 3 q assumption 4 5 pq r 2,3

e 1,5 6 qr i 3-5 Inductive Hypothesis Remove last line and change assumption to premise to obtain proof of p q r, p q r 1 pqr 2 premise premise 3 q assumption 4

5 pq r 2,3 e 1,5 6 qr i 3-5 By induction p q r, p q r Inductive Step p q r, p q r and correctness of i Implies p q r p (q r) i

F F T F T T T F F T T

T Proof of Soundness Use induction on the length of the proof Base case. When the proof has length 1, premise and conclusion are the same. Clearly the conclusion is T when the premise is T Look at the rule in the last line of the proof Obtain proofs for the premises and use induction hypothesis to show entailment for premises Use correctness of rule and truth of premises to deduce truth of conclusion Correctness of Rules of Inference e

F F F T T F F F

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

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

T T T F F F T T T T T T T Correctness of Rules of Inference

e i F F T T

F T F T F F T F T Induction for Implication Elimination Given a proof of length k for the sequent 1,,n and assume the rule at step k is e and the premise Then we obtain proofs for (replace open assumptions by premises) 1,,n 1 2

1,,n 1,,n Inductive Step Since the proofs are shorter by induction 1,,n1 2 1,,n 1,,n By correctness of the e rule, we conclude 1,,n A similar proof must be carried out for each of the rules of inference Proof of Completeness 1. Reduce to tautologies 1,,n is equivalent to = 1 (2 (n ) ) This follows from (A B) C A (B C) 2. Prove for each row in the truth table for

3. Combine the proofs in (2) using case analysis and the LEM to obtain a proof for the tautology Key Lemma for Proof of Completeness Proposition. Let be a boolean formula with propositional atoms p1, ,pn. Let l be any row in the truth table for . Let be pi if the entry for pi is T and pi if the entry if F. Then is provable if in row l is T is provable if in row l is T Proof of Lemma Use structural induction on the formula Base case. is a propositional atom. In this case the proofs of p and p are trivial. For boolean operators assume proofs for the operands and then construct a proof from them for each of the operators , , and . This is shown for . The other cases are similar. Inductive Step for Implication To prove 1 2 For each entry in the truth table for 1 2

Assume proofs for 1 [ 1 ] and 2 [ 2 ] Prove 1 2 1 2 [1 F, 2 F, 1 2 T] 1 2 1 2 [1 F, 2 T, 1 2 T] 1 2 (1 2) [1 T, 2 F, 1 2 F] 1 2 1 2 [1 T, 2 T, 1 2 T] Inductive Step for Implication 1 2 1 2 1 1 2 2 1 3 1 4 5

6 22 11 22 premise assumption 2,3 e4 i 3-5 Inductive Step for Implication 1 2 1 2 1 1 2 2 1 3 1 4 5

6 22 11 22 premise assumption 2,3 e4 i 3-5 Inductive Step for Implication 1 2 1 2 1 1 2 2 2 3 1 2 premise i 3-5

1 2 (1 2) 1 1 2 2 1 3 2 4 5 (1 2) 22 assumption 4,2 ( (11 22))

3,5 i i 4-6 4-6 6 7 7 premise Combining Proofs Combine proofs for = 1 (2 (n ) ) 1 p1 p1 LEM 2 p1 assumption

p1 assumption 3 p2 p2 LEM p2 p2 LEM 4 p2 p2 p2 p2 5

6 7 e e

8 e

Recently Viewed Presentations

• Deddf Rhentu Cartrefi (Ffioedd ac ati) (Cymru) 2019Renting Homes (Fees etc.) (Wales) Act 2019. Good Evening / Noswaithdda! To begin with, could I please have a show of hands- how many of you are familiar with the code of practice?...
• The Lion Pilot. Created by the Boy Scouts of America to address the needs of kindergarten-age boys . Must be 5 years old by September 30, 2016 and not yet 7 years old to participate
• 5S Seiton Set in order Simplify the arrangement Seiton refers to setting things in order, creating optimal boundaries and locations for each item in a work area. 5S Seiso Shine Sweep Cleanliness Seiso means that every day the work place...
• Planck mass & density at peak. PURUSHA. 2/14/2012. Coherent state . Maximum coherent potential. Perpetual simultaneous interactions. Stresses merge to unity count. Forms 'negative' ground state. Initiates gravitational acceleration. Sum of all odd & even harmonics.
• Every form of poetry has its own structure. Examples may include: * Narrative *Haiku *Free Verse *Lyric *Ballads *Limericks *Concrete. NARRATIVE POETRY *Poetry that tells a story in verse. *Narrative poems have elements similar to those in short stories, such...
• "Cement" including Cement Clinker is a binder; a substance that sets, hardens, and binds upon exposure to moisture. The main risk associated with the carriage of clinker is that the exposed clinker dust will: Dampen, harden and bind to the...
• Arial Symbol Times New Roman Default Design Microsoft Photo Editor 3.0 Photo KaleidaGraph Plot Adobe Photoshop Image Media Clip MathType 5.0 Equation Motivation Energy and Nanotechnology Sources Nano for Energy Nanoscience Research for Energy Needs Examples Thermoelectrics Devices Nanoscale Effects...
• TEESSIDE PENSION FUND Pensionable Pay Pensionable Pay Meaning of pensionable pay Pensionable or not Final pay - general Full time & part time employees Final pay - BIS Last 365 days Reductions & restrictions Certificate of Protections Pre 2008 &...