Конъюнктивная нормальная форма

Cтраница 3

Qnxn) M, где М есть конъюнктивная нормальная форма. Если никакой квантор всеобщности не стоит в префиксе левее Qr, мы выберем новую константу с, отличную от других констант, входящих в М, заменим все хг, встречающиеся в М, на с и вычеркнем ( Qrxr) из префикса. Затем весь этот процесс применим для всех кванторов существования в префиксе; последняя из полученных формул есть скулемовская стандартная форма - для краткости, стандартная форма формулы F. Константы и функции, используемые для замены переменных квантора существования, называются скулемовскими функциями. [31]

Однако для каждой функции может существовать несколько дизъюнктивных и конъюнктивных нормальных форм. Однако существует один вид дизъюнктивной нормальной формы и один вид конъюнктивной нормальной формы, в которых функция может быть записана только единственным образом. Они называются совершенными нормальными формами. [32]

Дизъюнктом ( clause) называется элемент в конъюнктивной нормальной форме от сколемизированной правильно построенной формулы. [33]

Правая часть равенства ( 5) называется совершенной конъюнктивной нормальной формой ( кратко СК. [34]

Вычисление замыкания для множества зависимостей сводится к вычислению сокращенной конъюнктивной нормальной формы для функции DEP. В том случае, когда сокращенная ДНФ найдена для функции F ( DEP) / U, каждая простая импликанта, в которой нет переменных с отрицанием, определяет ключ. Безызбыточное покрытие, как и в случае с функциональными зависимостями, определяется тупиковой нормальной формой. [35]

Простейший ( но весьма громоздкий) способ построения дизъюнктивных и конъюнктивных нормальных форм для булевых функций состоит в использовании эквивалентных преобразований. [36]

Возможна ли формула, которая находится и в конъюнктивной нормальной форме, и в дизъюнктивной нормальной форме. [37]

Задача об электронном замке. [38]

Процедуры получения из таблиц истинности булевых выражений в конъюнктивной нормальной форме должны быть совершенно иными. [39]

Аналогично можно перейти от конъюнктивной нормальной формы к совершенной конъюнктивной нормальной форме. Например, задана конъюнктивная нормальная форма ( a b) ( b c) ( a ck Требуется найти для этой функции совершенную конъюнктивную нормальную форму. [40]

Подобные схемы описываются, очевидно, дизъюнктивными либо конъюнктивными нормальными формами, методы минимизации которых разобраны в § 2 настоящей главы. [41]

Содержательно эта проблема состоит в том, чтобы по произвольной конъюнктивной нормальной форме ( определение КНФ см. в § 8 гл. Ясно, что проблему ВЫПОЛНИМОСТЬ можно решить тривиальным алгоритмом, перебирая для заданной КНФ К, зависящей от п переменных, все 2П двоичных наборов длины п и вычисляя для каждого из них значение формулы К. [42]

Тем не менее рассматривая отношение между А и его конъюнктивной нормальной формой Ас, мы можем показать, что А доказуемо, если а 0 доказуемо. [43]

Вместе с тем та же функция может быть задана совершенной конъюнктивной нормальной формой, включающей не более 2т конъюнктивных членов. [44]

Таким образом, любая истинностная функция может быть представлена дизъюнктивной и конъюнктивной нормальной формой. [45]

Страницы: 1 2 3 4