0
$\begingroup$

This question already has an answer here:

am having problems understanding the difference between validity and satisfiability. Given the following:

(i) For all F, F is satisfiable or ~F is satisfiable.

(ii) For all F, F is valid or ~F is valid.

How do I prove which is true and which is false?

Statement (i) is true, as for all F, F will either be satisfiable, or ~F will be satisfiable (truth table). However, how do I go about solving for statement (ii)?

Any help is highly appreciated!

$\endgroup$

marked as duplicate by Git Gud, Lord_Farin, Mark Bennet, Vedran Šego, user1551 Sep 23 '13 at 21:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

A formula is satisfiable if it holds under some interpretation, i.e., it can be satisfied. A formula is valid if it holds under every interpretation, i.e., it cannot be falsified. E.g., over the natural numbers $x = 2$ is satisfiable (we can satisfy it by interpreting $x$ as $2$) but not valid (we can falsify it by interpreting $x$ as $3$).

So for part (i) any interpretation of a formula $F$ will make one of $F$ or $\lnot F$ hold. But for part (ii) if $F$ is $x = 2$, then $F$ can be satisfied and falsified, so neither $F$ nor $\lnot F$ is valid.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.