Propositional logic/Tautologies/Applied sciences/Introduction/Section

For every single proposition and compound propositions every truth value is allowed, and the truth values of the compound propositions are determined by the truth assignments of the single propositions and the truth rules of the connectives. So, depending on the truth assignments, all statements might be true or false. However, those statements are particularly interesting which produce for every single assignment always the value true. Such propositions are called tautologies. They are important in mathematics as they represent allowed conclusions as they appear in proofs quite often. E.g., if one has already proven the statements ${}p$ and ${}p\rightarrow q$, where ${}p$ and ${}q$ represent concrete mathematical statements, then one can deduce the validity of ${}q$. In propositional logic, this deduction is represented by the tautology

$(p\wedge (p\rightarrow q))\rightarrow q.$

As mentioned, a tautology is characterized by the constant logical value true. The proof that a certain proposition is a tautology is easiest done with the help of a truth table.

Modus ponens
${}p$ ${}q$ ${}p\rightarrow q$ ${}p\wedge (p\rightarrow q)$ ${}(p\wedge (p\rightarrow q))\rightarrow q$ t t t t t t f f f t f t t f t f f t f t

Double negation
${}p$ ${}\neg p$ ${}\neg (\neg p)$ ${}p\leftrightarrow \neg (\neg p)$ t f t t f t f t

Tertium non datur
${}p$ ${}\neg p$ ${}p\vee \neg p$ t f t f t t

The rule tertium non datur goes back to Aristotle. It says that a proposition is either true or false and that there is no third possibility. The rule above says formally only that at least one truth value must hold, but the rule before says that ${}p$ and ${}\neg p$ can not be both true, what is also called the law of noncontradiction (together this is called the principle of bivalence). The validity of these rules is dubious in colloquial statements, but in the framework of propositional logic and of mathematics they hold without any restriction. This is related to the fact that in these fields only such statements are allowed which have a unique truth value. As a principle of proof, the logical principle of bivalence occurs as proof by cases, the following tautology expresses this.

Proof by cases
${}p$ ${}q$ ${}p\rightarrow q$ ${}\neg p$ ${}\neg p\rightarrow q$ ${}((p\rightarrow q)\wedge (\neg p\rightarrow q))$ ${}((p\rightarrow q)\wedge (\neg p\rightarrow q))\rightarrow q$ t t t f t t t t f f f t f t f t t t t t t f f t t f f t

In a proof by cases, one wants to proof ${}q$, and one proves it first under the additional assumption that ${}p$ holds (case 1) and secondly under the additional assumption that ${}\neg p$ holds (case 2). One has to do two steps, but in each step one can use additional information.

Contraposition is often used in proofs, and quite often this is not made explicit. In a proof we use a pragmatic viewpoint, and sometimes it is easier to pass from ${}\neg q$ to ${}\neg p$ instead of passing from ${}p$ to ${}q$.

Contraposition
${}p$ ${}q$ ${}p\rightarrow q$ ${}\neg p$ ${}\neg q$ ${}\neg q\rightarrow \neg p$ ${}(p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)$ t t t f f t t t f f f t f t f t t t f t t f f t t t t t

The proof by contradiction is also a useful pattern of argumentation. One shows that a certain statement ${}p$ implies a contradiction, often of the form ${}q\wedge \neg q$, and then one infers that ${}p$ can not be true, so that ${}\neg p$ must hold.

Proof by contradiction
${}p$ ${}q$ ${}p\rightarrow q$ ${}p\rightarrow \neg q$ ${}(p\rightarrow q)\wedge (p\rightarrow \neg q)$ ${}\neg p$ ${}(p\rightarrow q)\wedge (p\rightarrow \neg q)\rightarrow \neg p$ t t t f f f t t f f t f f t f t t t t t t f f t t t t t