Boolean functions and their construction

Boolean functions perform logical operations on truth values—true and false. This branch of mathematics helps programmers describe the logic of algorithms.

Boolean functions are a mathematical way of describing logical operations. They are named after the British mathematician George Boole, who in the mid-19th century founded the field of mathematical logic—Boolean algebra. While conventional mathematical operations are performed on real numbers, Boolean algebra works with truth values: true and false. In the binary number system used in programming, these are represented by the numbers 1 and 0.

A simple example of a Boolean function: imagine a smart home program that controls lighting. To understand the state of a switch, the program uses logical values. If the light is on, the switch’s state in the program will be 1, or true. If it’s off, it will be 0 or false. Receiving a true or false answer based on the condition “Is the light on?” is the simplest Boolean function.

Boolean functions have inputs—the operands—and an output—the result. For example, there are light switches in two rooms and a hallway. To turn off the light in the hallway when the lights in both rooms are off, the smart home program needs to use the Boolean AND function. This function takes the values ​​from the room switches—the inputs: if both are off (false and false), the output will also be false, and then the light in the hallway will also turn off.

What Boolean functions are commonly used in programming:

● AND — conjunction. Returns true if both outputs are true.

● OR — disjunction. Returns true if at least one of the outputs is true.

● NOT — NOT, negation, inversion. Inverts the value of the input: if the input was true, returns false, and vice versa.

● ID — identity. Returns the input value unchanged. True remains true, and false remains false.

● XOR – exclusive OR. Returns true if only one of the outputs was true.

● IF, THEN — “if…, then…”, implication. Defines the relationship between the premise and the consequent. Returns the consequent true if the premise is true. If the premise is false, the consequent can be either false or true.

● NAND — NAND-NOT. Inverts the result of the AND function; that is, it returns false only if both inputs are true.

● NOR — OR-NOT. Inverts the result of the OR function; that is, it returns true only if both inputs are false.

● XNOR — exclusive OR-NOT. Returns true if both inputs are the same, that is, both are true, or both are false.

Understanding Boolean functions is taught in the course for analysts. Students study linear algebra, mathematical analysis, probability theory, statistics, and more. Suitable for those who want to develop in data science.

The operation of Boolean functions is illustrated using truth tables. They help understand the output of a Boolean function for all possible inputs and ensure that the functions used lead to the correct results. Let’s look at the truth tables for the three main types of Boolean functions:

1. AND — conjunction. Returns true if both outputs are true. The rows of the table indicate all possible combinations of input values ​​A and B. The third column indicates the result of these combinations with the Boolean AND function, also known as conjunction or logical multiplication. Logical multiplication of inputs A and B is denoted by the symbol ∧.

The truth table of the AND function shows that the output 1 (true) is only possible when both outputs are also 1 (true). If at least one input is 0 (false), the output will also be 0 (false).

2. OR — disjunction. Returns true if at least one of the outputs is true. The OR function in Boolean algebra is also called disjunction or logical addition. The logical addition of inputs A and B is denoted by the symbol ∨.

The output of the OR function is 1 if at least one of the inputs is 1. When the values ​​of input A and input B are both 0, the result of the logical addition will also be 0.

3. NOT — negation, inversion. Inverts the value of the input: if the input was true, it returns false, and vice versa. The Boolean NOT function — also known as negation or inversion — has only one input; the function changes its value to the opposite.

Function superposition is the combination of several Boolean functions in complex logical operations. Superposition allows for the creation of complex algorithms that employ multiple conditions that change the values ​​of the inputs. Essentially, superposition is the sequential application of different functions to the initial inputs.

Let’s say we’re given a Boolean function (A AND B) OR (C AND D). This operation has four inputs: A, B, C, and D. As in regular mathematics, we first perform the AND operations within the parentheses to obtain new outputs, and then OR them.

Truth table for the function (A AND B) OR (C AND D):

The result of superposition is the application of the OR function to the inputs resulting from the AND operations on the pairs of inputs A, B, and C, D.

In Boolean algebra, every Boolean function has its own dual function, which is obtained from the original by inverting or replacing OR with AND and vice versa. Examples of dual functions:

● OR — OR and AND — AND;
● XOR — exclusive OR and XNOR — exclusive NOR-NOT;
● NOT — NOT and ID — identity;
● NAND — NAND-NOT and NOR — NOR-NOT.

Dual functions in programming help optimize computations. For example, if an algorithm requires calculating a logical function, it is sometimes more efficient to calculate its dual, especially if it has a simpler form. This can lead to improved performance or a reduction in the number of operations.

Minimization, or decomposition of a function into variables, allows one to represent a complex Boolean function as a combination of simpler functions, each dependent on a single variable. There are several methods for decomposing functions into variables:

● Karnaugh map method. The approach is based on transforming the truth tables of Boolean functions. The table cells are divided into rectangles to combine adjacent ones. The values ​​in the resulting rectangles are the variables of the simplified logical expression of the function.

● Shannon decomposition. The essence of the method is to divide the truth table into two parts: one should contain inputs for which the variable takes the value 1, the other – for which it takes the value 0. As a result, the Boolean function takes the form of the sum of two subfunctions.

● Quine’s method. It involves two stages: first, the function is reduced to a reduced form using the operations of gluing and absorption. Second, the reduced function is reduced to a minimum by removing variables that do not affect the result of the original function.

● Quine-McCluskey Method. This approach simplifies the standard Quine method. It involves fewer gluing operations by initially dividing the truth table into regions with an equal number of zeros or ones.

● Blake-Poretsky method. The method is based on the transformation of the truth table of a function into Gray matrices, which represent ternary vectors.