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

Every valid formula is satisfiable.

So A & D both are correct but A is more precise.

---

Valid == Tautology!

---

vishalshrm539 

https://math.stackexchange.com/questions/629198/validity-vs-tautology-and-soundness

---

in which condition F1 can be unsatisfiable?

---

$F_1: P \Rightarrow \neg P\equiv\neg P\vee \neg P\equiv\neg P$

When we put $P\equiv T$ it will $F$

 and When we put $P\equiv F$ it will $T$

It is called contingency.

Always false called contradiction or unsatisfiable

Always true called valid or tautology

At least one true called satisfiable.

 

$F_2: (P \Rightarrow \neg P) \lor ( \neg P \Rightarrow P)\equiv\neg P\vee P\equiv T$(Always true)

---

Correct ME

F1: P => ~p

This statement have logical implication(=>) means  P → ~p is tautology

therefore F1 is always true (therefore F1 is valid statement)

---

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

---

A satisfiable proposition can be a tautology.

---

Property	Meaning
Valid	TRUE for all assignments
Satisfiable	TRUE for at least one assignment
Unsatisfiable	TRUE for none

---

why are we not considering option d also , as along with option a , option d is also correct . f1 and f2 are both satisfiable . then why not option d ?

---

F1​ is satisfiable, F2​ is valid

Options A is Correct

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

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.

---

got it

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

 

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

Answer 5

The correct option is A) F1 is satisfiable, F2 is valid

Following is the solution of this question:

Answer 6

I can see both are satisfiable i wl go for option b

Comments

valid means always true. That is, whatever be the values assigned to the variables, the formula returns true. eg. $p\vee \neg p$

---

Then what is your opinion about this which is the most appropriate

---

(a) is the most appropriate.