The Gateway to Computer Science Excellence
+19 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
in Mathematical Logic by Veteran (52.2k points)
edited by | 2.7k views
Every valid formula is satisfiable.

So A & D both are correct but A is more precise.
Valid == Tautology!
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)

3 Answers

+27 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)

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.
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



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

+1 vote

"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. 

by (353 points)
–2 votes
I can see both are satisfiable i wl go for option b
by Boss (14.4k 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
50,737 questions
57,342 answers
105,214 users