search
Log In
22 votes
2.2k views

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
edited by
2.2k views

2 Answers

33 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.

edited by
0
Good Explanations sir
6
When in confusion, better to use truth table, surely to give correct answer
0
how to find out if reverse implication is not true? nevermind I understood
0

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

0
why option A is wrong ?
1

$X\equiv(P∨Q)→R$

$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(P→R)∨(Q→R)$

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

$Y\equiv\bar{P}+R+\bar{Q}+R$

$Y\equiv\bar{P}+\bar{Q}+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..

Answer:

Related questions

29 votes
2 answers
1
4.2k views
What is the first order predicate calculus statement equivalent to the following? "Every teacher is liked by some student" $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$ ...
asked Sep 21, 2014 in Mathematical Logic gatecse 4.2k views
0 votes
0 answers
2
16 views
Find a counterexample, if possible ,to these universally quantified statements, where the domain for all variables consists of all integers. $\forall x \exists y (x=1/y)$ $\forall x \exists y (y^2 -x <100)$ $\forall x \forall y (x^2 \neq y^3)$
asked Mar 19, 2019 in Mathematical Logic Pooja Khatri 16 views
0 votes
0 answers
3
34 views
Express each of these system specifications using predicates, quantifiers, and logical connectives. When there is less than 30 megabytes free on the hard disk, a warning message is sent to all users. No directories in the file system can be opened and no files can ... be delivered when there are at least 8 megabytes of memory available and the connection speed is at least 56 kilobits per second.
asked Mar 18, 2019 in Mathematical Logic Pooja Khatri 34 views
23 votes
2 answers
4
4.3k views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. ... to $7$ Precedence of $+$' is higher than that of $\times$', and both operators are left associative; expression is evaluated to $9$
asked Nov 27, 2016 in Compiler Design jothee 4.3k views
...