UoL CS Notes
Menu

Truth Values

COMP111 Lectures

An interpretations $I$ assigns to every atomic proposition $p$ a truth value: \(I(p)\in\{0,1\}\)

This means:

  • If $I(p)=1$, then $p$ is called true under the interpretation $I$.
  • If $I(p)=1$, then $p$ is called false under the interpretation $I$.

Given an assignment $I$ we can computer the truth value of compound formulas step by step by using truth tables.

Negation

The negation $\neg P$ of a formula $P$. It is not the case that $P$:

$P$ $\neg P$
1 0
0 1

Conjunction

The conjunction $(P\wedge Q)$ of $P$ and $Q$. Both $P$ and $Q$ are true:

$P$ $Q$ $(P\wedge Q)$
1 1 1
1 0 0
0 1 0
0 0 0

Disjunction

The disjunction $(P\vee Q)$ of $P$ and $Q$, at least one of $P$ and $Q$ is true:

$P$ $Q$ $(P\vee Q)$
1 1 1
1 0 1
0 1 1
0 0 0

Equivalence

The equivalence $(P\Leftrightarrow Q)$ of $P$ and $Q$, $P$ and $Q$ take the same truth value:

$P$ $Q$ $(P\Leftrightarrow Q)$
1 1 1
1 0 0
0 1 0
0 0 1

Implication

The implication $(P\Rightarrow Q)$, if $P$ then $Q$:

$P$ $Q$ $(P\Rightarrow Q)$
1 1 1
1 0 0
0 1 1
0 0 1

Truth Under an Interpretation

So, given an interpretation $I$, we can compute the truth value of any formula $P$ under $I$:

  • If $I(p)=1$, then $p$ is called true under the interpretation $I$.
  • If $I(p)=1$, then $p$ is called false under the interpretation $I$.

Example

$p_1$ $p_2$ $\neg p_2$ $\neg p_1$ $(p_1\wedge\neg p_2)$ $(p_2\wedge\neg p_1)$ $P$
1 1 0 0 0 0 1
1 0 1 0 1 0 0
0 1 0 1 0 1 1
0 0 1 1 0 0 1

Thus the interpretations $I$ making $P$ true are:

  • $I(p_1)=1$ and $I(p_2)=1$
  • $I(p_1)=0$ and $I(p_2)=1$
  • $I(p_1)=0$ and $I(p_2)=0$