1 CmSc 175 Discrete Mathematics Lesson 04: Valid and Invalid Arguments. Syllogisms 1. Definitions Definition: An argument is a sequence of statements, ending in a conclusion. All the statements but the final one (the conclusion) are called premises(or assumptions, hypotheses) Verbal form of an argument: (1) If Socrates is a human being then Socrates is mortal. (2) Socrates is a human being Therefore (3) Socrates is mortal Here (1) and (2) are the assumptions, and (3) is the conclusion. Abstract (logical) form of an argument - using variables: (1) If P then Q (2) P Therefore (3) Q Another way to write the above argument: P → Q P  Q Definition: A logical argument is valid, if the conclusion is true whenever the assumptions are true. An argument is invalid if it is not valid. 2. Testing an argument for its validity Three ways to test an argument for validity: A. Critical rows 1. Identify the assumptions and the conclusion and assign variables to them. 2. Construct a truth table showing all possible truth values of the assumptions and the conclusion. 3. Find the critical rows - rows in which all assumptions are true 4. For each critical row determine whether the conclusion is also true. a. If the conclusion is true in all critical rows, then the argument is valid b. If there is at least one row where the assumptions are true, but the conclusion is false, then the argument is invalid2 B. Using tautologies The argument is true if the conclusion is true whenever the assumptions are true. This means: If all assumptions are true, then the conclusion is true. "All assumptions" means the conjunction of all the assumptions. Thus, let A1, A2, … An be the assumptions, and B - the conclusion. For the argument to be valid, the statement If (A1 Λ A2 Λ… Λ An) then B must be a tautology - true for all assignments of values to its variables, i.e. its column in the truth table must contain only T i.e. (A1 Λ A2 Λ… Λ An) → B ≡ T C. Using contradictions If the argument is valid, then we have (A1 Λ A2 Λ… Λ An) → B ≡ T This means that the negation of (A1 Λ A2 Λ… Λ An) → B should be a contradiction - containing only F in its truth table In order to find the negation we have first to represent the conditional statement as a disjunction and then to apply the laws of De Morgan (A1 Λ A2 Λ… Λ An) → B ≡ ~( A1 Λ A2 Λ… Λ An) V B ≡ ~A1 V ~A2 V …. V ~An V B. The negation is: ~((A1 Λ A2 Λ… Λ An) → B) ≡ ~(~A1 V ~A2 V …. V ~An V B) ≡ A1 Λ A2 Λ …. Λ An Λ ~B The argument is valid if A1 Λ A2 Λ …. Λ An Λ ~B ≡ F There are two ways to show that a logical form is a tautology or a contradiction: a. by constructing the truth table b. by logical transformations applying the logical equivalences (logical identities)3 Examples: 1. Consider the argument: P → Q P  Q Testing its validity: a. by examining the truth table: P Q P→ Q ---------------------------- T T T T F F F T T F F T There is only one critical row - the first one, where both the premises ( P and P→ Q) are true. In that row the value of Q is true, hence the argument is a valid argument. b. By showing that the statement 'If all premises then the conclusion" is a tautology: The premises are P and P→ Q. The statement to be considered is: (P Λ (P→ Q)) → Q We shall show that it is a tautology by using the following identity laws: (1) P→ Q ≡ ~P V Q (2) (P V Q) V R ≡ P V (Q V R) commutative laws (P Λ Q ) Λ R ≡ P Λ (Q Λ R) (3) (P Λ Q) V R ≡ (P V R) Λ (Q V R) distributive law (4) P Λ ~P ≡ F (5) P V ~P ≡ T (6) P V F ≡ P (7) P V T ≡ T (8) P Λ T ≡ P (9) P Λ F ≡ F (10) ~(P Λ Q) ≡ ~P V ~Q De Morgan's Laws4 (P Λ (P→ Q)) → Q by (1) ≡ ~(P Λ (P→ Q)) V Q by (10) ≡ ( ~P V ~(P→ Q) ) V Q by (1) ≡ ( ~P V ~(~P V Q)) V Q by (10) ≡ (~P V (P Λ ~Q)) V Q by (3) ≡ ((~P V P) Λ (~P V ~Q)) V Q by (5) ≡ (T Λ (~P V ~Q)) V Q by (8) ≡ (~P V ~Q) V Q by (2) ≡ ~P V (~Q V Q) by (5) ≡ ~P V T by(7) ≡ T c. We can prove the argument also by showing that the negation of the conclusion and the assumptions are contradictory, i.e. the conjunction of all assumptions and the negation of the conclusion is a contradiction: (P Λ (P→ Q)) Λ ~ Q by (1) ≡ (P Λ (~P V Q)) Λ ~ Q by (3) ≡ ((P Λ ~P) V (P Λ Q)) Λ ~ Q by (4) ≡ (F V (P Λ Q)) Λ ~ Q by (6) ≡ (P Λ Q) Λ ~ Q by (2) ≡ P Λ (Q Λ ~ Q) by (4) ≡ P Λ F by (9) ≡ F Crucial fact about a valid argument: the truth of its conclusion follows necessarily from the logical form alone and the truth of the assumptions5 Thus in the argument (1) If P then Q (2) P Therefore (3) Q Q is true whenever (1) and (2) are true, no matter what is the nature of the statements P and Q. 2. Consider the argument P → Q Q  P We shall show that this argument is invalid by examining the truth tables of the assumptions and the conclusion. The critical rows are in boldface. P Q P→ Q ---------------------------- T T T T F F F T T here the assumptions are true, however the conclusion is false F F T Exercise: Show the validity of the argument: 1. P V Q (premise) 2. ~Q (premise) Therefore P (conclusion) a. by using critical rows b. by contradiction using logical identities6 Solution: a. by critical rows conclusion Premises P Q P V Q ~Q T T T F T F T T Critical row F T T F F F F T b. By contradiction using identities ((P V Q) Λ ~Q ) Λ ~P ≡ ((P Λ ~Q ) V (Q Λ ~Q )) Λ ~P ≡ ((P Λ ~Q ) V F) Λ ~P ≡ (P Λ ~Q ) Λ ~P ≡ P Λ ~P Λ ~Q ≡ F Λ ~Q ≡ F7 Syllogisms (patterns of arguments, inference rules) Aristotle (384 – 322 B.C) was the first to study patterns of arguments, …