Mathematical Logic - Part 2

In the previous entry, we examined the foundations of mathematical logic. Now, let us explore the axioms of Boolean algebra, accompanied by derivations—because I believe that understanding is greatly enhanced when we can see the derivations and understand how each element follows from the others.

Axioms of Boolean algebra

I think it’s important to first explain the meaning of the term “axiom.” An axiom refers to a self-evident truth that is accepted as fundamental within a given framework, which means it does not require proof or further explanation —much like the fact that none of my cats can operate a submarine. However, I believe a more profound understanding is achieved when one can see the proof behind a concept. We have a total of 11 axioms to explore in mathematical logic, but don’t worry; none of them are difficult; they are almost self-evident

I. Axiom – Associativity law

This axiom can be expressed in two forms:

Form 1: $\displaystyle A+ \left( B+C \right)=\left( A+B \right)+C$
Form 2: $\displaystyle A\cdot \left( B \cdot C \right)=\left( A\cdot B \right) \cdot C$

Associativity signifies the ability to group expressions, meaning you can re-parenthesize without affecting the result! For our proof, I’ll be using Form 2. Let’s dive into the truth table—it’s about to get thrilling with three terms! These are simple multiplications, and I’ll detail each step along the way.

The task: $\displaystyle A\cdot \left( B \cdot C \right) \stackrel{?}{=} \left( A\cdot B \right) \cdot C$

Options	$A$	$B$	$C$	$\displaystyle \left(b \cdot c \right)$	$\displaystyle \left(a \cdot b \right)$	$\displaystyle \left(b \cdot c \right) \cdot a$	$\displaystyle \left(a \cdot b \right) \cdot c$
1	$0$	$0$	$0$	$0 \cdot 0 = 0$	$0 \cdot 0 =0$	$0 \cdot 0 =0$	$0 \cdot 0 = 0$
2	$0$	$0$	$1$	$0 \cdot 1= 0$	$0 \cdot 0 =0$	$0 \cdot 0 =0$	$0 \cdot 1= 0$
3	$0$	$1$	$0$	$1\cdot 0= 0$	$0 \cdot 1 =0$	$0 \cdot 0 =0$	$0 \cdot 0 = 0$
4	$0$	$1$	$1$	$1\cdot 1= 1$	$0 \cdot 1 =0$	$0 \cdot 1 =0$	$0 \cdot 1= 0$
5	$1$	$0$	$0$	$0\cdot 0= 0$	$1 \cdot 0 =0$	$1 \cdot 0 =0$	$0 \cdot 0 = 0$
6	$1$	$0$	$1$	$0\cdot 1= 0$	$1 \cdot 0 =0$	$1 \cdot 0 =0$	$0 \cdot 1= 0$
7	$1$	$1$	$0$	$1\cdot 0= 0$	$1 \cdot 1 =1$	$1 \cdot 0 =0$	$1 \cdot 0 =0$
8	$1$	$1$	$1$	$1\cdot 1= 1$	$1 \cdot 1 =1$	$1 \cdot 1 =1$	$1 \cdot 1 =1$

If you’ve now examined the last two columns of the table, you will notice that they are completely identical, which means we have successfully proven the form $A \cdot (B \cdot C) = (A \cdot B) \cdot C \ \blacksquare$ . The Hungarian-American mathematician Paul Halmos introduced the symbol ( $\blacksquare$ ) at the end of the proof (1916-2006). I will include this symbol at the conclusion of every derivation. The proof of the form ( A + (B + C) = (A + B) + C ) can be demonstrated in a similar manner.

II. Axiom – Commutativity law

Translated into English, this means that the order of the individual factors in an expression can be swapped without changing the result! How exciting! We can represent this axiom in two forms:

Form 1: $\displaystyle A+B=B+A$
Form 2: $\displaystyle A \cdot B = B \cdot A$

Now, let’s prove the following statement:

$\displaystyle ( A + B \stackrel{?}{=} B + A )$

Options	$A$	$B$	$A+B$	$B+A$
1	$0$	$0$	$1$	$1$
2	$0$	$1$	$1$	$1$
3	$1$	$0$	$1$	$1$
4	$1$	$1$	$1$	$1$

The last two columns of the table are equal, which means we have successfully proven that: $\displaystyle A + B = B + A \blacksquare$

III. Axiom – Distributivity law

