The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

Let $P, Q$ and $R$ be three atomic propositional assertions. Let $X$ denote $( P ∨ Q ) → R$ and Y denote $(P → R) ∨ (Q → R).$ Which one of the following is a tautology?

  1. $X ≡ Y$
  2. $X → Y$
  3. $Y → X$
  4. $¬Y → X$
in Mathematical Logic by Boss (16.3k points)
edited by | 1.6k views

2 Answers

+29 votes
Best answer
$X \equiv (P \vee Q) → R$
$\quad \equiv \neg(P \vee Q) \vee R$
$\quad \equiv (\neg P \wedge \neg Q) \vee R$
$\quad \equiv (\neg P \vee R) \wedge (\neg Q \vee R)$
$\quad \equiv (P →  R) \wedge (Q → R)$

So, $X  → Y$ is true as $(A \wedge B) → (A \vee B)$ is always TRUE but reverse implication is not always true.

Hence, B.
by Veteran (421k points)
edited by
Good Explanations sir
When in confusion, better to use truth table, surely to give correct answer
how to find out if reverse implication is not true? nevermind I understood

A→B is implication and B→ A is the reverse implication, in the same way, u can check that...

why option A is wrong ?


$X\equiv\lnot(P∨Q)\vee R$

$X\equiv (\lnot P \wedge \lnot Q)\vee R$

$X\equiv \bar{P}.\bar{Q}+R$


$Y\equiv(\lnot P\vee R)∨(\lnot Q\vee R)$



How $X \equiv Y$ gives always true?

It is not possible to $X \equiv Y$ gives always true(Tautology).

+2 votes

A good explanation is already given by arjun sir. I'm going to share my approach- (using rules of boolean algebra, checking options one by one)

$X=(P\vee Q)\rightarrow r$

     $=\overline{p+q} +R$

     $=\bar{P}• \bar{Q} +R$

$Y=(P\rightarrow R) \vee (Q\rightarrow R)$

    $=(\bar{P} + R) + (\bar Q +R)$

    $=\bar P +\bar Q + R$

A. Clearly $X\;\text {not}\equiv Y$

B. X$\rightarrow$Y $=\bar X+Y$

     $=(\overline{\bar P \bar Q+R}) + (\bar P +\bar Q + R)$

     $=(P+Q) \color{green}{\bar R }\; +(\bar P +\bar Q)+ \color{green}R$

     $=(P+Q+R)(\bar R+R)+(\bar P+\bar Q)$

     $=(P+Q+R)+(\bar P+\bar Q)$

     $=1\;(TRUE)$  So option B is correct..

by Boss (10.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,376 questions
55,840 answers
91,403 users