Логические основы построения цифровых автоматов. Булевы формулы и функции. Количество булевых функций от n переменных. Существенные и фиктивные переменные. Эквивалентные функции. Двойственные функции. Принцип двойственности.

Булева функция (или логическая функция, или функция алгебры логики) от n аргументов — отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла.

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2^(2n).

Таблицы истинности

Булева функция задаётся конечным набором значений, что позволяет представить её в виде таблицы истинности, например

Нульарные функции

При n = 0 количество булевых функций сводится к двум 220 = 21 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
Таблица значений и названий нульарных булевых функций:

	Значение	Обозначение	Название
	0	F0,0 = 0	тождественный ноль
	1	F0,1 = 1	тождественная единица, тавтология

Унарные функции

При n = 1 число булевых функций равно 2^2^1 = 2^2 = 4. Определение этих функций содержится в следующей таблице.

Таблица значений и названий булевых функций от одной переменной:

x0=x	1	0	Обозначение	Название
0	0	0	F1,0 = 0	тождественный ноль
1	0	1	F1,1 = x = ¬x = x' = NOT(x)	отрицание, логическое "НЕТ", "НЕ", "НИ", инвертор, SWAP (обмен)
2	1	0	F1,2 = x	тождественная функция, логическое "ДА", повторитель
3	1	1	F1,3 = 1	тождественная единица, тавтология

Бинарные функции

При n = 2 число булевых функций равно 2^2^2 = 2^4 = 16.

Тернарные функции

При n = 3 число булевых функций равно 2^(2^3) = 2^8 = 256 (скобки нужны, так как запись a^n^m не обладает свойством ассоциативности (сочетательности) и (2^2)^3 = 4^3 = 64).

Фиктивные переменные

Определение. Говорят, что булева функция f(x₁, …, x_i, …, x_n) существенно зависит от переменной x_i, если выполняется условие

f(x₁, …, x_i-1,0,x_i+1, …, x_n) ≠ f(x₁, …, x_i-1,1,x_i+1, …, x_n).

В этом случае также говорят, что переменная x_i существенная, в противном случае ее называют фиктивной переменной.

Пример. Рассмотрим булеву функцию f(x₁, x₂, x₃) и исследуем ее переменные x₁ и x₃.

Из таблиц истинности видно, что переменная x₁ функции f(x₁, x₂, x₃) существенная, так как f(0,x₂, x₃) ≠ f(1,x₂, x₃). Переменная x₃ фиктивная, так как f(x₁, x₂, 0) = f(x₁, x₂, 1). •

Очевидно, что для выявления фиктивных переменных можно не строить в явном виде таблиц истинности левой и правой частей неравенства, а сравнивать соответствующие части вектора-столбца значений функции.

Алгоритм распознавания фиктивной переменной по таблице истинности.

– Для переменной x₁ сравниваются половины столбца значений функции: верхняя и нижняя, так как именно в верхней половине x₁=0, а в нижней x₁=1, если они совпадают, то переменная x₁ фиктивна;

– для переменной x₂ сравниваются четвертины столбца в каждой половине, так как именно в верхних четвертинах x₂ =0, а в нижних x₂ =1, если четвертины в каждой половине совпадают, то переменная x₂ фиктивна;

– и так далее (за четвертинами следуют 1/8, 1/16, … ).

Эквивалентные функции

Две булевы функции тождественны(эквивалентны) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.