Propositional Calculus and Boolean Algebra

Arithmetic expressions and equations

Since we’re familiar with real numbers, we will start with the following arithmetic equality:

$$\begin{equation} 3 \times (4 + 5) = 3 \times 4 + 3 \times 5. \end{equation}$$

The expression on the left-hand side has three numbers: $3, 4$, and $5$. Furthermore, we have used two arithmetic operations: addition($+$) and multiplication($\times$). These operations allow us to combine two numbers to get another number as a result. The famous BODMASBODMAS stands for brackets, order, division, multiplication, addition, and subtraction. It specifies the precedence of the arithmetic operations. rule tells us that to evaluate the left-hand side, we must first add $4$ with $5$ and then multiply $3$ by the result. The final calculation yields another number, $27$, as the answer.

The calculation on the right-hand side is also dictated by rules of arithmetic (including BODMAS). It also yields the same result, therefore justifying the equality.

Equation (1) is just an example of the distributive law for real numbers. In general, it states that:

$$\begin{equation} a\times (b + c) = a \times b + a \times c. \end{equation}$$

Equation (2) is true for any real numbers $a, b,$ and $c$.

The distributive law (and other laws) allows us to manipulate algebraic equations (over real numbers).

Logical expressions and equivalences

Just as arithmetic operations like addition, subtraction, and multiplication allow us to combine numbers to create other numbers, logical operations allow us to combine propositions to create new propositions called compound propositions. Let’s start with an illustrative example. Consider the following statement:

$E_1$: If Eddie gets a bonus in January, she will buy a pair of sunglasses and a new cellphone.

In the above statement $E_1$, we can readily identify three atomic statements. Let’s make a list of them:

1. $J:$ Eddie gets a bonus in January.
2. $S:$ Eddie buys a pair of sunglasses (in January).
3. $C:$ Eddie buys a new cellphone (in January).

The truth value of $E_1$ depends on the truth values of $J, S$, and $C$.

Furthermore, the following statement is obtained by combining $S$ and $C$.

$B:$ Eddie buys a pair of sunglasses and a new cellphone.

This statement labeled $B$ is called the conjunction of $S$ and $C$ (You don’t need to know what conjunction is at this point; only realize that it combines two statements).

The statement $E_1$ is obtained by combining $J$ and $B$ using an operation called implication (we’re not assuming an understanding of implication operation here.)

Therefore, the statement $E_1$ is written by logicians as:

$$\begin{equation} E_1 : J \rightarrow S \land C. \end{equation}$$

Now, let us make another compound statement:

$E_2:$ Either Eddie did not get a raise in January or she bought both sunglasses and a new cellphone.

The statement $E_2$ is written by logicians as:

$$\begin{equation} E_2 : \overline{J} \lor (S \land C). \end{equation}$$

A few moments of thought will convince you that:

$$E_1 \equiv E_2.$$

We can write down both these statements to get a logical equivalence:

$$\begin{equation} J \rightarrow S \land C \equiv \overline{J} \lor (S \land C). \end{equation}$$

Now, here is the difficult part. Is this logical equivalence true, just like the distributive law is true for all real numbers? The answer is yes!

To realize that $E_1$ and $E_2$ are equivalent statements, you must have thought of all possibilities of the atomic statements, $J, S$, and $C$. Therefore, Equation (5) is true regardless of the truth values of $J, S$, and $C$.

Just as Equation (2) is valid regardless of the values of the real numbers substituted, a logical equivalence holds irrespective of the truth value of atomic statements. Some of these fundamental equations are given the status of laws.

For now, without understanding the meaning of a bar, $\land,$ and $\lor$, let’s write the logical equivalence as:

$$\begin{equation} p \rightarrow (q \land r) \equiv \overline{p} \lor (q \land r). \end{equation}$$

Here $p, q$, and $r$ are atomic statements. These atomic statements are called boolean variables. Each boolean variable can be either true or false (but not both).

The logical equivalence (6) holds in the same sense as Equation (2) (Distributive law) holds for real numbers. The equivalence is true regardless of the individual values the boolean variables take.

We can combine statements to form new statements called compound statements. Various laws allow us to manipulate these compound statements. These laws of combining statements and the rules that enable us to manipulate them are collectively called propositional calculus. Since the atomic statements are called boolean variables, these rules are also called boolean algebra. The knowledge of boolean algebra is even more fundamental than elementary algebra, which deals with numerical operations instead of logical ones.