Computing a Truth Value

Every connective is a truth function (Truth Values of the Connectives), and every formula is built step by step (The Main Connective and Scope). Put those two facts together and you can find the value of any formula once you know the values of its letters.

Key idea

Work from the inside out. Write the value of each letter, then the value of each smallest compound part, and keep going until you reach the main connective. Its value is the value of the whole formula.

Why it works

A formula is a tree: the letters are the leaves and the main connective is the root. Each connective needs the values of its own parts before it can give a value, so the innermost parts must be done first. Working left to right ignores the tree and can apply a connective to the wrong pieces.

One row: the part columns show the inside-out order.

Worked examples

Worked example: Two letters

Let $p$ be T and $q$ be F. Find the value of $\neg (p \land q) \lor q$.

Innermost: $p \land q$ is F (one part is F).
$\neg (p \land q)$ is T.
The main connective $\lor$ joins T and $q$ = F, giving T.

Answer: T

Worked example: Three letters

Let $p$ be T, $q$ be F and $r$ be T. Find $(p \lor q) \to \neg r$.

$p \lor q$ is T.
$\neg r$ is F.
The conditional has a T antecedent and an F consequent, so it is F.

Answer: F

Worked example: A negation in front

With the same values, find $\neg ((p \to q) \leftrightarrow r)$.

$p \to q$ is F (T → F).
$(p \to q) \leftrightarrow r$ compares F with T: different, so F.
The outer $\neg$ makes it T.

Answer: T

Common mistake

Working left to right, or applying a negation to the wrong part. In $\neg p \land q$ the $\neg$ belongs to $p$ alone, but in $\neg (p \land q)$ it belongs to the whole conjunction. Before you compute, find the main connective and the scope of each $\neg$; then write the value of every part under its connective, as the table above does.

Writing each part's value under its connective is not busywork. It lets you, or anyone checking your work, find a slip in a single step instead of redoing the whole formula. Longer formulas need nothing new, only more parts. A formula with ten connectives takes ten small steps, each one a look-up in the table of the connective.

A good check at the end: look at the main connective and ask whether the value you got makes sense for it. A conjunction you marked T must have both parts T; a conditional you marked F must have a true antecedent and a false consequent. If not, one of the inside steps went wrong.

The same method answers questions about parts: the value of $p \to r$ inside $(p \to r) \land q$ is just the value you wrote under that arrow on the way up.

Computing a Truth Value

Worked examples

Practice

Builds on

Leads to

Sources and further reading