Discrete Mathematics | Propositional Logic | Test 2 | Question: 10

Question

 Premises $P_1,P_2,...,P_n$ infer/derive a conclusion $Q$ if and only if the conditional $(P_1 \wedge P_2 \wedge...\wedge P_n) \rightarrow Q$ is a tautology.      
        
Consider the following statements:     

1. From $P$ and $P \rightarrow Q$ we may infer $Q$      
2. From $P$ and $P \rightarrow (Q \vee R)$ we may infer $Q \vee R$       
3. From $\neg Q$ and $P \rightarrow Q$ we may derive $\neg P$   

iv. From $\neg P$ and $P \vee Q$ we may derive $Q$    
v.  From $(P \wedge Q) \rightarrow R$ we may derive $P \rightarrow (Q \rightarrow R)$     
vi. From $P \rightarrow (Q \rightarrow R)$ we may derive  $(P \wedge Q) \rightarrow R$    
vii. From $P$ we may derive $(P \wedge Q)$     
viii. From $P \rightarrow R$ and $Q \rightarrow R$  we may derive $(P \rightarrow (Q \wedge R))$     
ix. From $P \rightarrow R$ and $Q \rightarrow R$  we may derive $((P \vee Q) \rightarrow R)$      
($P$, $Q$ and $R$ are distinct atomic sentences )     
     
Number of correct statements are ______

Answer 1

1. (P $\wedge$ (P → Q)) → Q  :- Modus ponens
2. (P $\wedge$ (P → (Q V R))) → (Q V R)  :- Modus ponens
3. (Q’ $\wedge$ (P → Q)) → P’  :- Modus tolens
4. (P’ $\wedge$ (P V Q)) → Q  $\equiv$ (P’ $\wedge$ Q) → Q $\equiv$ P + Q’ + Q $\equiv$ True. Tautology. So, valid argument.
5. (P $\wedge$ Q) → R $\equiv$ (P $\wedge$ Q)’ + R $\equiv$ P’ + Q’ + R
   P → (Q → R) $\equiv$ P’ + (Q → R) $\equiv$ P’ + Q’ + R
   ((P $\wedge$ Q) → R) → (P → (Q → R)) $\equiv$ (P’ + Q’ + R) → (P’ + Q’ + R) $\equiv$ True. Tautology. So, valid argument.
6. (P → (Q → R)) → ((P $\wedge$ Q) → R) $\equiv$ (P’ + Q’ + R) → (P’ + Q’ + R) $\equiv$ True. Tautology. So, valid argument.
7. P → (P $\wedge$ Q) $\equiv$ P’ + PQ $\equiv$ P’ + Q. Here if P is true and Q is false, then P’+Q is false. Not Tautology. So, invalid argument.
8. ((P → R) $\wedge$ (Q → R)) → (P → (Q $\wedge$ R)) $\equiv$ ((P’+R)$\wedge$(Q’+R)) → (P’ + (Q $\wedge$ R)) $\equiv$ (P’Q’ + R) → (P’ + QR) $\equiv$ PR’ + QR’ + P’ + QR $\equiv$ R’+Q+P’. Not Tautology. So, invalid argument.
   (Another approach)
   Valid Argument :- If all the premises are true, then the conclusion must be true. If it is possible to make all the premises true and the conclusion false, then the argument is invalid. But if it is impossible to make all the premises true and the conclusion false, then the argument is valid.
   Let’s take conclusion as false and try to make all the premises true.
   Conclusion is false => (P → (Q $\wedge$ R)) $\equiv$ False => P is true and (Q $\wedge$ R) is false.
   1^st Premise is true => (P → R) $\equiv$ true => R is true (because P is true) => Q is false (because Q is false).
   2^nd Premise is true => (Q → R) $\equiv$ true (possible because Q is false and R is false)
   So, it is possible to make all the premises true and the conclusion false. Therefore the argument is invalid.
9. ((P → R) $\wedge$ (Q → R)) → ((P V Q) → R)
   Let’s try 2^nd approach. Let’s take conclusion as false and try to make all the premises true.
   Conclusion is false => ((P V Q) → R) $\equiv$ False => (PVQ) is true and R is false.
   1st Premise is true => (P → R) $\equiv$ true => P is false (because R is false) => Q is true (because (PVQ) is true).
   2nd Premise is true => (Q → R) $\equiv$ true => Impossible because Q is true and R is false. So, (Q → R) is false.
   So, it is impossible to make all the premises true and the conclusion false. Therefore the argument is valid.

Comments

4 stands for Modus tollendo ponens (Latin name)

5 stands for Law of Exportation

6 stands for Law of Importation