1.5. Специальные формульные представления булевых функций

Как уже отмечалось, наиболее удобными для физической реализации являются пороговые функции. Это тождественная функция х, отрицаниех, конъюнкция , дизъюнкция , штрих Шеффера  , функция Вебба , а также обобщения функций  ,  ,  ,  на случай произвольного числа переменных.

Поэтому с практической точки зрения основной интерес представляют формульные представления булевых функций при помощи рассмотренных выше пороговых элементарных и обобщенных функций. Набор элементарных либо обобщенных функций, при помощи которого синтезируют формулы, будем называть базисным набором.

1.5.1. Конъюнкции и дизъюнкции над множеством переменных. Нормальные формы

Определение. Конъюнкцией над множеством переменных Х=(х₁,... ,х_n) называется логическое произведение вида:

К= х_i1^{ i1}  . . .  х_is^{ is} ,

где (х_{i1 , ... ,} х_is )  Х, х_ik^{ ik} = x_ik либоx_ik .

Конъюнкцию К можно представить как результат (s-1) применения двуместной функции логического умножения либо одной обобщенной функции , а также одноместной функции  . Аналогом функции  по принципу действия (выделение 1 на крайней позиции вектора истинности) является функция Вебба . Поскольку правило x у=x  у справедливо для любого числа переменных, то любая конъюнкция К может быть представлена в виде: К=( х_i1^{ i1}, . . . , х_is^{ i s} ), где  ― обобщенная функция Вебба. Данное представление назовем представлением в базисном наборе ( ). Отрицаниеx может быть выражено при помощи функции Вебба следующими способами:x = (х, х) = (х, 0) =( 0, х ) (дублирующая подстановка (х, х) на практике реализуется замыканием входов элемента  , а подстановка 0 ― заземлением соответствующего входа у функционального элемента (рис.1.5)). Поэтому любая конъюнкция К может быть полностью выражена при помощи элементов  ( в базисном наборе ()). При этом общее число функциональных элементов в конъюнкции К при использовании обоих базисных наборов одинаково.

Рис.1.5

Определение. Дизъюнкцией над множеством переменных Х=(х₁ , ... , х_n) называется логическая сумма вида:

D= х_i1^{ i1} . . .  х_is ^{ is},

где (х_{i1, ... ,} х_is )  Х, х_ik^{ ik} = x_ik либоx_ik .

Дизъюнкция D может быть реализована как при помощи (s-1) двуместной функции  , так и применением одной обобщенной функции  , а также одноместной функции . Поскольку аналогом функции  по принципу действия (выделение 0 на крайней позиции вектора истинности) является функция штрих Шеффера , то с учетом зависимости x у =x  у, любая дизъюнкция D может быть представлена в виде:

D =  ( х_i1^{ i1}, . . . , х_is^{ is} ),

где  ― обобщенная функция Шеффера. Данное представление назовем представлением в базисном наборе (  ).

Так как отрицание можно выразить через  :x = (х, х) =  (х,1) = (1,х) (рис.1.6), то с использованием данных правил любая дизъюнкция D может быть полностью выражена при помощи элементов  ( в базисном наборе (  )). При этом у одной и той же дизъюнкции общее число функциональных символов при использовании обоих наборов также одинаково.

Рис.1.6

Определение. Дизъюнктивной нормальной формой (ДНФ) булевой функции f (х ⁿ) называется формульное выражение вида:

f = К₁  ...  К_р ,

где К₁ , ... , К_р - конъюнкции.

Для соединения конъюнкций в ДНФ могут использоваться как 2—местная, так и обобщенная функция . Последняя с использованием эквивалентного соотношения

 (К₁ , ... , К_р ) =   ( К₁ , ... , К_р )

может быть заменена обобщенной функцией Вебба.

Определение. Веббовой нормальной формой (ВНФ) булевой функции f (х ⁿ) назовем её выражение вида:

f =   ( К₁ , ... , К_р ),

где К₁,...,К_р — конъюнкции, представленные как К_s =( х_i1^i1, ... , х_is^is), (1  s  p).

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

Замечание 1. В виде ДНФ и ВНФ могут быть представлены все функции алгебры логики, не равные константе 0. Эта функция не представима в данных формах, поскольку при наличии хотя бы одной конъюнкции в формулах ДНФ или ВНФ в векторе истинности функции также должна присутствовать хотя бы одна единица.

