Теорема.

Каждая булева функция является суперпозицией следующих функций: отрицания, конъюнкции и дизъюнкции.

Доказательство:

Первое доказательство.

Обозначим множество всех булевых функций через P₂. Если данная функция f P₂ является константой, равной нулю, то, согласно соотношению 0 = ù (x ù x) или 0 = x ù x, утверждение справедливо. В противном случае, существуют такие наборы (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n)=1. Для каждого такого набора (a_1, a₂,…, a_n) образуем элементарную конъюнкцию , которая имеет значение 1 только на наборе (a_1, a₂,…, a_n). Тогда

f(x_1, x₂,…, x_n) =, (3)

где дизъюнкции берётся по всем таким наборам (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n) = 1. Так как правая часть равенства (3) является суперпозицией требуемых функций, то теорема доказана.

Второе доказательство.

Если функция f P₂ является константой равной 1, то, согласно 1= x ù x или 1=ù (x ù x), утверждение справедливо. В противном случае, существуют такие наборы (a_1, a₂,…, a_n), что f(a_1, a₂,…, a_n)  1, или, что то же самое, f(a_1, a₂,…, a_n) = 0. Таким образом, функция f(x_1, x₂,…, x_n) может быть представлена в виде

f(x_1, x₂,…, x_n) = , (4)

где конъюнкция берётся по всем таким наборам (a_1, a₂,…, a_n), что

f(a_1, a₂,…, a_n)=0. Правая часть равенства (4) опять, как и в первом доказательстве, является суперпозицией требуемых функций. Теорема доказана.

Определение.

Правая часть равенства (3) называется совершенной дизъюнктивной нормальной формой (кратко СДНФ) функции f(x_1, x₂,…, x_n).

Замечание.

СДНФ существует только для тех булевых функций, которые не являются константами, равными нулю.

Определение.

Правая часть равенства (4) называется совершенной конъюнктивной нормальной формой (СКНФ) функции f(x_1, x₂,…, x_n).

Замечание.

СКНФ существует только для тех булевых функций, которые не являются константами, равными единице.

Определение.

Конъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается буквой K с соответствующим индексом. Индексом в обозначении служит номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной x_i символом 1, а переменной ù x_i – символом 0.

Определение.

Дизъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается (в литературе) буквой D с соответствующим индексом. Индексом служит инверсионный номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной x_i символом 0, а переменной ù x_i – символом 1.

Примеры.

1. x₁x₂ – номер набора –11₂ = 3₁₀, полная конъюнкция обозначается K₃.

2. – номер набора – 010₂ = 2₁₀, полная конъюнкция обозначается K₂.

3. x₁ x₂ – номер инверсионного набора – 00₂ – 0₁₀, полная дизъюнкция обозначается D₀.

4. – номер инверсионного набора – 101₂ – 5₁₀, полная дизъюнкция обозначается D₅.

Определение.

Полная конъюнкция, принимающая значение 1 только на одном наборе аргументов, соответствующем её индексу, и значение 0 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией единицы.

Определение.

Полная дизъюнкция, принимающая значение 0 только на одном наборе аргументов, соответствующем её индексу, и значение 1 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией нуля.

Замечание.

Значение булевой функции для конкретных значений аргументов удобно обозначить символом  с индексом в виде десятичного числа, соответствующего двоичному набору аргумента, например, f(1,1) = ₃, f(1,0,1) = ₅.

Примеры.

С учётом введённых определений булеву функцию f(x_1, x₂) можно записать {с учетом разложения в СДНФ или СКНФ} в следующем виде:

.

Замечание.

Приведенный пример показывает, каким образом можно перейти от табличного представления булевой функции к её аналитическому представлению. При табличном представлении функции задаются её значения _i для каждого набора аргументов, определяемого индексом i. Так как в силу определения операции конъюнкции имеем 0K_i = 0 и 1K_i = K_i, то для представления функции в виде СДНФ нужно выписать дизъюнкцию всех тех конституэнт единицы K_i, для которых _i = 1. Учитывая также, что 0D_i=D_i и 1D_i=1, СКНФ получается как конъюнкция всех тех конституэнт нуля D_i, для которых значение функции _i равно 0.

3. Законы двойственности.

Определение.

Учитывая определённую симметрию операций  и  в аксиоматике алгебры Буля логических высказываний и операций, операции  и  называются двойственными.

Определение.

Формулы и ^* называются двойственными, если одна получается из другой заменой каждой операции на двойственную.

Примеры.

1. двойственна .

2. двойственна .

3. двойственна .

Замечание.

Как для операций, так и для формул отношение двойственности взаимно, то есть если ^* двойственна , то и, наоборот, двойственна ^*.

Лемма.

Если формулы (X₁, X₂,…, X_n) и ^*(X₁, X₂,…, X_n) двойственны, а X₁, X₂,…, X_n – все входящие в них элементарные высказывания, то (X₁, X₂,…, X_n) равносильна ^*.

Доказательство:

Доказательство непосредственно следует из законов де Моргана.

Следствие из леммы.

Частным случаем леммы являются следующие соотношения:

; (5)

. (6)

Они являются обобщением законов де Моргана и называются законами Клода Шеннона.

Задание.

Доказать законы Клода Шеннона и лемму.

Теорема (закон двойственности).

Если и равносильны, то и двойственные им формулы ^*и ^* также равносильны.

Доказательство:

Пусть (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) – равносильные формулы, а X₁, X₂,…, X_n – входящие в них элементарные высказывания. Тогда, в силу леммы, ^*(X₁, X₂,…, X_n) равносильна , а^*(X₁, X₂,…, X_n) равносильна .

Из равносильности формул (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) следует равносильность формул и , так как в силу определения равносильности (X₁, X₂,…, X_n) и (X₁, X₂,…, X_n) принимают одинаковые значения при любых значениях переменных X₁, X₂,…, X_n, а, следовательно, и при значениях . Следовательно, формулы и также равносильны, далее, в силу леммы формула ^*(X₁, X₂,…, X_n) равносильна формуле , а формула ^*(X₁, X₂,…, X_n) равносильна формуле . Следовательно, формулы ^*(X₁, X₂,…, X_n) и ^*(X₁, X₂,…, X_n) равносильны между собой, что и требовалось доказать.