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

4 is answer of this question

---

i have a doubt here like the order of given propositional formulae to be followed or can be changed like

p and (p->q) can be converted to :

(p->q) and p which consequently results in q as following the modus ponnens could you correct me where I am going wrong !

---

You're going the right way. Q is an answer. But there are other options as well. 
"A implies B" means: in every row where A is true, B is also true. 
Check with P=T, Q=T row, all options other than (i) come out true, so all four are implied.

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

Tysm

---

No p⟹q means p→q is a tautology

---

@SkillIssue how we say p->q means it is tautology? what if 1->0 then its false 

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) ?

---

@jiminparkYes, this is what X => Y means. If Y can be implied from X, then X => Y.

Answer 3

  4 is the answer.

Comments

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

Answer 5

For two propositions A and B , if we can take A as true and derive B as true somehow then we can say A logically implies B $( A \implies B)$

Taking given premise A as true

Now check each option whether it is implied by given premise or not

options B, C, D, E are implied by given premise $P \land \left( P \to Q\right)$ and option A doesn’t imply it

$\therefore$ the count is 4

Comments

the shorter way is to get P and Q values as True, substituting them in the options and checking true or false

---

Upvote for the hardwork.

Answer 6

GIVEN

P->Q

P

________

1.implies Q

2 NOW Q implies P OR Q

3.P IS TRUE so it implies P OR ~Q

4 THIS IS DIFFERENT STILL EASY....P->Q is true ..Q is true and TRUE IS TRUE (trivially)..to understand ..make table of p->T

Answer => 4

Comments

bhai answer bhi bata dete ek bar :) , 0? 1? 2? 3? 4? 5?

---

4 -answer