GATE CSE 2006 | Question: 27

Question

Consider the following propositional statements:

• $P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$
• $P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$

Which one of the following is true?

• A. $P_1$ is a tautology, but not $P_2$
• B. $P_2$ is a tautology, but not $P_1$
• C. $P_1$ and $P_2$ are both tautologies
• D. Both $P_1$ and $P_2$ are not tautologies

Comments

sorry got it actually iam doing left side for second statement also And bymistakenly they both are not equivalent so not tautology

---

Simplification is fastest way

---

Put some value and check  P1 and P2

Both are not tautologies
Option D is correct

Answer 1

(D) Both $P_1$ and $P_2$ are not tautologies.

$P_1:$ If $A$ is true and $B$ is false, LHS of $P_1$ is true but RHS becomes false. Hence not tautology.

$P_2:$ Forward side is true. But reverse side is not true. When $A$ is false and $B$ is true and C is false, RHS is true but LHS is false.

LHS of $P_2$ can be simplified as follows:

$((A∨B) → C) \equiv (~(A∨B) ∨ C)$
$\quad \quad \equiv (~A ∧~B) ∨C)$
$\quad \quad \equiv (~A ∨C) ∧ (~B ∨C)$
$\quad \quad \equiv (A→C) ∧ (B→C)$

Comments

 

LHS of 𝑃2 can be simplified as follows:
((𝐴∨𝐵)→𝐶)≡( (𝐴∨𝐵)∨𝐶)

@Arjun sir it will be ≡( (𝐴'∧𝐵')∨𝐶) 

 

---

Just for confusion.

---

Korchum koodi conceptual clarity thannoode..(like to solve it using by case method with C)...only for genius answer aanallo

Answer 2

$P_1 : \underbrace{((A \land B) \to C)}_{\alpha} \equiv \underbrace{((A \to C) \land (B \to C))}_{\beta}$

$\underline{\text{Case I}}: C = \top$

$\alpha : (A \land B) \rightarrow T \\$

$\quad = T \\$

$\beta : (A \rightarrow T) \land (B \rightarrow T) \\$

$\quad= T \land T\\$

$\quad = T$

$\boxed{\textcolor{green}{\alpha \equiv \beta}} $

$\underline{\text{Case II}}: C = F$

$\alpha : (A \land B) \rightarrow F \\$

$\quad = \neg (A \land B) \\$

$\beta : (A \rightarrow F) \land (B \rightarrow F) \\$

$\quad= \neg A \land \neg B$

$\boxed{\textcolor{red}{\alpha \not\equiv \beta}} $

Hence $P_1$ is not tautology.

---

Now consider,

$P_2 : \underbrace{((A \lor B) \to C)}_{\alpha} \equiv \underbrace{((A \to C) \lor (B \to C))}_{\beta}$

$\underline{\text{Case I}}: C = \top$

$\alpha : (A \lor B) \rightarrow T \\$

$\quad = T \\$

$\beta : (A \rightarrow T) \lor (B \rightarrow T) \\$

$\quad= T \lor T\\$

$\quad = T$

$\boxed{\textcolor{green}{\alpha \equiv \beta}} $

$\underline{\text{Case II}}: C = F$

$\alpha : (A \lor B) \rightarrow F \\$

$\quad = \neg (A \lor B) \\$

$\beta : (A \rightarrow F) \lor (B \rightarrow F) \\$

$\quad= \neg A \lor \neg B$

$\boxed{\textcolor{red}{\alpha \not\equiv \beta}} $

Hence $P_2$ is not tautology.

---

Answer: D

Comments

@gopal_gate Best Approach to solve this Question thanks.

Answer 3

Answer is "D" for this question

but what if we exchange in right side of P1 & P2 let's see what happen

P1 : ((A ∧ B) → C)) ≡ ((A → C) ∨ (B → C))       
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∧ (B → C)) 

P1: ~A +~B +C  ≡ ~A +~B+C   

P2:  ~A~B + C ≡(~A+C)(~B+C)     // Here we know that C+~A~B = (C+~A)(C+~B)

 P1 and P2 are both not tautologies here

Comments

@Prateek kumar option (D) says they are not tautologies, correct the final statement. 

---

“but what if we exchange in right side of P1 & P2”

Prateek has given proof after changing RHS. For that both will be tautologies.

Answer 4

So, P1 and P2 are both not tautologies here

Answer 5

Checking by algebraic manipulation: