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

В том числе любую булеву функцию можно выразить в виде дизъюнктивной формы. Существует простой метод построения такой формулы по таблице истинности. Результат построения называется "совершенной дизъюнктивной нормальной формой" (СДНФ).

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

Пусть нам дана произвольная булева функция 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 - константы false или true, определяющие значения переменных; F_j - константы false или true, определяющие значения функции для данной комбинации переменных; M = 2^N - количество всех возможных комбинаций.

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

Если A_i,j = true, то S_i,j(x_i) = x_i

Если A_i,j = false, то S_i,j(x_i) = ~x_i

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

(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₃)             (1)
...
(S_1,M(x₁) & S_2,M(x₂) & S_3,M(x₃) & ... & S_N,M(x_N) & F_M)

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

Осталось доказать, что правая часть (1) действительно равна исходной функции. Возьмем произвольную строку таблицы:

A1,j

A2,j

A3,j

...

AN,j

Fj

Убедимся, что значение функции F_j действительно равно значению правой части (1) когда значения переменных равны значениям, указанным в этой строке: x₁ = A_1,j, x₂ = A_2,j и т.д., в общем, x_i = A_i,j для i = 1, 2, 3,..., N.

Вспомогательные функции для этой строки:

Если A_i,j = true, то S_i,j(x_i) = x_i = A_i,j = true

Если A_i,j = false, то S_i,j(x_i) = ~x_i = ~A_i,j = ~false = true

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

S_i,j(x_i) = true    (2).

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

S_1,j(x₁) & S_2,j(x₂) & S_3,j(x₃) & ... & S_N,j(x_N) & F_j = F_j & true & true & true ... & true = F_j

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

A_n,j ≠ A_n,k

Отсюда:

Если A_n,j = true, то A_n,k = false, значит S_n,k(x_n) = x_n = A_n,k = false

Если A_n,j = false, то A_n,k = true, значит S_n,k(x_n) = ~x_n = ~A_n,k = ~true = false

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

S_n,k(x_n) = false    (3).

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

S_1,k(x₁) & S_2,k(x₂) & ... & S_n,k(x_n) & ... & S_N,k(x_N) & F_k = S_1,k(x₁) & S_2,k(x₂) & ... & false & ... & S_N,k(x_N) & F_k = false

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

И по законам поглощения x false = x и false x = x формула (1) превращается в:

(false)
(false)
...
(false)
(F_j)
(false)
...
(false) = F_j

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

В формуле (1) строки, в которых F_j = false можно опустить (см. правило 3.2) в главе "Приведение подобных членов". А в строках, в которых F_j = true можно опустить F_j (см. правило 2.1).

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

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

Составим СДНФ для функции f(x, y, z):

x	y	z	f(x, y, z)
false	false	false	false
false	false	true	false
false	true	false	false
false	true	true	true
true	false	false	true
true	false	true	false
true	true	false	true
true	true	true	false

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

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

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

Вопросы и задания для самостоятельной работы

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

   x	y	z	f(x, y, z)
   false	false	false	true
   false	false	true	true
   false	true	false	false
   false	true	true	false
   true	false	false	false
   true	false	true	false
   true	true	false	false
   true	true	true	true

   Посмотреть ответ

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

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

   a	b	f(a, b)
   false	false	true
   false	true	false
   true	false	false
   true	true	false

   Посмотреть ответ

   f(a, a) = ~a&~b