edited by
8,283 views
30 votes
30 votes

$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)$
  1. Only I and II
  2. Only I, II and III
  3. Only I, II and IV
  4. All of I, II, III and IV
edited by

7 Answers

Best answer
37 votes
37 votes

I and II are present in all options so need to check.

For III and IV

$(P∧Q)∨(P∧\neg Q) \equiv P∧(Q \vee\neg Q)$  (By distributive law)
$\quad \quad \equiv P∧T$
$\quad \quad \equiv P$

For III.

$P∨( \neg P∧\neg Q) \equiv P\vee \neg Q$ (By Absorption Law)

For IV.

$P∨(¬P∧Q) \equiv P∨Q$ (By Absorption Law)

So Option B is correct.

I, II, III are logically equivalent. 

edited by
16 votes
16 votes
(B) Only I, II and III. Draw truth table to check, evaluating individual expression will consume lot of time with no guaranteed answer.
13 votes
13 votes

answer B

I. ∨ ~Q
II. ~ ( ~∧ Q) apply De Morgan's law. we get  ∨ ~Q
III. (∧ Q) ∨ (∧~ Q) ∨ ( ~∧ ~Q)

=[(∧ Q) ∨ (∧ ~Q)] ∨ ( ~∧ ~Q)

=[P(Q V ~Q)] ∨ ( ~∧ ~Q)

=P ∨ ( ~∧ ~Q)

∨ ~Q
 

edited by
6 votes
6 votes
$$Option\ B\ is\ correct$$

writing in digital like boolean algebra is much faster

1st $p+q'$

2nd $(p'.q)'=p+q'$

3rd is (P∧Q)∨(P∧¬Q)∨(¬P∧¬Q) which is also
$p.q+p.q'+p'q'$

$=(p.q+p.q')+(p.q'+p'q')$        //A+A=A
=$p+q'$

write 4th similarly is $p+q$ i.e. not equivalent to 1st, 2nd and 3rd.
Answer:

Related questions

3 votes
3 votes
3 answers
1
ParthPratim asked Nov 3, 2022
967 views
I have been trying to solve the question GATE CSE 2008 Question.Are the following two representations logically equivalent ?$\beta \rightarrow (\exists x, \alpha (x))$$\e...
70 votes
70 votes
5 answers
2
Kathleen asked Sep 12, 2014
13,842 views
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown autom...