Multiplication is distributive over addition, meaning you can break down the parentheses—logic multiplication distributes across its terms, while logical addition is performed on each factor separately. This fundamental axiom exists in two forms:

Form 1: $\displaystyle A+\left( B\cdot C \right)=\left( A+B \right) \cdot \left( A+C \right)$
Form 2: $\displaystyle A+\left( B\cdot C \right)=\left( A \cdot B \right) + \left( A \cdot C \right)$

Okay, now prove the Form 1: $\displaystyle A+\left( B\cdot C \right) \stackrel{?}{=}\left( A+B \right) \cdot \left( A+C \right)$

For the sake of simplicity, let’s use the following designations: $\displaystyle A+\left( B\cdot C \right) \longrightarrow Y_1$ and $\displaystyle \left( A+B \right) \cdot \left( A+C \right) \longrightarrow Y_2$

Options	$A$	$B$	$C$	$\left( B \cdot C \right)$	$Y_1$	$\left( A + B \right)$	$\left( A + C \right)$	$Y_2$
1	$0$	$0$	$0$	$0 \cdot 0=0$	$0 + 0=0$	$0 + 0=0$	$0 + 0=0$	$0 \cdot 0=0$
2	$0$	$0$	$1$	$0 \cdot 1=0$	$0 + 0=0$	$0 + 0=0$	$0 + 1=1$	$0 \cdot 1=0$
3	$0$	$1$	$0$	$1 \cdot 0=0$	$0 + 0=0$	$0 + 1=1$	$0 + 0=0$	$1 \cdot 0=0$
4	$0$	$1$	$1$	$1 \cdot 1=1$	$0 + 1=1$	$0 + 1=1$	$0 + 1=1$	$1 \cdot 1=1$
5	$1$	$0$	$0$	$0 \cdot 0=0$	$1 + 0=1$	$1 + 0=1$	$1 + 0=1$	$1 \cdot 1=1$
6	$1$	$0$	$1$	$0 \cdot 1=0$	$1 + 0=1$	$1 + 0=1$	$1 + 1=1$	$1 \cdot 1=1$
7	$1$	$1$	$0$	$1 \cdot 0=0$	$1 + 0=1$	$1 + 1=1$	$1 + 0=1$	$1 \cdot 1=1$
8	$1$	$1$	$1$	$1 \cdot 1=1$	$1 + 1=1$	$1 + 1=1$	$1 + 1=1$	$1 \cdot 1=1$

Tbe column 6 are 9 identical, therefore $\displaystyle A+\left( B\cdot C \right) = \left( A+B \right) \cdot \left( A+C \right) \blacksquare$

Note: the $1+1=1$ is not a type; rather a speciality of Boolean algebra. Do not interpret 1 is an ordinary number – instead, consider it as representing FALSE (0) and TRUE (1) values

IV. Axiom – Complementation law

The word “complement” refers to the logical negation—that is, a statement that an TRUE assertion cannot exist without its FALSE counterpart. This principle can also be expressed in two forms:

Form 1: $A \cdot \overline{A}=0$
Form 2: $A + \overline{A}=1$

The proof:

Options	$A$	$\overline{A}$	$A \cdot \overline{A}$	$A + \overline{A}$
1	$0$	$1$	$0 \cdot 1 =0$	$0 +1 = 1$
2	$1$	$0$	$1 \cdot 0 =0$	$1+0 = 1$

The last two columns of the table show opposing results as options, and that was our goal. $\blacksquare$

V. Axiom – Idempotency law

Put simply, it means that I have two sets, and both contain exactly the same elements. When I take the union or intersection of these two sets—these are two-variable expressions—I always obtain the same result every time.

Form 1: $A \cdot A=A$
Form 2: $A + A =A$

The proof:

Options	$A$	$A \cdot A$	$A +A$
1	$0$	$0 \cdot 0 = 0$	$0 +0 =0$
2	$1$	$1 \cdot 1 = 1$	$1 +1 =1$

The last two columns of the table are equal to the value of $A$ in both cases, and this is what we set out to prove. $\blacksquare$

VI. Axiom – Identity law

Form 1: $A \cdot 1=A$
Form 2: $A + 0 =A$

The proof:

Options	$A$	$A \cdot 1$	$A +0$
1	$0$	$0 \cdot 1 = 0$	$0 +0 =0$
2	$1$	$1 \cdot 1 = 1$	$1 +1 =1$

The last two columns of the table are equal to the value of $A$ in both cases, and this is what we set out to prove. $\blacksquare$

