Лекция 5. 1. Закон двойственности

8 9 10 11 12 13 14

ТЕМА: ЗАКОН ДВОЙСТВЕННОСТИ. ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ ФОРМУЛ АЛГЕБРЫ ЛОГИКИ.

ПЛАН:

1. Закон двойственности.

2. Дизъюнктивная нормальная форма.

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

4. Проблема разрешимости.

Главная

1. Закон двойственности.

Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания. Операция конъюнкции называется двойственной для операции дизъюнкции, а операция дизъюнкции называется двойственной для операции конъюнкции.

Определение: Формулы А и А* называются двойственными, если формула А* получается из формулы А путем замены в ней каждой операции на двойственную.

Примеры: Для формулы А º (х v y)z двойственной является А*º х y v z.

Для формулы двойственной является

Прежде чем ввести принцип двойственности, рассмотрим лемму.

Лемма 1: Пусть А формула, х₁, х₂,…, х_к - список простых входящих в формулу высказываний. Тогда А принимает значение 1 на значениях (s₁, s₂,…, s_k) тогда и только тогда, когда двойственная формула А* принимает значение 0 на множестве (t₁, t₂, …, t_k), которое получено из множества (s₁, s₂,…, s_k) путем замены 1 на 0 и 0 на 1.

Продемонстрируем справедливость леммы на примере:

Двойственная:

Составим таблицы истинности для формул. (Порядок действий проставьте самостоятельно). Обе таблицы будут содержать четыре строки.

Для формулы А.

х	у

Для формулы А*.

х	у

Лемма 2. Если для формулы А(х₁, х₂,…, х_к) двойственной является А*(х₁, х₂,…, х_к), то справедлива равносильность:

Примеры:

1. А º х v y, двойственная ей А* º ху. Составим отрицание формулы А:

2. Составить двойственную формулу для формулы и проверить справедливость леммы 2.

Преобразуем формулу А: Двойственная формула

Составим отрицание формулы А:

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

Теорема: Если формулы А и В равносильны, то равносильны и им двойственные формулы, то есть А* º В*.

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

2. Дизъюнктивная нормальная форма.

Операции конъюнкции и дизъюнкции коммутативны и ассоциативны, поэтому, как бы не расставляли скобки, получим равносильные формулы.

Определение: Формула называется элементарной конъюнкцией, если она является конъюнкцией переменных (простых высказываний) и их отрицаний.

Пример: Эти формулы- элементарные конъюнкции.

. Каждая из этих формул не является элементарной конъюнкцией.

Определение: Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Для любой формулы путем равносильных преобразований можно получить ее ДНФ и не одну. Например: для формулы А º х(х®у) имеем: . Для этой же формулой можно составить еще несколько ДНФ:

Рассмотрим еще два примера на приведение формулы к ДНФ.

1. .

Формула так же ее ДНФ.

Ее ДНФ является также

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

Определение: Формула называется элементарной дизъюнкцией, если она является дизъюнкцией переменных (простых высказываний) и их отрицаний..

Пример: Эти формулы- элементарные дизъюнкции.

. Каждая из этих формул не является элементарной дизъюнкцией.

Определение: Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Для любой формулы путем равносильных преобразований можно получить ее КНФ и не одну.

Примеры:

2. Для этой же формулы составим ДНФ:

4. Проблема разрешимости.

Как было сказано выше, все формулы алгебры логики делятся на три класса:

1) тождественно истинные,

2) тождественно ложные и

3) выполнимые.

В связи с этим возникает задача: к какому классу относится данная формула?

Эта задача носит название проблемы разрешимости.

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

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

Однако практическое использование таблицы истинности для формулы А(х₁, х₂, …, х_к)при больших п затруднительно.

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

не является. Одновременно с этим решается вопрос о том, будет ли формула А выполнимой.

Предположим, что мы имеем критерий тождественной истинности для формул алгебры логики. Рассмотрим механизм его применения.

Применим критерий тождественной истинности к формуле А. Если окажется, что формула-А - тождественно истинная, то задача решена. Если же окажется, что формула А не тождественно истинная, то применим критерий тождественной истинности к формуле. Если окажется, что формула — тождественно истинная, то ясно, что формула А - тождественно ложная, и задача решена.

Если же формула - не тождественно истинная, то остается единственно возможный результат: формула А выполнима.

Установим теперь критерий тождественной истинности произвольной формулы алгебры логики. С этой целью предварительно сформулируем критерий тождественной истинности элементарной дизъюнкции.

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

Критерий тождественной истинности элементарной дизъюнкции позволяет сформулировать и доказать критерии тождественной истинности произвольной формулы алгебры логики.

Теорема 2. Для того, чтобы формула алгебры логики А была тождественно истинна, необходимо и достаточно, чтобы любая элементарная дизъюнкция, входящая в КНФ А, содержала переменную и ее отрицание.

Аналогично можно установить критерий тождественной ложности формулы алгебры логики, используя ее ДНФ. Приводим соответствующие теоремы.

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

Теорема 4. Для того, чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточно, чтобы, любая конъюнкция, входящая в ДНФ А, содержала переменную и ее отрицание.

На основании теорем 3 и 4 получим алгоритм проверки формулы:

1. привести формулу к какой либо ДНФ;

2. если ДНФА º 0, то задача решена, если нет, то переходим к следующему шагу;

3. составляем , если , то задача решена и А º 1, если же не является тождественно ложной, то А выполнима.

На основании критериев тождественной ложности и истинности можно составить комбинированные критерии.

Например:

1. привести формулу А к КНФА;

2. если КНФА º 1, то задача решена, если нет, то переходим к следующему шагу;

3. составляем ДНФА, если ДНФА º 0, то А º 0; если ДНФА не тождественно ложная, то А выполнимая.

(Самостоятельно составьте комбинированный алгоритм, начав его с приведения формулы к ДНФА.)

Пример 1. Применим критерий истинности.

2.Составим КНФ: , значит, А выполнима.

Пример 2. Применим критерий ложности.

2.Составим ДНФ: , значит, А º 1.

Пример 3.

Приведем формулу к какой-либо нормальной форме:

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