Замечание 2. Выражения с одним слагаемым вида f = К₁ для сохранения общности также будем относить к ДНФ (ВНФ). Назовем такие формы вырожденными.

Пример 1. Представить ДНФ булевой функции f = ху х у z в эквивалентной ВНФ. Дать решение задачи а) в базисном наборе ( ) и б) в базисном наборе () .

Решение.  Заменяя умножение во внутренних конъюнкциях ДНФ функцией Вебба, вначале изменим внутренние конъюнкции формы: ху = (х, у), х у z = (х,у,z). Внешнее сложение преобразуем с использованием правила:  (К₁, ... , К_р) =   (К₁ , ... , К_р ). В итоге получим искомое выражение функции в базисном наборе ( ):

f =  ((х, у), (х, у, z )).

Применяя эквивалентную заменуx = (х, х), находим формульное выражение функции, содержащее только функцию Вебба:

f =[ (((х, x), у), ( х, (y, у), (z, z))),  (((х, x), у), ( х, (y, у), (z ,z)))].

Полученные выражения дают искомое решение задачи.

Определение. Конъюнктивной нормальной формой (КНФ) булевой функции f (х ⁿ) называется её формульное выражение вида:

f=D₁... D_р,

где D₁ ,..., D_р — дизъюнкции.

В КНФ могут использоваться 2 — местная или обобщенная функции . Последняя с использованием эквивалентного соотношения  (D₁, ... , D_р) =   (D₁, ... , D_р ) может быть заменена обобщенной функцией Шеффера.

Определение. Шефферовой нормальной формой (ШНФ) булевой функции f (х ⁿ) назовем её выражение вида:

f = (D₁, ..., D_р),

где D₁, ... ,D_р — дизъюнкции, представленные в эквивалентной форме D_i = (х_i1^{ i1}, . . . , х_is^{ i s} ), (1  i  p).

Замечание 3. В виде КНФ и ШНФ могут быть представлены все функции алгебры логики, не равные константе 1. Данная функция не представима в виде КНФ и ШНФ, поскольку при наличии хотя бы одной дизъюнкции в их формулах вектор истинности функции также должен иметь хотя бы один нуль.

Замечание 4. Выражения с одним сомножителем вида f = D₁ для сохранения общности будем считать вырожденными КНФ (ШНФ).

Пример 2. Перевести КНФ булевой функции f =(х  у  z)& (у  z) в эквивалентную ШНФ. Дать решение задачи а) в базисном наборе (  ) и б) в однофункциональном наборе () .

Решение.  Заменим сложение во внутренних суммах (дизъюнкциях) КНФ обобщенной функцией Шеффера: (х  у  z) =  (х,у,z); (у  z)=  (у, z). Затем по правилу  (D₁, ... , D_р)=  (D₁, . . . , D_р ) производим замену внешнего сложения. В итоге получаем выражение функции в базисном наборе (  ):

f =  ( (х,у,z),  (у, z)).

После эквивалентной заменыx = (х, х), находим формулу функции, содержащую только функцию Шеффера:

f = [ ( (х, (у, у), (z, z)),  (у , z)),  ( (х, (у, у), (z, z)), (у , z))].

Таким образом, получены обе искомые формулы.

ЗАДАЧИ

1. Доказать (например, с использованием таблиц истинности) правильность следующих подстановок:

а)x = (х, х) = (х, 0) =(0, х) ;

б)x = (х, х) =  (х, 1) = (1, х) .

2. Доказать эквивалентность следующих обобщенных формул:

а) F₁= ( х₁, ... , х_s ) и F₂ =  ( х₁, ... , х_s );

б) F₁ = & ( х₁, ... , х_s ) и F₂ =  ( х₁, ... , х_s).

3. Представить ДНФ в виде эквивалентной ВНФ. Дать решения задачи в базисных наборах ( ) и () :

а) f =х у z у z ;

б) f = х уху  у z .

4. Преобразовать КНФ булевых функций в эквивалентные ШНФ с использованием базисных наборов (   ) и ( ) :

а) f = (х  у z)(х у z);

б) f = (х  у)(у z)(х z).