GATE CSE 2001 | Question: 1.3

Question

Consider two well-formed formulas in propositional logic

$F_1: P \Rightarrow \neg P$          $F_2: (P \Rightarrow \neg P) \lor ( \neg P \Rightarrow P)$

Which one of the following statements is correct?

• A. $F_1$ is satisfiable, $F_2$ is valid
• B. $F_1$ unsatisfiable, $F_2$ is satisfiable
• C. $F_1$ is unsatisfiable, $F_2$ is valid
• D. $F_1$ and $F_2$ are both satisfiable

Comments

If this question would be MSQ, then option A) and D), both are correct.

---

I too think of the same think because a tautology is also satisfiable.. can any one correct me if i am wrong … My reasoning is the satisfiable wants at least one input combination for which the output is true ..  and tautology give output true for all input combination of inputs ..

---

Well we can solve this easily by the case method or by the boolean algebra

Answer 1

$F1: P\to \neg P$

    $=\neg P\vee \neg P$

    $=\neg P.$      can be true when P is false ( Atleast one T hence satisfiable)

$F2:  (P\to \neg P)\vee (\neg P\to P)$

     $=\neg P \vee (P\vee P)$

     $=\neg P \vee P$

     $=T.$

VALID

Option (A)

Comments

Arjun Sir, there's some typo here in F1 

=¬P∧¬P 

it should be -P v –P 

---

can we say if  Contingency then we can say it is satisfiable?

Bcoz contingency can also be happen if it’s not satisfiable.

Please verify.

 

As i learn SATISFIABLE == Tautology

and NOT SATISFIABLE == Contradiction

can we include a contingency in both scenario?

---

@princeit07 yes i think so because in contingency having sometimes true & sometime false then it is neither tautology nor contradiction.

Answer 2

"A valid (true for every set of values)  formula is always satisfiable (true for at least one value)  , but a satisfiable formula may or may not be valid".

as F1 is not valid but satisfiable,

and F2 is valid(which implicitly means is satisfiable too).

therefore OPTION A is the complete solution, but OPTION D is not. 

Answer 3

Given:

$F_1: P → \sim P$

$F_2: (P → \sim P) \vee (\sim P → P) $

 

Lets find out by case method for each of the above equation.

$F_1: P → \sim P$

Case 1: $P=True$	Case 2: $P=False$
$F_1: True → \sim True$ $F_1: True → False$ $F_1: False$	$F_1: False→ \sim False$ $F_1: False → True$ $F_1: True$

 

We observe that $F_1$ is both $True$ and $False$ depending upon the input value. This is the property of Satisfiability.

Therefore $F_1$ is Satisfiable.

 

$F_2: (P →\sim P) \vee (\sim P → P) $

Case 1: $P=True$	Case 2: $P=False$
$F_2: (True → \sim True) \vee (\sim True → True)$ $F_2: (True → False) \vee (False → True)$ $F_2: False \vee True$ $F_2: True$	$F_2: (False → \sim False) \vee (\sim False → False)$ $F_2: (False → True) \vee (True → False)$ $F_2: True \vee False$ $F_2: True$

 

We observe that $F_2$ is $True$ for both the cases. It doesn’t depends upon the input. This is the property of Tautology.

Therefore $F_2$ is Valid $(Valid \equiv Tautology)$.

 

Answer is (A).

Answer 4

 

😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