GATE CSE 2016 Set 2 | Question: 01

Question

Consider the following expressions:

1. $false$
2. $Q$
3. $true$
4. $P\vee Q$
5. $\neg Q\vee P$

The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.

Comments

how v?

---

$(P \;\wedge (P\Rightarrow Q))\Rightarrow ( Q' \vee P)$ resulting in tautology. I am not sure this way is correct.

---

4 statements are correct because logic implication means my conclusion follows from my arguments,so arguments--> conclusion is a tautology. so except i) all are tautologies,if u simplify it.

---

Logically implied means if P ˄ (P→ Q) is True then the conclusion must be true. Suppose  P ˄ (P→ Q) is true then P,Q both must be true. So conclusion can be Q, P V Q, ~Q V P, True. So 4 expressions can be logically implied. If False is the conclusion then P ˄ (P→ Q)→ False results in False(or invalid).

Answer 1

$4$ should be the correct answer.$$\begin{array}{|l|l|l|l|} \hline \textbf{P} & \textbf{Q} & \textbf{P} \implies \textbf{Q} & \textbf{P} \wedge ( \textbf{P} \implies \textbf{Q}) \\\hline \text{F} & \text{F} & \text{T} & \text{F} \\\hline \text{F} & \text{T} & \text{T} & \text{F} \\\hline \text{T} & \text{F} & \text{F} & \text{F} \\\hline \text{T} & \text{T} & \text{T} & \text{T} \\\hline \end{array}$$

Suppose $\left(P\wedge(P\implies Q)\right)\iff A$ (For notational convenience)

Thus for options, $(i),(ii),(iii),(iv),(v)$
If $(A\implies \text{option x})$ is a tautology.
then $P\wedge(P\implies Q)$ logically implies $\text{option x}$
else $P\wedge(P\implies Q)$ does not logically implies $\text{option x.}$

$$\small{\begin{array}{|c|c|c|cc|cc|cc|cc|cc|} \hline \textbf {P}& \ \textbf {Q} &\ \textbf{A}&\rlap{\textbf{Option(i)} }&& \rlap{\textbf{Option(ii)}}& &\rlap{\bf{Option(iii)} }&& \rlap{\bf {Option(iv)}}&& \rlap{\bf{Option(v)}} \\\hline &&& \text{False}&A \Rightarrow F & \text{Q}&A \Rightarrow Q&\text{True}&A\Rightarrow true&(P \vee Q)&A \Rightarrow (P \vee Q)&\neg Q \vee P&A \Rightarrow  (\neg Q \vee P))\\\hline F&F&F& & T && T && T && T && T\\\hline F & T & F && T & &T &&T &&T&&T \\\hline T & F & F && T & &T &&T &&T&&T \\\hline T & T & T &F& F & T&T &T&T &T&T&T&T \\\hline \end{array}}$$

Answer $=4$

P.S: Blank entries in the above truth table are like don't care conditions because in those rows the value of $A$ is set to False. Hence, $(A\implies \text{Anything})$ would be set to True.

Comments

What’s the difference between $\Rightarrow and \rightarrow$

Please someone comment the answer

---

They are the same @mani312

---

Tysm

Answer 2

Without making truth table we can solve very easily

P˄(P->Q)

=P˄(~P˅Q)

=(P˄~P)˅(P˄Q)

=P˄Q

Now Check these implications whether they are right or wrong.For checking try T -> F combination if any of them generate this combination then it will be ruled out. If you see carefully  1.P˄Q -> FALSE will ruled out

1.P˄Q->FALSE

2.P˄Q->Q

3.P˄Q->TRUE

4.P˄Q->P˅Q

5.P˄Q->~Q˅P

so answer is 4

Comments

@vnc I also thought the same way of solving given expression without truth table and also got :  P ^ Q

but after that what to do ? how and what  to check???? I did not get the question

---

@shweta after calculation of p^Q you calculate (p^Q) -> false is a tautology or You can also search that if LHS(P^Q) is True then R will not be false because that is the only condition when implied is false.

---

@shweta1920, I did the same thing. I was trying to search if anything among the given expression is equivalent to P^Q ; which is wrong!

I just want to ask:

if X → Y ; ( If Y can be logically implied from X) then does this mean ( X → Y = TRUE) ?

Answer 3

  4 is the answer.

Answer 4

ans :4

all except the option i satisfies.

P and Q -> true, P or Q,~Q or P,Q

Comments

yes. 4 is the answer - unless I miss something..

---

The point is p^(p->q) is implied q by using modus ponens but not equivalent to q.

p^(p->q) equivalent to (p^q)  so by simplification rules both p,q are true.Hence (~qvp ) is also true.

---

A proposition can be true or false, but true / false, taken alone, are not propositions.

Literal True IS a proposition that is always True.So we can imply it just like we imply any other proposition.