Нормальные

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

Особую
роль в последнем языке играет класс формул, к-рые могут быть записаны в
виде 0 или 1, где
и каждое - либо переменное высказывание,
либо его отрицание, либо конъюнкция таковых, при этом каждое
не содержит одинаковых сомножителей и не содержит сомножителей видаодновременно
и все - попарно различны. Здесь скобки опускаются,
т. к. предполагается, что операция конъюнкции связывает "сильнее", чем
дизъюнкция, т. е. при вычислении по заданным значениям переменных следует
сначала вычислить значения Эти выражения
наз. дизъюнктивными нормальными формами (днф). Каждую формулу
реализующую функцию, отличную от константы, в языке над
при помощи равенств (1) - (7) можно привести к равной ей днф, содержащей
все переменные формулы и любое число других
переменных, причем каждое в этой днф содержит
одни и те же переменные. Такая днф наз. совершенной днф формулы.
Возможность приведения к совершенной днф лежит в основе алгоритма, устанавливающего
Равенство или неравенство двух наперёд заданных формул.

Важную роль
в А. л. и её приложениях играет т. н. сокращённая днф.< Днф наз.
сокращённой, если выполнены

следующие условия:¹
1) в ней нет таких пар слагаемых и
что всякий сомножитель изимеется ив;
2) для всяких двух таких слагаемых и,
из к-рых один содержит сомножителем нек-рое переменное, а другой - отрицание
этого переменного (при условии, что в данной паре слагаемых нет другого
переменного, для к-рого это же имеет место), имеется (в этой же днф) слагаемое,
равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая днф
при помощи равенства (1) - (7) может быть приведена к равной ей сокращённой
днф. Напр., сокращённой днф для формулы
является

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

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

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

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я