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

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

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

Пусть нам дана эта функция f(x1, x2, x3,...,xN) в виде таблицы истинности:

Таблица - http://vsst.3dn.ru/index/0-29

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

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

Si,j(xi) = xi, если Ai,j = 1; 
Si,j(xi) = ~xi, если Ai,j = 0; 

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

(S1,1(x1) & S2,1(x2) & S3,1(x3) & ... & SN,1(xN) & F1)  
 (S1,2(x1) & S2,2(x2) & S3,2(x3) & ... & SN,2(xN) & F2)  
 (S1,3(x1) & S2,3(x2) & S3,3(x3) & ... & SN,3(xN) & F3) ... (*) 
 (S1,M(x1) & S2,M(x2) & S3,M(x3) & ... & SN,M(xN) & FM) = 
= f(x1, x2, x3,...,xn)

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

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

Si,n(xi) = xi = Ai,n = 1, если Ai,n = 1; 
Si,n(xi) = ~xi = ~Ai,n = ~0 = 1, если Ai,n = 0. 

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

Si,n(xi) = 1 (1). 

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

S1,n(x) & S2,n(x) & S3,n(x) & ... & SN,n(xN) & Fn = Fn & 1 & 1 & 1 ... & 1 = Fn 

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

Ak,n ≠ Ak,m 

Отсюда: 

Sk,m(xk) = xk = Ak,m = 0, если Ak,n = 1; 
Sk,m(xk) = ~xk = ~Ak,m = ~1 = 0, если Ak,n = 0. 

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

Sk,m(xk) = 0 (2). 

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

S1,m(x1) & S2,m(x2) & ... & Sk,m(xk) & ... & SN,m(xN) & Fm = 
= S1,m(x1) & S2,m(x2) & ... & 0 & ... & SN,m(xN) & Fm = 
= ... & 0 & ... & Fm = 0 

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


(0)  
(0)  
... 
 (0)  
 (Fn)  
 (0)  
... 
 (0) =f(x1, x2, x3,...,xN)                        И по законам поглощения x 0 = x и 0x = x получаем:

00 ... 0 (Fn) 0 ... 0 = Fn = f(x1, x2, x3,...,xN)

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

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

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

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