VII. Axiom – Annulment law

Form 1: $A \cdot 0=0$
Form 2: $A + 1 =1$

The proof:

Options	$A$	$A \cdot 0=0$	$A + 1 =1$
1	$0$	$0 \cdot 0 = 0$	$0 +1 =1$
2	$1$	$1 \cdot 0 = 0$	$1 +1 =1$

The last two columns of the table are equal to the value of $A$ in both cases, and this is what we set out to prove. $\blacksquare$

Note: This identity can also be applied when simplifying an expression like $A \left(1+ B+C… \right)$ later on. Observe that, because of the second form, the part inside the parentheses will always be equal to 1. Therefore, the expression simplifies to the form $A \left(1\right)$ .

VIII. Axiom – Complement law

Law 1: $\displaystyle \overline{0}=1$
Law 2: $\displaystyle \overline{1}=0$

Therefore $0$ and 1 are complement results.

IX. Axiom – Absorption law

This is a bit more complex than the previous ones. Absorption here means that we can remove redundant terms from the expression, simplifying the problem without changing the final result. As before, this principle can be expressed in two forms:

Form 1: $\displaystyle A+\left(A \cdot B \right)=A$
Form 2: $\displaystyle A\cdot \left(A + B \right)=A$

The proof:

Options	$A$	$B$	$\displaystyle \left( A \cdot B \right)$	$\displaystyle \left( A + B \right)$	$\displaystyle A \cdot \left( A \cdot B \right)$	$\displaystyle A+\left( A \cdot B \right)$
1	$0$	$0$	$0$	$0$	$0$	$0$
2	$0$	$1$	$0$	$1$	$0$	$0$
3	$1$	$0$	$0$	$1$	$1$	$1$
4	$1$	$1$	$1$	$1$	$1$	$1$

Notice that $A$ , $\displaystyle A+\left(A \cdot B \right)=A$ and $\displaystyle A\cdot \left(A + B \right)=A$ are equal. $\blacksquare$

Note 1: $\displaystyle B+\left(A +B \right)=B$ and $\displaystyle B\cdot \left(A + B \right)=B$ can be quickly proved using a truth table
Note 2: The equation $\displaystyle A\cdot \left(AB + ABC+… \right)=A$ can be derived in the same way. All we need to do is factor out $A$ and transforming the expression into: $\displaystyle A\cdot \left(1 + B+BC… \right)=A$ . At this point, the VI. axiom comes into play, which states that the value inside the parentheses is 1 – that is $\displaystyle A\cdot \left(1\right)=A$

In addition to the logical proof, you should also demonstrate the absorption axiom using a truth table. Since there are two variables $A$ and $B$ , there are a total of 4 possible combinations for each form, so the total number of variations across all expressions is 32…

$\displaystyle Y_1 \rightarrow A+\left( A \cdot B \right)=A$ and $\displaystyle Y_2 \rightarrow B+\left( A \cdot B \right)=B$ expressions:

Options	$Y_1$	$Y_2$
1	$\displaystyle A + \left( A \cdot B \right)=A$	$\displaystyle B + \left( A \cdot B \right)=B$
2	$\displaystyle \overline{A} + \left( A \cdot B \right)=\overline{A}+B$	$\displaystyle \overline{B} + \left( A \cdot B \right)=\overline{B}+A$
3	$\displaystyle A + \left( \overline{A} \cdot B \right)=A+B$	$\displaystyle B + \left( \overline{B} \cdot A \right)=A+B$
4	$\displaystyle \overline{A} + \left( \overline{A} \cdot B \right)=\overline{A}$	$\displaystyle \overline{B} + \left( \overline{B} \cdot A \right)=\overline{B}$
5	$\displaystyle A + \left( A \cdot \overline{B} \right)=A$	$\displaystyle B + \left( B \cdot \overline{A} \right)=B$
6	$\displaystyle A + \left( \overline{A} \cdot \overline{B} \right)=A+\overline{B}$	$\displaystyle B + \left( \overline{A} \cdot \overline{B} \right)=B+\overline{A}$
7	$\displaystyle \overline{A} + \left( A \cdot \overline{B} \right)=\overline{A} + \overline{B}$	$\displaystyle \overline{B} + \left( B \cdot \overline{A} \right)=\overline{A} + \overline{B}$
8	$\displaystyle \overline{A} + \left( \overline{A} \cdot \overline{B} \right)=\overline{A}$	$\displaystyle \overline{A} + \left( \overline{A} \cdot \overline{B} \right)=\overline{B}$

