Большая Советская Энциклопедия (АЛ) - Большая Советская Энциклопедия "БСЭ" (читать книги полные txt) 📗

(7) Х®Y ==

ÚY, Х~Y = (X&Y)Ú(&).

  Эти равенства, устанавливаемые, например, с помощью истинностных таблиц, позволяют уже без помощи таблиц получать др. равенства. Методом получения последних являются т. н. тождественные преобразования, которые меняют, вообще говоря, выражение, но не функцию, реализуемую этим выражением. Например, при помощи законов поглощения получается закон идемпотентности ХÚХ = X. Упомянутые равенства в ряде случаев позволяют существенно упростить запись формул освобождением от «лишних скобок». Так, соотношения (1) и (2) дают возможность вместо формул (...(Á₁ &Á₂ )&...)& Á_s и (...(Â₁ ÚÂ₂ )Ú...)Ú Â_s использовать более компактную запись Á₁ &Á₂ &...&Á_s и Â₁ ÚÂ₂ Ú...Â_s Первое из этих выражений называется конъюнкцией сомножителей Á₁ ,..., Á_s , а второе — дизъюнкцией слагаемых Â₁ ,..., Â_s . Равенства (5), (6), (7) показывают также, что константы 0 и 1, импликацию и эквивалентность, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, всякая функция А. л. может быть реализована формулой, записываемой с помощью символов

 

  Нормальные формы. Множество всех формул, в построении которых участвуют переменные высказывания, некоторые из символов &, Ú,®, ~ , ^- и констант 0 и 1, называются языком над данными символами и константами. Равенства (1) — (7) показывают, что для всякой формулы в языке над &, Ú,®, ~ , ^- ,0, 1 найдётся равная ей формула в языке над &, Ú,^- ,0, 1, например

 

  Особую роль в последнем языке играет класс формул, которые могут быть записаны в виде Á₁ ÚÁ₂ Ú...ÚÁ_s , 0 или 1, где s ³1, и каждое Á_i — либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое Á_i не содержит одинаковых сомножителей и не содержит сомножителей вида Х и

 одновременно и все Á_i — попарно различны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает «сильнее», чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислить значения Á_i .Эти выражения называются дизъюнктивными нормальными формами (днф). Каждую формулу Á, реализующую функцию, отличную от константы, в языке над &, Ú, ®, ~ , ^- , 0, 1 при помощи равенств (1) — (7) можно привести к равной ей днф, содержащей все переменные формулы Á и любое число других переменных, причем каждое Á в этой днф содержит одни и те же переменные. Такая днф называется совершенной днф формулы Á. Возможность приведения к совершенной днф лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперёд заданных формул.

  Важную роль в А. л. и её приложениях играет т. н. сокращённая днф. Днф называется сокращённой, если выполнены следующие условия: 1) в ней нет таких пар слагаемых Á_i и Á_j , что всякий сомножитель из Á_i имеется и в Á_I ; 2) для всяких двух таких слагаемых Á_i и Á_i ,из которых один содержит сомножителем некоторое переменное, а другой — отрицание этого переменного (при условии, что в данной паре слагаемых нет другого переменного, для которого это же имеет место), имеется (в этой же днф) слагаемое Á_i , равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая днф при помощи равенства (1) — (7) может быть приведена к равной ей сокращённой днф. Например, сокращённой днф для формулы ((X ~ (Y®Z)) ® (X&Z)) является

 

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

 

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

 

  Операция (или функция) 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 и обратно. Тождественные преобразования в последнем языке осуществляются при помощи равенств, установленных для конъюнкции и дополнительных: