Basic Operations of Boolean Algebra

At the heart of Boolean algebra are three fundamental operations: NOT, AND, and OR. These operations are analogous to the basic connectors in logical reasoning and are implemented in digital circuits by corresponding logic gates.

1.2.1 The NOT Operation (Inversion)

The NOT operation is the simplest of the three. It operates on a single variable and inverts its value. If the input is 0, the output is 1, and if the input is 1, the output is 0. This is also known as inversion or complementation.

• Symbolic Representation: The NOT operation on a variable A is represented by a bar over the variable (Aˉ), a prime symbol (A′), or a tilde (~$A$). In this text, we will primarily use the bar notation, Aˉ.
• Truth Table: A truth table is a tabular representation of all possible inputs and the corresponding outputs of a logical operation.

A	Aˉ
0	1
1	0

• Logic Gate: The electronic circuit that performs the NOT operation is called an inverter or NOT gate.

1.2.2 The AND Operation

The AND operation combines two or more variables. The output of the AND operation is 1 only if all of its inputs are 1. If any input is 0, the output is 0.

• Symbolic Representation: The AND operation between two variables A and B is represented by a dot ($A\cdot B$), or more commonly, by simply placing the variables next to each other (AB).
• Truth Table:

A	B	$A\cdot B$
0	0	0
0	1	0
1	0	0
1	1	1

• Logic Gate: The circuit that performs the AND operation is called an AND gate.

1.2.3 The OR Operation

The OR operation also combines two or more variables. The output of the OR operation is 1 if at least one of its inputs is 1. The output is 0 only when all inputs are 0. This is also known as an inclusive OR.

• Symbolic Representation: The OR operation between two variables A and B is represented by a plus sign (A + B).
• Truth Table:

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

• Logic Gate: The circuit that performs the OR operation is called an OR gate.

Boolean Expressions and Functions

A Boolean expression is formed by combining Boolean variables with the basic logical operations. For example, F=ABˉ+C is a Boolean expression.

A Boolean function is an expression that specifies the relationship between a set of input variables and one or more output variables. The expression F(A,B,C)=ABˉ+C defines a function F with inputs A, B, and C. The value of the function can be determined for any combination of input values by substituting them into the expression and evaluating it according to the order of operations (precedence): NOT, then AND, then OR. Parentheses can be used to alter the order of evaluation.

Example 1.1: Evaluate the function F(A,B,C)=A+BˉC for $A=1,B=0,C=1$.

1. NOT: Evaluate Bˉ. Since $B=0$, Bˉ=1.
2. AND: Evaluate BˉC. $1\cdot 1=1$.
3. OR: Evaluate A+(BˉC). $1+1=1$.
4. Therefore, $F(1,0,1)=1$.