Latest Tweets

Truth table

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.

 

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)$: