Лекция 5

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

ПЛАН:

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.

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

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

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

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

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