Boolean Algebra

Propositions are denoted by italicized capital letters, such as \(A\), \(B\), \(C\), etc., and we require propositions to have an unambiguous objective meaning and be of simple definite logical type that must be either true or false.

The symbol

$$AB, \tag{1.6}$$

called the logical product or the conjunction, denotes the proposition "both \(A\) and \(B\) are true". The order \(AB\) or \(BA\) does not matter.

The expression

$$A+B, \tag{1.7}$$

called the logical sum or disjunction, stands for "at least one of the propositions, \(A\), \(B\) is true". It has the same meaning as \(B+A\). The introduced notation is only a shorthand of writing propositions, and do not stand for numerical values.

Two propositions with the same truth value are equally plausible, which is denoted by \(A=B\). The symbol \(\equiv\) means "equals by definition".

The order of combining propositions is the following:

  1. The expression in parentheses is evaluated first.
  2. The logical product of propositions is evaluated next.
  3. The logical sum of propositions is performed the last.

The denial of a proposition is denoted with a bar:

$$\overline A \equiv A \, \text{is false.} \tag{1.8}$$

Basic identities of Boolean algebra:

$$\begin{align} \text{Idempotence:}\quad &\begin{cases} AA = A\\ A+A = A \end{cases}\\[2ex] \text{Commutativity:}\quad &\begin{cases} AB = BA\\ A+B = B+A \end{cases}\\[2ex] \text{Associativity:}\quad &\begin{cases} A(BC) = (AB)C = ABC\\ A+(B+C) = (A+B)+C = A+B+C \tag{1.9} \end{cases}\\[2ex] \text{Distributivity:}\quad &\begin{cases} A(B+C) = AB + AC\\ A+(BC) = (A+B)(A+C) \end{cases}\\[2ex] \text{Duality:}\quad &\begin{cases} \text{If} \, C = AB, \, \text{then} \, \overline C = \overline A + \overline B\\ \text{If} \, D = A+B, \, \text{then} \, \overline D = \overline A \, \overline B\\ \end{cases}\\[2ex] \end{align}$$

The proposition

$$A \implies B \tag{1.10}$$

means "\(A\) implies \(B\)", and means only that \(A \overline B\) is false, or \((\overline A + B)\) is true. This can also be written as logical equation \(A = AB\).

If \(A\) is true then \(B\) must be true, or if \(B\) is false then \(A\) must be false; the same as in strong syllogisms (1.1) and (1.2). On the other hand, if \(A\) is false, (1.10) says nothing about \(B\), or if \(B\) is true, (1.10) says nothing about \(A\); this is where weak syllogisms (1.3) and (1.4) can be applied.