I 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!
This question doesn't really belong in computational science (I'd suggest math.stackexchange.org), but I'll go ahead and answer anyway.
An expression in propositional calculus is valid if the expression is true under all possible assignments of the variables. The expression is satisfiabile is it is true under at least one assignment of the variables.
For example, consider the expression $p \lor \neg p$. The truth table is
$ \begin{array}{cc} p & p \lor \neg p \\ T & T \\ F & T \end{array} $
Thus this expression is valid and satisfiable.
Next, consider the expresion $p \lor q $. This has the truth table
$ \begin{array}{ccc} p & q & p \lor q \\ T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array} $
This expression is satisfiable (since there is at least one assignment of the variables that makes the expression true), but not valid (since there is at least one assignment that makes the expression false.)
If you look at a truth table with columns for an expression $A$ and $ \neg A$, then either all entries in the column for $A$ are T or all entries are F or there is a mixture of T and F entries. If all entries in the column for $A$ are T, then $A$ is valid. If all entries in the column for $A$ are F, then all entries in the column for $\neg A$ are T, and $\neg A$ is valid. What happens when the column for $A$ has a mixture of T and F entries?