3.Равносильные преобразования формул.

Используя равносильности I, II и III групп можно часть формулы или формулу заменить равносильной ей форму­лой.

Такие преобразования формул называются равносильными.

Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.

Формула А считается проще равносильной ей фор­мулы В, если она содержит меньше букв, меньше ло­гических операций. При этом обычно операции экви­валентность и импликация заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям. Рассмотрим ряд при­меров.

Пример 1: Доказать равносильность . Используя равносильности I, II и III групп запишем цепочку равносильных формул:

П ример 2: Упростить формулу

Запишем цепочку равносильных формул:

Пример 3: Доказать тождественную истинность формулы

Запишем цепочку равносильных формул:

Задачи для самостоятельного решения

1. Установить, какие из следующих формул являются тождественно истинными, тождественно ложными путем преобразований и таблицы истинности. :

2. Упростить формулу:

3 . Доказать равносильность:

Контрольные вопросы

1. Какие формулы алгебры логики называются равносильными?

2. На какие классы подразделяются формулы?

3. Связь между понятиями равносильности и эквивалентности.

4. Перечислить равносильности первой группы важнейших равносильностей алгебры логики.

5. Перечислить равносильности, выражающие одни логические операции через другие.

6. Перечислить основные законы алгебры логики.

7. Что называется равносильным преобразованием формулы алгебры логики?

Лекция 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.

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

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

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

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

х	у	1	2	3	4	5	6	7
1	1	0	0	0	1	1	1	1
0	0	1	1	1	0	1	0	0
1	0	0	1	0	1	0	0	1
0	1	1	0	0	1	1	0	1

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

х	у	1	2	3	4	5	6	7
1	1	0	0	0	1	0	1	1
0	0	1	1	1	0	0	0	0
1	0	0	1	1	0	0	1	0
0	1	1	0	1	0	1	1	0

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

Примеры:

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

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

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

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

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

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

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