The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 votes

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?

  1. $F_1$ is satisfiable, $F_2$ is valid
  2. $F_1$ unsatisfiable, $F_2$ is satisfiable
  3. $F_1$ is unsatisfiable, $F_2$ is valid
  4. $F_1$ and $F_2$ are both satisfiable
asked in Mathematical Logic by Veteran (59.4k points)
edited by | 1.5k views
Every valid formula is satisfiable.

So A & D both are correct but A is more precise.
Valid == Tautology!

3 Answers

+22 votes
Best answer

F1: $P\to \neg P$

    $=\neg P\wedge \neg P$

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

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

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

     $=\neg P \vee P$



Option (A)

answered by Active (2.6k points)
edited by
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) =
So, F1 is Satisfiable and F2 is valid
Option (a) is correct.
Why not option D

both F1 and F2 are satisfiable
option A is more tight
+2 votes
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
answered by Loyal (7.7k points)
–1 vote
I can see both are satisfiable i wl go for option b
answered by Boss (14.1k points)
If both are satisfiable (d) must be the answer rt? Also, isn't F2 valid making (a) a better answer?
What is a valid argument? I dont know plz explain i know the satisfiable only
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,203 questions
43,662 answers
42,944 users