Cтраница 2
Формула Y называется конъюнктивной нормальной формой формулы а, если у находится в конъюнктивной нормальной форме и обе импликации ( а у) и ( уФа) являются пропозициональными тавтологиями. [16]
Аналогично можно перейти от конъюнктивной нормальной формы к совершенной конъюнктивной нормальной форме. Например, задана конъюнктивная нормальная форма ( a b) ( b c) ( a ck Требуется найти для этой функции совершенную конъюнктивную нормальную форму. [17]
Эта формула уже представляет собой конъюнктивную нормальную форму. [18]
Если запрос представляется в конъюнктивной нормальной форме, то сначала производится поиск по дизъюнкциям высказываний, а в качестве ответа на запрос выдаются только такие сообщения, у которых коды объектов содержатся во всех результатах поиска по дизъюнкциям высказываний. [19]
Нетрудно обосновать следующий способ написания совершенных конъюнктивных нормальных форм формул по заданным диаграммам Венна. [20]
Фразовая форма очень похожа на конъюнктивную нормальную форму, за исключением того, что позитивные и негативные литералы в каждой дизъюнкции группируются вместе по разные стороны от символа стрелки, а затем символ отрицания отбрасывается. [21]
Последнее из полученных выражение представляет собой конъюнктивную нормальную форму. [22]
Если же при переходе к конъюнктивной нормальной форме не предполагается, что знак конъюнкции связывает менее тесно, чем знак дизъюнкции, то скобки остаются, но в скобках должны быть только элементарные дизъюнкции. [23]
Если исходная функция задана в конъюнктивной нормальной форме, то построение минимальной формы методом непосредственного упрощения осуществляется так. Вначале, пользуясь законом распределительности конъюнкции относительно дизъюнкции, раскрывают в конъюнктивной нормальной форме скобки. После этого приводят подобные члены и устраняют элементарные поглощения. Таким образом получается дизъюнктивная нормальная форма, минимизацию которой проводят указанным алгоритмом. [24]
Конъюнкция любого числа дизтермов называется конъюнктивной нормальной формой. [25]
Роль аналога конъюнкции простых-дизъюнкций в случае конъюнктивной нормальной формы здесь играют конечные множества импликаций некоторого специального вида. [26]
Как некоторую модификацию получаемого с помощью конъюнктивной нормальной формы метода доказательства полноты систем аксиом исчисления высказываний можно рассматривать доказательство, которое недавно дали Гермес и Шольц для первоначально установленного Лукасевичем факта, что формулы I вместе с формулой ( - А - - В) - ( В - А) при использовании подстановок и схемы заключения представляют собой систему, достаточную для вывода всех тождественно истинных формул исчисления высказываний, построенных с помощью одних только знаков импликации и отрицания. [27]
Задача об истинности булевского выражения в конъюнктивной нормальной форме ставится только в варианте принятия решения: существуют ли у переменных, входящих в выражение, такие значения истинности, подстановка которых делает все выражение истинным. Как число переменных, так и сложность выражения не ограничены, поэтому число комбинаций значений истинности может быть очень велико. [28]
Пусть нам задано булево выражение в конъюнктивной нормальной форме ( А В С) ( А В) Y. Первый шаг в конструировании логической схемы для этого выражения показан на рис. 4.4, а. Заметьте, что для получения выхрда Y члены ( термы) этого выражения ( А В С) и ( А В) должны быть связаны функцией И. На рис. 4.4 6 та же схема изображена в более компактной форме. [29]
Докажем, что для каждой формулы существует конъюнктивная нормальная форма. [30]