The Gateway to Computer Science Excellence
+22 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 (17.5k points)
edited by | 1.8k views

2 Answers

+32 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 (431k 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).

+4 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 (12.9k 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,737 questions
57,309 answers
105,019 users