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

The concept behind this solution is:
a) Satisfiable
If there is an assignment of truth values which makes that expression true.
b) UnSatisfiable
If there is no such assignment which makes the expression true
c) Valid
If the expression is Tautology
Here, P => Q is nothing but –P v Q
F1: P => -P = -P v –P = -P
F1 will be true if P is false and F1 will be false when P is true so F1 is Satisfiable
F2: (P => -P) v (-P => P) which is equals to (-P v-P) v (-(-P) v P) = (-P) v (P) =
Tautology
So, F1 is Satisfiable and F2 is valid
Option (a) is correct.

---

1."A formula is called Satisfiable if it is true at least one case "

2."A formula is called valid if it is true in all the cases."

3.Valid formula or tautology are the same things.

4.Satisfiable and Contradiction are two opposite argument.

5.If formula is Satisfiable can not be Contradiction and vice-versa

---

Why not option D

both F1 and F2 are satisfiable

---

option A is more tight

---

i think 4th option should be Tautology & Contradiction are two opposite arguments

and 5th option too.

i know it applies to satisfiablity too but most appropriate would be for Tautology.

---

This answer packed everything together.Thanks a bunch!

---

what is invalid or Faulty in terms of  propositional Logic ?

---

Falsy means always false or contradiction.

Invalid means at least one false

---

@ bhanu kumar 1 

Read the entire comment and answer, you will understand better.

---

ok

---

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

 

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