Большая Советская Энциклопедия (АЛ)

  Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Так называют выражения, которые можно получить из днф путём замены в них знаков Ú на &, а & на Ú. Например, из днф

 

  получается кнф

 

  Операция (или функция) f называется двойственной для операции y, если таблица, задающая f получается из таблицы, задающей y, путём замены в ней всюду 0 на 1 и 1 на 0 (включая замену значений функций). Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу и т. д. Преобразованием формул, при котором знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 — на 0, называются преобразованием двойственности. Если верно равенство Á = Â и Á* двойственно Á, а Â* двойственно Â, то верно Á* = Â*, называемое двойственным предыдущему. Это т. н. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая кнф двойственна некоторой днф. Совершенная кнф и сокращённая кнф определяются как такие кнф, что двойственные им выражения являются соответственно совершенной днф и сокращённой днф.

  Следствия. Гипотезы. Минимизация. Совершенные и сокращённые днф и кнф используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы Á понимается такая формула Â, что (®Á) = 1, а под следствием формулы Á — такая формула Â, что (Á®Â) = 1. Гипотеза формулы Á называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы Á. Аналогично, следствие формулы называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы Á. Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы и в получении из них при помощи законов (2) — (7) всех остальных гипотез и следствий.

  Сокращённая днф имеет важные приложения. Следует отметить прежде всего задачу минимизации функций А. л., являющуюся частью т. н. задачи синтеза управляющих систем. Минимизация функций А. л. состоит в построении такой днф для заданной функции А. л., которая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную «сложность». Такие днф называются минимальными. Каждая минимальная днф для заданной отличной от константы функции А. л. получается из сокращённой днф любой формулы, реализующей эту функцию, выбрасыванием некоторых слагаемых Á_i , из этой сокращённой днф.

  Языки. Интерпретации. В языке над &, Ú, ®, ~, 0, 1, + , где знак + интерпретируется как сложение по модулю два, устанавливаются следующие соотношения:

 

 

 

  Эти равенства позволяют переводить формулы в языке над &, Ú, ®, ~, ^- , 0, 1 в равные им формулы в языке над &,+, 1 и обратно. Тождественные преобразования в последнем языке осуществляются при помощи равенств, установленных для конъюнкции и дополнительных:

(11)   Х +Y=Y+ X;

(12)   (Х+Y) + Z = Х+(Y + Z);

(13)   Х&(Y + Z) = X&Y + X&Z

(14) Х&Х = Х, X + (Y + Y) = X, X&1 = X,

  здесь по-прежнему считается, что конъюнкция связывает «сильнее», чем знак +. Этих равенств достаточно для того, чтобы из них при помощи тождественных преобразований, так же как и при рассмотрении языка над &, Ú, ®, ~, ^- , 0, 1, можно было вывести любое верное равенство в языке над &, +, 1. Выражение в этом языке называется приведённым полиномом (п.п.), если оно либо имеет вид Á₁ +Á₂ + ... Á_s , где каждое Á_i есть или 1, или переменное, или конъюнкция различных переменных без отрицаний, Á_i ¹Á_j при i¹ j и s³1, либо равно 1 + 1. Например, выражение XYZ + XY+1 является п. п. Всякую формулу А. л. можно привести к п. п.

  Кроме рассмотренных языков, существуют и др. языки, равносильные им (два языка называются равносильными, если при помощи некоторых правил преобразования каждая формула одного из этих языков переводится в некоторую равную ей формулу в другом языке и обратно). В основу такого языка достаточно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию А. л. Такие системы называются функционально полными. Примерами полных систем являются