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