edited by
8,932 views
30 votes
30 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
edited by

5 Answers

Best answer
37 votes
37 votes

$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)

edited by
5 votes
5 votes

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

1 votes
1 votes

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

1 votes
1 votes

 

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

Answer:

Related questions

25 votes
25 votes
2 answers
1
Kathleen asked Sep 14, 2014
10,419 views
Which of the following requires a device driver?RegisterCacheMain memoryDisk
37 votes
37 votes
3 answers
2
Kathleen asked Sep 14, 2014
12,502 views
Where does the swap space reside?RAMDiskROMOn-chip cache
36 votes
36 votes
2 answers
3
Kathleen asked Sep 14, 2014
12,519 views
The process of assigning load addresses to the various parts of the program and adjusting the code and the data in the program to reflect the assigned addresses is called...
25 votes
25 votes
2 answers
4