Test: Propositional Logic - Computer Science Engineering (CSE) MCQ

Concept:
Logically Equivalent: Two expressions are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions. In this case, we write X≡Y and say that X and Y are logically equivalent.

The given expression is,
 "I pass only if you pass"
P = I pass.
¬P = I fail.
Q = you pass.
¬Q = you fail.
 "I pass only if you pass" = P ⇒ Q = ¬P ∨ Q
Option 1: You pass only if I pass
False,  Q ⇒ P = ¬Q ∨ P
Option 2: If you fail then I fail
True, ¬Q ⇒ ¬P = Q∨ ¬P
Option 3: If you pass then I pass.
False, Q ⇒ P = ¬Q ∨ P
Option 4: You fail if I pass.
False, ¬Q ⇒ P = Q ∨ P
Hence the correct answer is If you fail then I fail.

Option 1: P→Q is True

True, In general, P→ Q is false, only when P is true and Q is false.

If q is true, then irrespective of the P value, it holds true.

 The population of Hyderabad is more than Delhi we can not predict which city is more polluted. So it may be True or False. 

Here, ‘Q’ is true, as Jan, Mar, May, Jul, Aug, Oct, Dec months have 31 days. 

P→Q is True.

Option 2: (P→Q)→ Q is False

False, As Q is true, P→Q and (P→Q )→Q holds true.

Option 3: Q→ (P→Q ) is False

False, As P→Q is true, Q→ ( P→Q) holds true.

Option 4: ¬(P→Q) is True

True, This complement of  (P→Q). As (P→Q) is true then ¬(P→Q) is False.

Hence the correct answer is P→Q is True

Satisfiable: A compound proposition that is not a contradiction is said to be satisfiable.
Tautology (Valid): A compound proposition that is always true is called tautology (valid).
Contradiction: A compound proposition that is always false is called a contradiction.
F₁ : (p ↔ q)∧(¬ p ↔ q)
We know that ¬ (p ↔ q)= (¬ p ↔ q)
So, if (p ↔ q) is assumed of A.
Then A∧¬A = 0 or False
Means (p ↔ q)∧(¬ p ↔ q) is unsatisfiable.
F2 : (p∨¬q)∧(¬ p∨q) ∧(¬ p∨¬q)
= (p+q¯)(p¯+q)(p¯+q¯)
= (p+q¯)(p¯+qq¯)
= (p+q¯)(p¯)
= p¯q¯
Which is not valid but satisfiable. 
So, F₁ is unsatisfiable but F₂ is satisfiable.
Hence the correct answer is F₁ is unsatisfiable, F₂ is satisfiable.

Data:
p: x ∈ {8, 9, 10, 11, 12}
q: x is a composite number
r: x is a perfect square
s: x is a prime number
Explanation:
p ⇒ q means p̅ + q
As, q is composite number So, p ⇒ results in {8, 9, 10, 12}
As, r: x is a perfect square, ¬ r results in all the numbers which are not perfect square
So, ¬ r: {8, 10, 11, 12}
¬ s: {8, 9, 10, 12}
¬ r ∨ ¬ s = {8, 9, 10, 11, 12}
Now, (p ⇒ q) ∧ (¬ r ∨ ¬ s) = {8, 9, 10, 12}
¬ ((p ⇒ q) ∧ (¬ r ∨ ¬ s)) results in a number which is not present in ((p ⇒ q) ∧ (¬ r ∨ ¬ s))
¬ ((p ⇒ q) ∧ (¬ r ∨ ¬s)) will give {11}.

Concept:
Hypothetical syllogism,
If p → q and q → r then p → r
Formula:
p → q ≡ ¬ q → ¬ p ≡ ¬ p ∨ q 

Explanation:
C(x): x is known to be corrupt
E(x): x will be elected
K(x): x is kind
Statement S1 can be written as:
S1 ≡ C(x) → ¬E(x) 
S2 can be written as:
S2 ≡ K(x) → E(x) ≡ ¬E(x) →¬K(x) 
By using hypothetical syllogism,
From S1 and S2, the conclusion is
C(x) → ¬K(x) ≡ K(x) → ¬C(x)
If a person is kind, then he is not known to be corrupt.

(p → q) → r is a contradiction which is possible only when r is false and (p → q) is true.
Now, from here we can clearly say that option 4 is correct as (r → p) → q means ¬ (r → p) ∨ q.
Since r is false, (r → p) is true and ¬ (r → p) becomes false.
So, it becomes (false ∨ q). Now it totally depends on q. Whenever q is true, this value will always be true.
Alternate Method:
Let X ≡ p → q, Y ≡ (p → q) → r ≡ X → r,
Z ≡ r → p and W ≡ (r → p) → q ≡ Z → p
Using Truth table

So, from truth table also, it is clear that (r → p) → q is always true when q is true, and Y is false.

The statement “If X then Y unless Z” means, if Z doesn’t occur, X implies Y i.e. ¬Z→(X→Y), which is equivalent to Z ∨ (X→Y)

(since P→Q ≡ ¬P ∨ Q), which is then equivalent to Z ∨ (¬X ∨ Y). Now we can look into options which one matches with this.

So option (a) is (X∧¬Z)→Y = ¬( (X∧¬Z) ) ∨ Y = (¬X∨Z) ∨ Y, which matches our expression. So option (A) is correct.

I₁ states that:
Statement
Consider A = it rains,
B = match played
So, If (it rains) then (match will not be played) that means,
A → (¬ B)
Inference states that “there was no rain” means A = false (F)
Therefore, for any F → (¬ B) i.e. for any "F that implies not B" is true.
So this inference is valid.
Here the only condition is if it rains the match will not be played. That doesn’t mean if it will not rain then the match will be played.
If the match was played then it means it doesn’t rain.
So this inference is valid.

I₂ states that:
Statement
Consider A = it rains,
B = match played
So, If (it rains) then (match will not be played) that means,
A → (¬ B)
Inference states that “the match was played”.
Here the only condition is if it rains the match will not be played. If the match was played then it means it doesn’t rain.
That doesn’t mean if it will not rain then the match will be played.
So this inference is invalid.
Hence, the correct answer is "option b".

If the statement is true, then the contrapositive is also logically true.

The given statement is,
"If Indian army moves back and Chinese army moves back, then there is no war”
For the compound statement p→q, the contrapositive is ~q→~p.
The given statement is in the form ( p∧q) →r
So contrapositive is ~r→~(p∧q).
Hence the correct answer is ​~r→~(p∧q).

Given that, If p = a number from {8, 9, 10, 11, 12}
q = not a composite number
r = a square number
s = a prime number
~((p→~ q)∧(~r ∨~S) )
¬((p→¬q)∧(¬r∨¬S))
¬(¬p∨¬q)∨¬(¬r∨¬S)
(p∧q)∨(r∧s)
p∧ q = {8, 9, 10, 11, 12} ∧  {11 } = {11}
(r ∧ s) = { a square number }∧{ a prime number}
(r ∧ s) = {9} ∧ {11} = { }
(p∧ q) ∨ (r ∧ s)= {11} ∨ { } = {11}
Hence the correct answer is 11.