СДНФ
[предыдущая глава]  [оглавление]  [следующая глава]

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

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

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

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

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

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

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

Если Ai,j = true, то Si,j(xi) = xi

Если Ai,j = false, то Si,j(xi) = ~xi

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


(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)             (1)
...
(S1,M(x1) & S2,M(x2) & S3,M(x3) & ... & SN,M(xN) & FM)

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

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

A1,j A2,j A3,j ... AN,j Fj

Убедимся, что значение функции Fj действительно равно значению правой части (1) когда значения переменных равны значениям, указанным в этой строке: x1 = A1,j, x2 = A2,j и т.д., в общем, xi = Ai,j для i = 1, 2, 3,..., N.

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

Если Ai,j = true, то Si,j(xi) = xi = Ai,j = true

Если Ai,j = false, то Si,j(xi) = ~xi = ~Ai,j = ~false = true

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

Si,j(xi) = true    (2).

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

S1,j(x1) & S2,j(x2) & S3,j(x3) & ... & SN,j(xN) & Fj = Fj & true & true & true ... & true = Fj

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

An,j ≠ An,k

Отсюда:

Если An,j = true, то An,k = false, значит Sn,k(xn) = xn = An,k = false

Если An,j = false, то An,k = true, значит Sn,k(xn) = ~xn = ~An,k = ~true = false

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

Sn,k(xn) = false    (3).

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

S1,k(x1) & S2,k(x2) & ... & Sn,k(xn) & ... & SN,k(xN) & Fk = S1,k(x1) & S2,k(x2) & ... & false & ... & SN,k(xN) & Fk = false

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

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


(false)
(false)
...
(false)
(Fj)
(false)
...
(false) = Fj

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

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

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

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

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

xyzf(x, y, z)
falsefalsefalsefalse
falsefalsetruefalse
falsetruefalsefalse
falsetruetruetrue
truefalsefalsetrue
truefalsetruefalse
truetruefalsetrue
truetruetruefalse

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

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

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

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

  1. Составьте СДНФ для функции, представленной таблицей:
    xyzf(x, y, z)
    falsefalsefalsetrue
    falsefalsetruetrue
    falsetruefalsefalse
    falsetruetruefalse
    truefalsefalsefalse
    truefalsetruefalse
    truetruefalsefalse
    truetruetruetrue
  2. Составьте СДНФ для функции, представленной таблицей:
    abf(a, b)
    falsefalsetrue
    falsetrue false
    truefalse false
    truetrue false