Prove that a sentence is tautology, satisfiable but not tautology or unsatisfiable

Question

I am trying to understand how to determine whether a sentence is a tautology, satisfiable but not tautology or unsatisfiable using the right approach

Example: (¬up → ¬down) → ¬up

---

I tried the following

(¬up → ¬down) → ¬up = (up ⋁ ¬down) → ¬up

then I get stucked in the next step

Answer 1

The easiest way to check whether a formula is satisfiable, tautological or contradictory is to have a look at the truth table:

• the last column has at least one row with true: the formula is satisfiable
• the last column has only rows with true's: the formula is tautological
• the last column has only rows with false's: the formula is contradictory/unsatisfiable

So let's have a look at the truth table for the formula $(\neg u \to \neg d) \to \neg u$ ("u" abbreviates "up", "d" abbreviates "down"):

u d | ¬u ¬d ¬u→¬d (¬u→¬d)→¬u
t t | f  f    t        f    
t f | f  t    t        f    
f t | t  f    f        t    
f f | t  t    t        t

Since the last column has at least one row with true, the formula is satisfiable/non-contradictory.
Since the last row has alwo rows with false, the formlua is not tautological.
A formula which is satisfiable but not tautological, i.e. which has both true's and false's in its truth table, is also called contingent.

Answer 2

In reference to your example:

$(P \Rightarrow Q)$ $\Rightarrow P$ is clearly satisifiable when $P$ and $Q$ are true, but it is not a tautology. Consider the implication $P \Rightarrow Q$ which is true when $P$ is false and $Q$ is true. Now consider the sentence $(P \Rightarrow Q)\Rightarrow P$. We will end up with $T \Rightarrow F$ since $P$ is false and so the sentence is not a tautology.

Answer 3

Possible methods to determine the semantic status of a formula ( tautology? antilogy? contingent formula?)

(1) Transform the formula using logical equivalences.

• If the formula is equivalent to a known tautology, then the formula is a tautology.

• If the formula is equivalent to a known antilogy ( logical falsehood) then it is a logical falsehood.

• If the negation of your formula is equivalent to a known tautology, then the formula is an antilogy.

• If the negation of the formula is equivalent to a known antilogy, then the formula is a tautology.

(2) If none of the above methods works, use a truth table.

Remark. The fact that method (1) does not work proves nothing ( it does not prove that it is not a tautology or an antilogy). Or I should say, it only proves that I did not manage to find an equivalent tautology/ antilogy. Some more clever logician might manage to find what I did not manage to find.

However, method 1's failure makes it probable ( simply probable) that the formula is contingent.

Anyway, a truth table will tell you what is the logical status of the formula.

(3) Since there is a correspondance between semantics and syntax, you can also try to derive ( as conclusion )the consequent of the conditional from the antecedent taken as hypothesis . If you manage to do that, the soundness of your formal system ( for example, the natural deduction system) guarantees you that the formula : "antecedent --> consequent" is a tautology.