Analysis of Arguments and Logic - Study Guide | MATH 124, Study notes of Mathematics

Download Analysis of Arguments and Logic - Study Guide | MATH 124 and more Study notes Mathematics in PDF only on Docsity! M124 – Logic Lecture 5 • Analysis of arguments – Logical consequence – Rules of inference – Rules of equivalence – Formal proof of arguments Logical Consequence • Let Φ be a set of formulae and f a formula – f is a logical consequence of Φ if for any assignment of truth values to atomic propositions for which all of the members of Φ true, f is also true – If f is a logical consequence of Φ, write Φ⊨f – Note: this is consistent with ⊨f when f is a tautology • This is important! It is the basis of formalisation of arguments Notation • An intuitive way to write an argument with a set of hypotheses Φ and conclusion f is as follows: Φ --- ∴f hypotheses conclusion Example 1 • Suppose Φ = {p, p⇒q, q ⇒r}, f = p ∧ q ∧ r • Then the corresponding argument can be written: p p⇒q q ⇒r ------------ ∴ p∧q ∧r Assume that p is true, p⇒q is true, and q⇒r is true. Then p and q and r are all true. Example 1 (continued) • Test validity of argument using truth table: p q r p p⇒q q⇒r p∧q∧r T T T T T T T T T F T T F F T F T T F T F T F F T F T F F T T F T T F F T F F T F F F F T F T T F F F F F T T F Example 2 (continued) • Test validity of argument using truth table: p q r p⇒q q⇒r r p T T T T T T T T T F T F F T T F T F T T T T F F F T F T F T T T T T F F T F T F F F F F T T T T F F F F T T F F Example 2 (continued) p q r p⇒q q⇒r r p T T T T T T T T T F T F F T T F T F T T T T F F F T F T F T T T T T F F T F T F F F F F T T T T F F F F T T F F In this row all hypotheses are true. But the conclusion is false Therefore argument is not valid Proofs in Propositional Logic • In mathematics, a proof is a sequence of steps, each of which is: – Self-evident (or axiomatic), or – An explicitly stated assumption (or hypothesis), or – Deduced from previous steps using rules of inference Rules of inference • Rules of inference are simple arguments which can be validated using truth tables • For more complex arguments, involving many propositions, use of truth tables is not practical • Complex arguments are validated via formal proofs, using simpler arguments which are known to be valid already Review of the last lecture • Valid arguments – An argument is valid if its conclusion is a logical consequence of its assumptions • The simplest way to prove that an argument is valid is to use a truth table – For any assignment of T and F to the elementary propositions in the assumptions and conclusion, if all assumptions are true then the conclusion must be true Review of last lecture • Problems: – If the number of elementary propositions is large then the number of rows in the truth table will be very large – If the formulae are complex, then the number of columns in the truth table will be large • So, try to show that more complex arguments are valid using formal proofs Example rules of inference • Law of Detachment: • Syllogism: p⇒q p ------- ∴ q p⇒q q ⇒r ------- ∴ p ⇒r Proof using truth tables p q p⇒q p q T T T T T T F F T F F T T F T F F T F F p q r p⇒q q⇒r p⇒r T T T T T T T T F T F F T F T F T T T F F F T F F T T T T T F T F T F T F F T T T T F F F T T T More rules of inference • Modus Tollens: • Addition: p⇒q ¬q ------- ∴ ¬ p p ------- ∴ p∨q More rules of inference • Reductio ad Absurdum: • We’ll see later that this is also known as ‘Proof by Contradiction’ ¬p⇒(r∧¬r) --------------- ∴ p Basically, this says that if q implies both r and ¬r, then q must be false The symbol ≡ • Recall that the symbol ≡ means logical equivalence • Recall that if f and g are both formulae involving the elementary propositions p1,…,pN, then f ≡ g if and only if f and g have the same truth table. • So, in principle the simplest way to show that two formulae are logically equivalent is to construct their truth tables and show that they are the same Standard equivalences • Using this method we can establish a set of standard equivalences which we can use later in proofs • Suppose p, q and r are elementary propositions: • Commutative Laws: – p ∧ q ≡ q ∧ p – p ∨ q ≡ q ∨ p Example proof p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p q r (p ∨ (q ∧ r)) ((p ∨ q) ∧ (p ∨ r)) T T T T T T T T T T T T T T T T T F T T T F F T T T T T T F T F T T T F F T T T F T T T T T F F T T F F F T T F T T T F F T T F T T T T F T T T F T T F T F F F T F F F T T F F F F F F T F F F F T F F F F F T T F F F F F F F F F F F F F T F More standard equivalences • Law of double negation: – ¬¬p ≡ p • Equivalence of contrapositive: – p ⇒ q ≡ ¬q ⇒ ¬p • Another useful equivalence: – p ⇒ q ≡ ¬p ∨ q – p ∨ ¬p is a tautology – p ∧ ¬p is a contradiction Definition of proof • A proof that a formula f is a logical consequence of a set of assumptions Φ is a sequence of statements, ending with f, each of which is: – True by assumption (i.e. in Φ), or – An axiom or definition, or – A previous theorem, or – A statement implied by previous statements by a rule of deduction, or – Logically equivalent to a previous statement Example proof 2 • Show that: is a valid argument p ∨ q q ⇒ r p ⇒ s ------- ∴ r ∨ s Intuitively, if p ∨ q is assumed true, then either p or q must be true (or both). If p is true and p ⇒ s is true, then s must be true. If q is true and q ⇒ r is true, then r must be true. Hence r or s must be true (or both) Example proof 2 • Where do we start? – The assumptions combine the ∨ and ⇒ connectives – These are related by p ⇒ q ≡ ¬p ∨ q – Also ¬¬p ≡ p, so ¬p ⇒ q ≡ p ∨ q – So, conclusion can be written ¬r ⇒ s ≡ r ∨ s – So, can we get ¬r ⇒ ¬q ⇒ p ⇒ s ? Example proof 2 (continued) 1. p ∨ q (given) 2. q ⇒ r (given) 3. p ⇒ s (given) 4. ¬r ⇒ ¬q (2 and Equiv. of contrapositive) 5. q ∨ p (1 and commutativity) 6. ¬ ¬q ∨ p (5 and law of double negation) 7. ¬q ⇒ p (6 and standard equivalence) 8. ¬r ⇒ s (4, 7 & 3 and syllogism) 9. r ∨ s (8 and standard equivalence) Completeness Theorem for Propositional Logic • If Φ is a set of formulae in Propositional Logic, and f is a formula in Propositional Logic, then Φ⊨f if and only if Φ⊢f f is a logical consequence of Φ if and only if f is provable from Φ Summary • Formal proof in propositional logic – Rules of inference – Rules of equivalence – Example proofs