In mathematical logic every statement is considered to be either true or false. Furthermore, if we have two statements $P$ and $Q$, by using logical operators we can make more complicated statements. Here we explain truth tables and tautology truth.
Propositions
Definition: A proposition is a declarative sentence that is either true or false (but not both).
Example 1:
a) $2 + 2 = 4$ (true proposition)
b) $2 + 2 = 5$ (false proposition)
c) $x + 2 = 8$
This is not a proposition because we can’t determine is it true or false since we don’t know the value of x.
d) ”What time is it?” is not a proposition because it is not a declarative sentence.
Definition: A propositional variable is a variable that represents propositions.
Therefore, a propositional variable can either be true or false.
Language of propositional alphabet
This alphabet is the union of sets $A_{1}, A_{2}$ and $A_{3}$:
$A_{1} = \{P_{0}, P_{1}, P_{2}, \cdots\}$ (its elements are propositional variables)
$A_{2} = \{\neg, \land, \lor, \rightarrow, \iff \}$ (its elements are logical connectives or logical operators)
$A_{3} = \{(, )\}$ (its elements are parentheses).
Logical operators:
$\neg$ (negation)
$\land$ (conjunction)
$\lor$ (disjunction)
$\rightarrow$ (conditional)
$\iff$ (biconditional)
Definition: A formula is
a) every propositional variable
b) if P and Q are formulas, then $(\neg P), (P \land Q), (P \lor Q), (P \rightarrow Q), (P\iff Q)$ are formulas.
Moreover, a word of propositional alphabet is a formula if it is a result of applying a finite number of times rules a) and b).
Definition: An interpretation is every mapping from the set of propositional variables $A_{1}$ to the set $\{0, 1\}$.
Furthermore, a formula F is true for interpretation I if $I(F) = 1$. Similarly, a formula F is false for interpretation I if $I(F) = 0$.
Tautology and contradiction
Definition: A tautology is a a formula that is true in every possible interpretation.
Definition: A contradiction is a formula that is false in every possible interpretation.
In addition, here are some examples of tautologies:
$$\neg \neg P \iff P$$
$$P \lor \neg P $$
$$\neg (P \land \neg P)$$
$$(P \rightarrow Q) \iff (\neg Q \rightarrow \neg P)$$
$$\neg P \rightarrow (P \rightarrow Q)$$
$$P \land (P \rightarrow Q) \rightarrow Q$$
$$\neg (P \land Q) \iff \neg P \lor \neg Q$$
$$\neg (P \lor Q) \iff \neg P \land \neg Q$$
$$P \land P \iff P$$
$$P \lor P \iff P$$
Example of contradiction is $P \land \neg P$.
Constructing a truth table
For example, look at the statement: ”Mark is hungry and Bella is thirsty.” It has a form ”$P$ and $Q$”, where
$P$ = Mark is hungry.
$Q$ = Bella is thirsty.
We consider that the statement of that form is true if and only if both $P$ and $Q$ are true. Otherwise, it is false.
If the statement is true, we put $1$. Otherwise, we put $0$.
Therefore, we can make a truth table:
The table shows all the combinations of truth values for $P$ and $Q$. Moreover, it shows us the corresponding truth value for $P \land Q$.
Generally speaking,
Therefore, the truth table is:
If the far right column of a truth table contains only $1’s$, the formula is a tautology. Similarly, if it contains only $0’s$, it is a contradiction.
Examples
Example 2: Construct the truth table for $P \lor \neg (P \land Q)$.
Solution:
The first thing we need to do is to list all the alternatives for $P$ and $Q$.
In the third column we list the values of $P \land Q$ by using the truth table for conjunction. In other words, $P \land Q$ is true if and only if both $P$ and $Q$ are true.
Furthermore, in the fourth column we list the values of $\neg (P \land Q)$ based on the values of $P \land Q$. In other words, we use the truth table for negation.
Finally, in the last column are values of the given expression.
Example 3: Construct the truth table for $(P \rightarrow Q) \lor (Q \rightarrow P)$. Is this a tautology?
Solution:
If we look at the last column, we notice that it contains only $1’s$. Therefore, the formula is a tautology.
Example 4: Construct the truth table for $P \land \neg (Q \lor R)$.
Solution:
Here we have three components; $P, Q$ and $R$. Similar to the previous examples, we list all the possibilities in the first three columns.
Next, we observe $Q \lor R, \neg (Q \lor R)$ and finally $P \land \neg (Q \lor R)$:
Tautology truth in math is always a true statement.
