Основные правила получения тавтологий

Различают два основных правила образования тавтологий.

Правило 1. (правило заключения; правило отделения или правило modus ponens). Если формулы F и являются тавтологиями, то формула Н также является тавтологией.

Доказательство.

Докажем методом «от противного». Предположим, что существует набор значений переменных, при которых значение формулы Н = 0. Тогда, так как F = 1 (по условию формула F – тавтология), значение импликации . Получили противоречие с условием ( – тавтология и не может принимать значение 0). Следовательно, наше предположение неверно и формула Н является тавтологией.

Правило 2. (правило подстановки). Если формула F, содержащая пропозициональную переменную Х, является тавтологией, то подстановка в формулу F всюду вместо переменной Х любой формулы Н снова приводит к тавтологии. Новая формула при этом обозначается .

Пример 13: (самостоятельно докажите, что она является тавтологией). Пусть . Тогда также является тавтологией (самостоятельно убедитесь в этом с помощью таблицы истинности).

Вопросы для контроля:

1. Высказывания. Высказывательные формы. Кванторы.

2. Логические связки. Логические операции.

3. Формулы логики высказываний.

4. Таблицы истинности.

5. Классификация формул логики высказываний.

6. Значение тавтологий.

7. Правила получения тавтологий.

Раздел 2. Логическая равносильность формул

Отношение равносильности

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

В логике говорят, что два предложения равносильны, если они одновременно истинны, либо одновременно ложны. Слово «одновременно» в этой фразе неоднозначно. Так, для предложений «Завтра будет вторник» и «Вчера было воскресенье» это слово имеет буквальный смысл: в понедельник они оба истинны, а в остальные дни недели – оба ложны. Для уравнений «х = 2» и «2х = 4» «одновременно» означает «при одних и тех же значениях переменной». Прогнозы «Завтра будет дождь» и «Неверно, что завтра не будет дождя» одновременно подтвердятся (окажутся истинными) либо не подтвердятся (окажутся ложными). В сущности, это один и тот же прогноз, выраженный в двух разных формах, которые можно представить формулами Х и . Эти формулы одновременно принимают значение «истина» либо значение «ложь». Для проверки достаточно составить таблицу истинности:

Х

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

Формулы F₁ и F₂ называются равносильными, если их эквиваленция – тавтология.

Равносильность двух формул записывается так: (читается: формула F₁ равносильна формуле F₂).

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

Пример 1: Выяснить, являются ли формулы равносильными: 1) , ; 2) , .

Решение.

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

Составим эквиваленцию формул: . Полученная формула содержит две различные переменные (А и В) и 6 операций: 1) ; 2) ; 3) ; 4) ; 5) ; 6) . Значит, в соответствующей таблице истинности будет 5 строк и 8 столбцов:

А	В

Из итогового столбца таблицы истинности видно, что составленная эквиваленция является тавтологией и, значит, .

2) Для того чтобы выяснить являются ли формулы и равносильными, используем второй способ, то есть составим для каждой из формул таблицу истинности и сравним итоговые столбцы. (Замечание. Для того чтобы эффективно использовать второй способ, необходимо, чтобы все составленные таблицы истинности начинались одинаково, то есть наборы значений переменных были одинаковы в соответствующих строках.)

В формуле две различные переменные и 2 операции, значит, в соответствующей таблице истинности 5 строк и 4 столбца:

А	В

В формуле две различные переменные и 3 операции, значит, в соответствующей таблице истинности 5 строк и 5 столбцов:

А	В

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

Выражение не является формулой (так как символ « » не относится к какой-либо логической операции). Оно выражает отношение между формулами (также как равенство между числами, параллельность между прямыми и т.п.).

Справедлива теорема о свойствах отношения равносильности:

Теорема 2.1. Отношение равносильности между формулами алгебры высказываний:

1) рефлексивно: ;

2) симметрично: если , то ;

3) транзитивно: если и , то .

Законы логики

Равносильности формул логики высказываний часто называют законами логики. Перечислим наиболее важные из них:

1. – закон тождества.

2. – закон исключенного третьего

3. – закон противоречия

4.

5.

6.

7.

8. – закон двойного отрицания

9. – коммутативность конъюнкции

10. – коммутативность дизъюнкции

11. – ассоциативность конъюнкции

12. – ассоциативность дизъюнкции

13. – дистрибутивность конъюнкции

14. – дистрибутивность дизъюнкции

15. – законы идемпотентности

16. ; – законы поглощения

17. ; – законы де Моргана

18. – закон, выражающий импликацию через дизъюнкцию

19. – закон контрапозиции

20. – законы, выражающие эквиваленцию через другие логические операции

Законы логики используются для упрощения сложных формул и для доказательства тождественной истинности или ложности формул.

Упрощение формул.

Пример 1. Упростить формулу (АvВ) ^(АvС)
Решение.а) Раскроем скобки
( A vB ) ^ ( A v C )   ^ v ^C v B^A v B^C
б) По закону идемпотентности A^A   , следовательно,
 ^ v ^C v B^A v B^C   v ^C v B^A v B^C
в) В высказываниях А и А· C вынесем за скобки А и используя свойство Аv1 1, получим
АvА^Сv ^ v ^C  ( ^  v С v  ^  v ^С  v  ^  v ^С

Аналогично пункту в) вынесем за скобки высказывание А.
 v^ v ^С  ^  v    ^С  v  ^С
Таким образом, мы доказали закон дистрибутивности.

Пример 2. Упростить выражение v  ^

Решение. v  ^      v    - поглощение

Пример 3. Упростить выражение  ^  v  ^
Решение.  ^  v  ^    v    - склеивание

Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний - все отрицания будут применяться только к простым высказываниям.
Пример 4. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний. Примечание!!!! знак «+» - дизъюнкция; знак «∙»-конъюнкция.

Решение.1. Воспользуемся формулой де Моргана, получим:

2. Для выражения применим еще раз формулу де Моргана, получим:

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

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

Пример 6. Преобразовать формулу так, чтобы в ней не использовались знаки логического умножения.
Решение. Используя формулы де Моргана и закон двойного отрицания получим:

Эквиваленция выражается через конъюнкцию и импликацию:

                 
Из (3) и (1) получаем:
               Y   X         (4)
Эта равносильность выражает эквиваленцию через конъюнкцию, дизъюнкцию и отрицание.
Из равносильностей (3) и (2) получаем равносильность:
   =  (5),
выражающую эквиваленцию через конъюнкцию и отрицание.

Не нашли, что искали? Воспользуйтесь поиском по сайту: