СДНФ и СКНФ методика построения по таблице истинности. Переход от ДНФ к СДНФ. Переход от КНФ к СКНФ.

При перекодировании системы на другой язык повышается ее быстродействие и увеличивается переносимость, но гибкость при этом снижается. Это приемлемо лишь в том случае, если система сохраняет все знания предметной области и это знание не будет изменяться в ближайшем будущем. Если ЭС создана именно из – за того, что предметная область изменяется, то необходимо поддерживать систему в инструментальной среде разработки.

Например, удачным примером ЭС является XCON(R1) – ЭС, которую фирма DEC использует для комплектации ЭВМ семейства VAX. Одна из ключевых проблем, с которой фирма DEC столкнулась – необходимость постоянного внесения изменений для новых версий оборудования, новых спецификаций и т. д. Для этой цели XCON(R1) поддерживается в программной среде OPS/5.

Основные логические операции. (Определение, таблица истинности, привести примеры)

Логические операции.

Логическая операция – способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний.

Логическое отрицание (инверсия)

Логическое отрицание (инверсия) образуется из высказывания с помощью добавления частицы «не» или использования оборота речи «неверно, что…».

Пример: Завтра мы не пойдем в техникум.

Таблица истинности:( таблица, с помощью которой можно описать логические значения высказывания при всех возможных значениях простых высказываний)

Инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно.

Обозначение инверсии: НЕ; ; NOT; ¯ .

Этот джемпер красного цвета – Неверно, что этот джемпер красного цвета.

Логическое умножение (конъюнкция)

Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза «и».

Пример: Закончились лекции, и студенты пошли домой.

Высказывая конъюнкцию, мы утверждаем, что выполняются оба события, о которых идет речь в составляющих высказываниях.

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно из высказываний ложно.

Обозначение конъюнкции: И; AND; & ;* ^

Логическое сложение (дизъюнкция)

Логическое сложение (дизъюнкция) образуется соединением двух высказываний в одно с помощью союза «или».

В русском языке союз «или» используется в двояком смысле.

Например, в предложении Обычно в 8 вечера я смотрю телевизор или пью чай союз «или» взят в неисключающем (объединительном) смысле, так как можно только пить чай или только смотреть телевизор, но можно также пить чай и смотреть телевизор одновременно. Такая операция называется нестрогой дизъюнкцией.

В высказывании Данный глагол I или II спряжения союз «или» используется в исключающем (разделительном) смысле.

Строгая

Строгой дизъюнкцией высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний.

Нестрогая

Дизъюнкция (нестрогая) двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно.

Обозначение дизъюнкции: ИЛИ; OR; v; +;

Примеры строгих и нестрогих дизъюнкций.

Логическое следование (импликация)

Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то …».

Пример: Если число делится на 9, то оно делится на 3.

Если коровы летают, то 2+2=5. (в логике допустимо рассматривать и бессмысленные с житейской точки зрения высказывания).

Обозначение импликации: А→В; А═>В.

Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное.

Логическое равенство (эквивалентность)

Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно при помощи оборота речи «…тогда и только тогда, когда…»

Пример: Две прямые параллельны тогда и только тогда, когда они не пересекаются.

Обозначение эквивалентности: А ≡ В; А<=>В; А~В

Эквивалентность двух высказываний истинна тогда только тогда, когда оба высказывания истинны или оба ложны.

Таблица истинности и методика её построения для сложного высказывания. Привести пример.

Приоритет логических операций.

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету.

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация и эквивалентность.

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Пример 1

Дана формула: АvВ═>С&D<=>Ā.

Порядок вычисления:

1. Ā - инверсия;

2. С&D - конъюнкция;

3. АvВ - дизъюнкция;

4. АvВ═>С&D - импликация;

5. АvВ═>С&D<=>Ā. – эквивалентность.

Пример 2

Вычислите значение логической формулы.

Е = А & В v A & C ( не¹ А и² В или⁴ А и³ С)

если логические переменные имеют следующие значения:

А=0, В=1, С=1

1) не¹ А = 1

2) не¹ А и² В = 1 и 1 =1

3) А и³ С = 0 и 1= 0

4) 1 или 0 = 1

Ответ: Е=1

Алгоритм построения таблицы истинности сложного высказывания.

Таблица истинности определяет истинность или ложность составного высказывания при всех возможных комбинациях исходных значений простых высказываний.

1. Вычислить количество строк и столбцов таблицы истинности.
Пусть сложное высказывание состоит из n простых. Тогда количество строк в таблице истинности равно 2ⁿ плюс 2 строки заголовка.

Количество столбцов в таблице равно сумме количества переменных и количества логических операций , входящих в высказывание.

2. Начертить таблицу и заполнить заголовок.

3. Заполнить первые n столбцов по порядку.

4. Заполнить остальные столбцы.

Понятие элементарного произведения; понятие дизъюнктивной нормальной формы (ДНФ). Понятие элементарной дизъюнкции, понятие конъюнктивной нормальной формы (КНФ). Переход от ДНФ к КНФ.

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.

Х^X ; X^Z^ Y.

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.

Х v X ; X v Z v Y.

Всякую дизъюнкцию элементарных конъюнкций называют дизъюнктивной нормальной формой(ДНФ). (Х^X) v (X^Y).

Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой (КНФ). (Х v X v Y) ^ (X v Y).

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

Например, является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ . Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

Зная ДНФ можно составить таблицу истинности соответствующей функции.

Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

- если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

- если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

или

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

Пример1. Привести выражение к ДНФ, а затем сократить ее (если это возможно).

Решение. “Понижаем” отрицания по правилу де Моргана. Получаем По правилу Блейка (имеются дизъюнктные слагаемые, содержащие у и ) к последнему выражению можно добавить слагаемое x z , котороепоглотит второе слагаемое в L.

Ответ: L = xy xz

СДНФ и СКНФ методика построения по таблице истинности. Переход от ДНФ к СДНФ. Переход от КНФ к СКНФ.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

На СДНФ накладываются следующие требования:

1. формула не является тождественно-ложной;
2. формула приведена к одному из видов ДНФ;
3. из формулы удалены элементарные конъюнкции, включающие одновременно переменную и её отрицание, согласно закону инверсии;
4. из формулы удалены одинаковые элементарные конъюнкции, кроме одной, согласно закону идемпотентности;
5. каждая элементарная конъюнкция в ДНФ включает все логические переменные, входящие в эту формулу.

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.

Например, выражение является СКНФ.

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Алгоритм получения СДНФ по таблице истинности.

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно1, то в конъюнкцию включать саму эту переменную, если равно 0, то её отрицание:

– для 2-й строки;

– для 3-й строки.

3. Все полученные конъюнкции связать в дизъюнкцию:

v

Алгоритм получения СКНФ по таблице истинности.

1. Отметить те строки таблицы истинности, в последнем столбце которых стоит 0:

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно0, то в конъюнкцию включать саму эту переменную, если равно 1, то её отрицание:

Х v Y – для 1-й строки;

– для 4-й строки.

3. Все полученные дизъюнкции связать в конъюнкцию:

(Х v Y) ( )

Полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Для нахождения формулы по таблице истинности рекомендуется использовать тот из двух алгоритмов, в котором в таблице помечается меньше строк.