$\displaystyle Y_1 \rightarrow A\left( A+B \right)=A$ and $\displaystyle Y_2 \rightarrow B\left( A+B \right)=B$ expressions:

Options	$Y_1$	$Y_2$
1	$\displaystyle A \cdot \left( A + B \right)=A$	$\displaystyle B \cdot \left( A + B \right)=B$
2	$\displaystyle \overline{A} \cdot \left( A+ B \right)=\overline{A} \cdot B$	$\displaystyle \overline{B} \cdot \left( A+ B \right)=\overline{B} \cdot A$
3	$\displaystyle A \cdot \left( \overline{A} + B \right)=A \cdot B$	$\displaystyle B \cdot \left( \overline{B} + A \right)=B \cdot A$
4	$\displaystyle \overline{A} \cdot \left( \overline{A} + B \right)=\overline{A}$	$\displaystyle \overline{B} \cdot \left( \overline{B} + A \right)=\overline{B}$
5	$\displaystyle A \cdot \left( A \cdot \overline{B} \right)=A$	$\displaystyle B \cdot \left( B \cdot \overline{A} \right)=B$
6	$\displaystyle A \cdot \left( \overline{A} + \overline{B} \right)=A \cdot \overline{B}$	$\displaystyle B \cdot \left( \overline{A} + \overline{B} \right)=B \cdot \overline{A}$
7	$\displaystyle \overline{A} \cdot \left( A + \overline{B} \right)=\overline{A} + \overline{B}$	$\displaystyle \overline{B} \cdot \left( B + \overline{A} \right)=\overline{A} + \overline{B}$
8	$\displaystyle \overline{A} \cdot \left( \overline{A} \cdot \overline{B} \right)=\overline{A}$	$\displaystyle \overline{B} \cdot \left( \overline{A} \cdot \overline{B} \right)=\overline{B}$

X. Axiom – Double negation law

This one looks like this: $\neg \neg A = A$ .

The proof:

Options	$A$	$\overline{A}$	$\neg \neg {A}$
1	$0$	$1$	$0$
2	$1$	$0$	$1$

The truth table clearly shows that after applying double negation, we regain the original statement $A$ . $\blacksquare$

XI. Axiom – De Morgan law

Identity 1: $\displaystyle \overline{A \cap B} \stackrel{?}{=} \overline{A} \cup \overline{B}$ let’s rewrite it into: $\displaystyle \overline{A \cdot B} \stackrel{?}{=} \overline{A} + \overline{B}$
Identity 2: $\displaystyle \overline{A \cup B} \stackrel{?}{=} \overline{A} \cap \overline{B}$ and we rewrite it this one too: $\displaystyle \overline{A + B} \stackrel{?}{=} \overline{A} \cdot \overline{B}$

You did it! The only two things left are understanding the order of operations AND practicing it.

Order of Operations in Boolean Algebra

The order of operations is not only critically important in Boolean algebra but across all of mathematics. You’ve probably seen various posts online claiming that only “geniuses” can solve equations with parentheses. To be honest, I don’t know how long the measurement of genius has been so low that such claims are made. Anyway, the order of operations — it’s not just mathematical logic:

Parentheses
Negation
AND (Conjunction)
OR (Disjunction)

Most often, you’ll be given an expression $Y$ , which you need to simplify as much as possible. In this section, you have all the necessary information to solve such logic problems. It’s not complicated if the basics are clear and you have a routine for solving these tasks. In the next part, I’ll provide exercises related to almost every example.

If you’re heading towards electrical engineering, it gets even more complex with circuit diagrams — many inputs, switches, and then you need to draw the simplest circuit. The point of this is to use the fewest circuit components possible.

Problem-Solving Strategy

Write down all the operations and axioms on a sheet of paper — this will be helpful when doing mathematical logic tasks — it makes debugging much easier.
Absorption rule — become a master of it; you can save a lot of time, which is very useful during exams and quizzes.
Work cleanly, mark everything clearly!
Avoid using the $x$ symbol for multiplication — you might accidentally introduce an extra variable along the way.
Write the terms in alphabetical order: A, B, C, and so on.
Work from the inside out — perform all operations inside parentheses first, following the order of operations, and only then remove the parentheses.

Exercises for the mathematical logic part will be provided in the next post.