# 3.2: Propositional Logic in Computer Programs

• Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
• Google and Massachusetts Institute of Technology via MIT OpenCourseWare
$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

Propositions and logical connectives arise all the time in computer programs. For example, consider the following snippet, which could be either C, C++, or Java:

\begin{aligned} \text{if } &(x > 0) || (x <= 0 \text{ && } y > 100) \\ & \vdots \\ &\textit{(further instructions)} \end{aligned}

Java uses the symbol || for “$$\text{OR}$$,” and the symbol && for “$$\text{AND}$$.” The further instructions are carried out only if the proposition following the word if is true. On closer inspection, this big expression is built from two simpler propositions.

Let $$A$$ be the proposition that $$x > 0$$, and let $$B$$ be the proposition that $$y > 100$$. Then we can rewrite the condition as

$\label{3.2.1} A \text{ OR } (\text{NOT}(A) \text{ AND } B)$

## Truth Table Calculation

A truth table calculation reveals that the more complicated expression 3.2 always has the same truth value as

$\label{3.2.2} A \text{ OR } B.$

We begin with a table with just the truth values of $$A$$ and $$B$$:

$\nonumber \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\text{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & & & & & \\ \mathbf{T} & \mathbf{F} & & & & & & \\ \mathbf{F} & \mathbf{T} & & & & & & \\ \mathbf{F} & \mathbf{F} & & & & & & \end{array}$

These values are enough to fill in two more columns:

$\nonumber \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\text{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & & \mathbf{F} & & & \mathbf{\large T} \\ \mathbf{T} & \mathbf{F} & & & \mathbf{F} & & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{T} & & & \mathbf{T} & & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{F} & & & \mathbf{T} & & & \mathbf{\large F} \end{array}$

Now we have the values needed to fill in the $$\text{AND}$$ column:

$\nonumber \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\text{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & & \mathbf{F} & \mathbf{F} & & \mathbf{\large T} \\ \mathbf{T} & \mathbf{F} & & & \mathbf{F} & \mathbf{F} & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{T} & & & \mathbf{T} & \mathbf{T} & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{F} & & & \mathbf{T} & \mathbf{F} & & \mathbf{\large F} \end{array}$

and this provides the values needed to fill in the remaining column for the first $$\text{OR}$$:

$\nonumber \begin{array}{cc|ccccc|c} A & B & A & \text { OR } & (\text{NOT}(A) & \text { AND } & B) & A \text { OR } B \\ \hline \mathbf{T} & \mathbf{T} & & \mathbf{\large T} & \mathbf{F} & \mathbf{F} & & \mathbf{\large T} \\ \mathbf{T} & \mathbf{F} & & \mathbf{\large T} & \mathbf{F} & \mathbf{F} & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{T} & &\mathbf{\large T} & \mathbf{T} & \mathbf{T} & & \mathbf{\large T} \\ \mathbf{F} & \mathbf{F} & & \mathbf{\large F} & \mathbf{T} & \mathbf{F} & & \mathbf{\large F} \end{array}$

Expressions whose truth values always match are called equivalent. Since the two emphasized columns of truth values of the two expressions are the same, they are equivalent. So we can simplify the code snippet without changing the program’s behavior by replacing the complicated expression with an equivalent simpler one:

\begin{aligned} \text{if } &(x > 0 || y > 100) \\ & \vdots \\ &\textit{(further instructions)} \end{aligned}

The equivalence of (\ref{3.2.1}) and (\ref{3.2.2}) can also be confirmed reasoning by cases:

$$A$$ is $$\textbf{T}$$. An expression of the form ($$\textbf{T} \text{ OR}$$ anything) is equivalent to $$\textbf{T}$$. Since $$A$$ is $$\textbf{T}$$ both (\ref{3.2.1}) and (\ref{3.2.2}) in this case are of this form, so they have the same truth value, namely, $$\textbf{T}$$.

$$A$$ is $$\textbf{F}$$. An expression of the form ($$\textbf{F} \text{ OR}$$ anything) will have same truth value as anything. Since A is $$\textbf{F}$$, (\ref{3.2.2}) has the same truth value as $$B$$.

An expression of the form ($$\textbf{T} \text{ AND}$$ anything) is equivalent to anything, as is any expression of the form $$\textbf{F} \text{ OR}$$ anything. So in this case $$A \text{ OR } (\text{NOT}(A) \text{ AND } B)$$ is equivalent to $$(\text{NOT}(A) \text{ AND } B)$$, which in turn is equivalent to $$B$$.

Therefore both (\ref{3.2.1}) and (\ref{3.2.2}) will have the same truth value in this case, namely, the value of $$B$$.

Simplifying logical expressions has real practical importance in computer science. Expression simplification in programs like the one above can make a program easier to read and understand. Simplified programs may also run faster, since they require fewer operations. In hardware, simplifying expressions can decrease the number of logic gates on a chip because digital circuits can be described by logical formulas (see Problems 3.5 and 3.6). Minimizing the logical formulas corresponds to reducing the number of gates in the circuit. The payoff of gate minimization is potentially enormous: a chip with fewer gates is smaller, consumes less power, has a lower defect rate, and is cheaper to manufacture.

## Cryptic Notation

Java uses symbols like “&&” and “||” in place of $$\text{AND}$$ and $$\text{OR}$$. Circuit designers use "$$\cdot$$" and "+," and actually refer to $$\text{AND}$$ as a product and $$\text{OR}$$ as a sum. Mathematicians use still other symbols, given in the table below.

$\nonumber \begin{array}{cc} \textbf{English} & \textbf{Symbolic Notation} \\ \text{NOT}(P) & \lnot P \quad \text{(alternatively,} \overline{P}) \\ P \text{ AND } Q & P \wedge Q \\ P \text{ OR } Q & P \lor Q \\ P \text{ IMPLIES } Q & P \longrightarrow Q \\ \text{If } P \text{ then } Q & P \longrightarrow Q \\ P \text{ IFF } Q & P \longleftrightarrow Q \\ P \text{ XOR } Q & P \oplus Q \end{array}$

For example, using this notation, “If $$P \text{ AND NOT } (Q)$$, then $$R$$” would be written:

$\nonumber P \wedge \overline{Q} \rightarrow R.$

The mathematical notation is concise but cryptic. Words such as “$$\text{AND}$$” and “$$\text{OR}$$” are easier to remember and won’t get confused with operations on numbers. We will often use $$\overline{P}$$ as an abbreviation for $$\text{NOT}(P)$$, but aside from that, we mostly stick to the words—except when formulas would otherwise run off the page.

This page titled 3.2: Propositional Logic in Computer Programs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .