I'm working on a task which i'm a bit stuck at. I need to decide whether the statements are true or fale. F stands for the statement logical formulas, and also if the claim is true I need to give a proof or explain why it is so. If the statement is false I need to give a contra-example
Here are the statements:
For all F, then F is satisfiable or ¬F is satisfiable
and
For all F, then F is valid or ¬F is valid.
Is there any easy way I can solve these kinds of statements by seeing if a statement satisfies or is valid or is neither both of them?
Would appreciate some help, thanks alot!
There exist three classes of formulas: tautologies, contingencies, and contradictions. A tautology has all "1"'s (at the end of its rows) for its truth table, a contingency has at least one "1" and at least one "0" for its truth table, and a contradiction has all "0"'s for its truth table.
Case 1: If a formula F qualifies as a tautology, it qualifies as valid. Thus, it always comes as satisfied, and thus always satisfiable. So, if F qualifies as a tautology, then either F is satisfiable or $\lnot$F is satisfiable.
Case 2: If a formula F qualifies as a contingency, then its truth table has at least one row with a "1" in it. Consequently, for that row the formula gets satisfied and thus F qualifies as satisfiable. So, if F qualifies as a contingency, then either F is satisfiable or $\lnot$F is satisfiable.
Case 3: If a formula F qualifies as a contradiction, then it has all "0"'s in its truth table. So, for no row does it come as satisfied. Thus, $\lnot$F has all "1"'s for its truth table. So, $\lnot$F always qualifies as satisfied, and thus qualifies as satisfiable. So, if F qualifies as a contradiction, then either F is satisfiable or $\lnot$ F is satisfiable.
Since these cases exhaust the possibilities, for any given propositional formula F either F is satisfiable or $\lnot$F is satisfiable.
As Git Gud points out you only need to consider a truth table for a propositional atom for the second part.