GATE CSE 2008 | Question: 31

Question

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent?

1. $P ∨ \neg Q$
2. $\neg(\neg P ∧ Q)$
3. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$
4. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$

• A. Only I and II
• B. Only I, II and III
• C. Only I, II and IV
• D. All of I, II, III and IV

Comments

Answer could be obtained via checking minimized SOP form.

---

option 1 and 2 can be easily seen that they are equivalent.

Option III- PQ+P(~Q)+(~P)(~Q)=P(Q+(~Q))+(~P)(~Q)=P+(~P)(~Q)

→   P+(~P)(~Q)=(P+(~P))+(P+~Q)=P+(~Q).

Option IV-Proceed same as in Option III.

---

To solve faster prefer solving using the case method.

Answer 1

Just Use digital Logic Concept.

convert V → + and ^ → .

So whose answer is P + Q’.

They are matched :)

Answer 2

The first two options are straightforward.

ie (q--->p)

now, the easiest way is check the condition of implication in (iii)option.

ie if Q is true , p has to be true . If Q is false, P Can be anything.

that’s exactly what is (iii) option.

Now, in 4th option.If Q is true p can be either true or false. Hence, 4th option is not equivalent to the remaining.

Answer: (i) , (ii), (iii) are equivalent.

Answer 3

The correct option is B 
1. P ∨∼Q≡P+Q′

2. ∼(∼P∧Q)≡(P′Q)′≡P+Q′

3. (P∧Q)∨(P ∧∼Q)∨(∼P ∧∼Q)
≡PQ+PQ′+P′Q′
≡P(Q+Q′)+P′Q′
≡P+P′Q′
≡(P+P′)(P+Q′)
≡p+Q′

4. (P∧Q)∨(P∧∼Q)∨(∼P∧Q)
≡PQ+PQ′+P′Q
≡P(Q+Q′)+P′Q
≡P+P′Q
≡(P+P′)(P+Q)=P+Q

Clearly (i), (ii) and (iii) are equivalent.

so Correct choice is (b).