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

Let first understand the question it says that we need to find the expression which are logically implied by (P $\wedge$  (P $\rightarrow$ Q) ) 

Now this can also be said as what are the proposition formula among the followings which are TAUTOLOGY. (So we will find this and one note if something is given as X INFER Y (OR)  X |= Y (OR) X$\rightarrow$Y this all say that Y is logically implied by X.

1.  (P $\wedge$ ( P $\rightarrow$ Q) ) $\rightarrow$ False 
   Now to prove wheather it is taotology or not in Implication we can just try to make T$\rightarrow$F if it is possible then you can say it is not tautogy
   Now here on right side of implication we have False already now can we make T at left side yes by putting P=T and Q=T. 
   Hence we this is false
2.  (P $\wedge$ ( P $\rightarrow$ Q) ) $\rightarrow$ Q 
   now let try to make T$\rightarrow$F . Hence Q=F now lets try to make left of implication as true as we have and logical connective all should be true for resultant to be true hence P=T but P$\rightarrow$Q = T$\rightarrow$F which is not TRUE hence on left side we got F if we set right side as F hence It is tautology
3.  (P $\wedge$ ( P $\rightarrow$ Q) ) $\rightarrow$ True
   Now here as right of implication is true hence you can never make it false hence it is tautology always
4.  (P $\wedge$ ( P $\rightarrow$ Q) ) $\rightarrow$ (P $\vee$ Q) 
   Now let make (P $\vee$ Q)=F Hence P=F and Q=F now let try to make left of implication true  but it is not possible as it will be (F $\wedge$ (T $\rightarrow$ F)) which is false hence tautology
5. (P $\wedge$ ( P $\rightarrow$ Q) ) $\rightarrow$ ($\bar{Q}$ $\vee$ P) 
   to make right of implication as false Q=T and P=F now try to make left as true but we cant make it as left will look like (F $\wedge$ ( F $\rightarrow$ T) )  which is false hence it is tautology.

Hence we have 4 number of expression which can be said as logically Implied by (P $\wedge$ ( P $\rightarrow$ Q) )

Answer 2

The correct option is  4

p∧(p⇒q)=p(p′+q)≡pq
Take (i) false
pq⇒ false ≡pq⇒0
≡(pq)′+0
≡p′+q′+0
≡ not valid
Take (ii)
pq⇒ q ≡(pq)′+q
≡(pq)′+q
≡p′+1+≡1
≡ valid
Take (iii)
pq⇒ true ≡pq⇒1
≡(pq)′+1≡1
≡ valid
Take (iv)
pq⇒ p + q ≡(pq)′+p+q
≡p′+q′+p+q
≡1+1
≡1
≡ valid

Take (v)
pq⇒q′+p≡(pq)′+p+q
≡p′+q′+p+q
≡1
≡ valid
So the number of expressions that are logically implies by p∧(p⇒q) is 4

Answer 3

Wow the question completely befooled me. From the given options I don't even know what to answer, but when I see that "implied" in the question things become very easy.

Here's what we need to do:

1. First of all simplify the given expression : P ∧ (P ⇒ Q). The simplification will give P ∧ Q

2. Now you need to apply implication of P ∧ Q with all the options, let P∧Q = x

now,

x ⇒ false

x ⇒ Q

x ⇒ true

x ⇒ (P v Q)

x ⇒ (not Q or P)  

The options that will yield true as output is the answer.