Мы изучили булевы функции от 1 и 2 аргументов. Рассмотрим теперь функции от произвольного числа аргументов. Оказывается, что любую булеву функцию от любого числа аргументов можно представить в виде комбинации функций от 1 и 2 аргументов. Этот важный факт позволяет, например, обойтись в сложных микросхемах лишь несколькими элементами, а на их основе строить любые другие логические схемы.

Совершенная дизъюнктивная нормальная форма (СДНФ)

Докажем, что всякую логическую функцию от N аргументов можно выразить через операции &, , ~ и константы 0 и 1. По ходу доказательства покажем, по какому именно алгоритму это делается. В принципе, вы можете пропустить этот параграф и сразу перейти к рассмотрению примера составления СДНФ. Вернитесь к доказательству, если захочется понять в деталях, каким образом работает СДНФ.

Пусть нам дана эта функция f(x₁, x₂, x₃,...,x_N) в виде таблицы истинности:

x1	x2	x3	...	xN	f(x1, x2, x3,...,xN)
A1,1	A2,1	A3,1	...	AN,1	F1
A1,2	A2,2	A3,2	...	AN,2	F2
...	...	...	...	...	...
A1,j	A2,j	A3,j	...	AN,j	Fj
...	...	...	...	...	...
A1,M	A2,M	A3,M	...	AN,M	FM

В таблице A_i,j - константы 0 или 1, определяющие значения аргументов; F_j - константы 0 или 1, определяющие значения функции для данной комбинации аргументов; M = 2^N - количество всех возможных комбинаций.

Определим функции от 1 аргумента:

S_i,j(x_i) = x_i, если A_i,j = 1;
S_i,j(x_i) = ~x_i, если A_i,j = 0;

Тогда исходная функция может быть представлена в виде:

(S_1,1(x₁) & S_2,1(x₂) & S_3,1(x₃) & ... & S_N,1(x_N) & F₁)
(S_1,2(x₁) & S_2,2(x₂) & S_3,2(x₃) & ... & S_N,2(x_N) & F₂)
(S_1,3(x₁) & S_2,3(x₂) & S_3,3(x₃) & ... & S_N,3(x_N) & F₃) ...             (*)
(S_1,M(x₁) & S_2,M(x₂) & S_3,M(x₃) & ... & S_N,M(x_N) & F_M) =
= f(x₁, x₂, x₃,...,x_N)

Как видите, она выражена только через функции , ~ и &. Каждая строка в нашем правиле (*) соответствует строке таблицы.

Осталось доказать, что левая часть (*) действительно равна исходной функции. Возьмем произвольную n-ю строку таблицы. Убедимся, что значение функции F_n действительно равно значению левой части (*) когда значения аргументов равны значениям, указанным в этой строке: x_i = A_i,n для i = 1, 2, 3,..., N.

S_i,n(x_i) = x_i = A_i,n = 1, если A_i,n = 1;
S_i,n(x_i) = ~x_i = ~A_i,n = ~0 = 1, если A_i,n = 0.

То есть, для выбранного n и для любого i верно:

S_i,n(x_i) = 1    (1).

Берем в (*) n-ю строку, подставляем в нее (1) и применяем закон поглощения x & 1 = x:

S_1,n(x₁) & S_2,n(x₂) & S_3,n(x₃) & ... & S_N,n(x_N) & F_n = F_n & 1 & 1 & 1 ... & 1 = F_n

Теперь берем в (*) любую другую строку, кроме n-й. Пусть она имеет номер m. Поскольку все строки таблицы содержат разные наборы A_i,j, то хотя бы в одном столбце будет различие. Пусть различие содержится в k-м столбце:

A_k,n ≠ A_k,m

Отсюда:

S_k,m(x_k) = x_k = A_k,m = 0, если A_k,n = 1;
S_k,m(x_k) = ~x_k = ~A_k,m = ~1 = 0, если A_k,n = 0.

То есть, для выбранных k и m верно:

S_k,m(x_k) = 0    (2).

Берем в (*) m-ю строку, подставляем в нее (2) и применяем законы поглощения x & 0 = 0 и 0 & x = 0:

S_1,m(x₁) & S_2,m(x₂) & ... & S_k,m(x_k) & ... & S_N,m(x_N) & F_m =
= S_1,m(x₁) & S_2,m(x₂) & ... & 0 & ... & S_N,m(x_N) & F_m =
= ... & 0 & ... & F_m = 0

Таким образом, значение всех строк СДНФ, кроме n-й равно 0 за счет нуля, который дает хотя бы одно различие в наборах аргументов. И лишь n-я строка равна F_n.

В результате получаем:

(0)
(0)
...
(0)
(F_n)
(0)
...
(0) =
= f(x₁, x₂, x₃,...,x_N)

И по законам поглощения x 0 = x и 0 x = x получаем:

0 0 ... 0 (F_n) 0 ... 0 = F_n = f(x₁, x₂, x₃,...,x_N)

Мы рассматривали произвольную n-ю строку таблицы и убедились, что для набора аргументов, записанного в этой строке, значение функции совпадает со значением левой части (*). Точно такое же рассуждение можно повторить для всех остальных строк, сколько бы их ни было. Таким образом, значение функции совпадает с левой частью (*) для всех возможных наборов аргументов. Что и требовалось доказать.

В формуле (*) строки, в которых F_j = 0 можно опустить, благодаря законам поглощения: x & 0 = 0, x 0 = x и 0 x = x. А в строках, в которых F_j = 1 можно опустить F_j, благодаря закону поглощения: x & 1 = x.

После этих сокращений получается запись, которая и называется совершенной дизъюнктивной нормальной формой (СДНФ).

Пример составления СДНФ.

Составим СДНФ для функции, которая приводилась ранее в качестве примера.

x	y	z	f(x, y, z)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Составляем СДНФ таким образом: для каждой строки с единицей в крайнем правом столбце образуем скобки и объединяем их операцией . В каждую скобку вставляем последовательность из простых элементов, объединенных операцией &: для ячейки таблицы, где проставлена 1, пишем переменную-аргумент, а для каждой ячейки, где проставлен 0, пишем переменную-аргумент со знаком ~ перед ним:

f(x,y,z) = (~x & y & z) (x & ~y & ~z) (x & y & ~z)

СДНФ можно упрощать и далее, для чего существуют разные методы, в том числе метод под названием "карты Карно", построенный на наглядных зрительных образах. Все эти методы основаны на правилах упрощения:

(a & b & c) (a & ~b & c) = a & c
(a & b) (a & ~b) = a
(b & c) (~b & c) = c

То есть, если в СДНФ обнаруживаются две скобки, которые отличаются только знаком ~ перед одним из элементов, их можно заменить на одну скобку, в котором этого элемента нет. Например, полученную выше формулу можно упростить по этому правилу, объединив две последние скобки в одну:

f(x,y,z) = (~x & y & z) (x & ~z)