Discrete Mathematics Thegatebook

Question

22)Which one is the correct

S1: A formula is valid iff its complement is not satisfiable
S2: A formula is satisfiable iff its complement is not valid.
a) Only S1 b) Only S2 c) both S1 and S2 d) none

Answer 1

C...

Comments

Please explain this question answer (A)

Answer 2

lets take a valid formula and verify the option

my formula is pV~p = True which is a valid formula.

So on negating or complimenting the formula would give you False which is not satisfiable.

So option S1 is True statement

take in the similar way you can show that Statement S2 is false

Answer 3

A formula is valid , nothing but a tautalogy.

If we negate a tautalogy , we will get a CONTRADICTION (all are False).... hence not SATISFIABLE.

A formula is satisfiable, iff there is at least one TRUTH value , so even a tautalogy is also satisfiable.

lets take $P \Lambda Q$

its SATISFIEABLE for P=T and Q=T. if we negate $P \Lambda Q$ then we will get (F,T,T,T)..its not a tautalogy.

 

In the same if you consider any tautalogy, its valid and satisfiable, but after complimenting its not a valid and satisfiable.