Тема 2. Логические исчисления
Основная задача математической логики – формализация правильных способов рассуждения. Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны (простые высказывание или пропозициональные переменные). Из простых высказываний с помощью логических связок (операций) могут быть построены сложные высказывания.
Таблицы истинности позволяют ответить на многие вопросы, касающиеся формул логики высказываний: о равносильности формул, о противоречивости и т. п. Но более сложные вопросы решить с помощью таблиц истинности нельзя. Поэтому рассмотрим другой метод – методформальных аксиоматических теорий.
2.1. Интерпретация формул
Пусть A(x1,x2,…xn) – пропозициональная формула, гдеx1,x2,…xn– пропозициональные переменные. Конкретный набор значений, который принимают переменныеx1,x2,…xnназывается интерпретацией.
I(A) – значение формулы в интерпретацииI.
В одной интерпретации формула может быть истинной, а в другой – ложной.
Формула, истинная в какой- то интерпретации – выполнимая.
Формула истинная во всех интерпретациях – тавтология (тождественно истинная формула), иначе – противоречие.
Пример 1.
Докажем, что формула является тавтологией.
Пример 2.
Докажем, что формула является выполнимой.
2.2. Примеры тождественно истинных формул высказываний
Закон тождества. «Всякое высказывание является логическим следованием себя самого»
x->x
Доказательство сводится к построению таблиц истинности
|
x |
|
|
0 |
1 |
|
1 |
1 |
Закон противоречия. «Для всякого высказывания неверно, что истинно и высказывание х и его отрицание.
Доказательство сводится к построению таблиц истинности
|
x |
|
|
0 |
1 |
|
1 |
1 |
Закон исключенного третьего. «Для каждого высказывания х истинно или само высказывание, или его отрицание»
Доказательство сводится к построению таблиц истинности
|
x |
|
|
0 |
1 |
|
1 |
1 |
Закон двойного отрицания. Отрицание от любого высказывания равносильно самому высказыванию.
Добавление антцедента (истина из чего угодно). Если х – истина, то для любого у истинно, что y->x.
Из ложного что угодно.
Modusponens. Еслиx->y– истинно иx– истинно, то согласно законуmpможно заключить, что истинно у.
Этот тип заключения очень часто используется при математических доказательствах.
Пример.
1. Все простые числа, большие 2 – нечетны.
2. 7 – простое число.
3. Следовательно, 7- нечетное число.
Здесь применяются 2 закона. Первый закон – закон заключения от общего к частному будет рассмотрен в логике предикатов.
На основании этого закона преобразуется первая посылка заключения: Для всех х, если х – простое число большее 2, то х – нечетно. Согласно заключению от общего к частному высказывание если 7 – простое число большее 2, то 7 – нечетно – истинно. (А)
7 – нечетно (В)
A->B– Истинно
А – истинно
Применяем mp, следовательно, высказывание 7-нечетно – истинно.
Modus tollens
Или
Этот закон применяется при доказательствах от противного. Он является двойственным к mp.
Закон силлогизма
Этот закон позволяет строить сколь угодно длинные цепочки рассуждений.