- •Министерство образования и науки Российской Федерации
- •Глава I. Алгебра высказываний
- •§ 1. Понятие высказывания
- •§ 2. Язык исчисления высказываний
- •Примеры формул и не формул
- •§ 3. Истинностные значения формул
- •§ 4. Законы логики, противоречия, выполнимые и равносильные формулы
- •§ 5. Совершенные дизъюнктивная и конъюнктивная нормальные формы
- •§ 6. Булевы функции
- •§ 7. Логическое следование
- •§ 8. Некоторые применения алгебры высказываний
- •Глава II. Алгебра предикатов
- •§ 1. Предикаты и кванторы
- •Логические операции над предикатами
- •§ 2. Равносильные и тождественно истинные предикаты
- •§ 3. Язык исчисления предикатов
- •§ 4. Интерпретации формул исчисления предикатов
- •§ 5. Приведённая и предварённая нормальные формы
- •§ 6. О структуре современных математических теорий
- •§ 7. Виды математических утверждений
- •§ 8. Некоторые методы доказательства теорем
- •Глава III. Формальные аксиоматические теории
- •§ 1. Формальные и неформальные аксиоматические теории
- •Примеры формальных аксиоматических теорий
- •Примеры доказательств в формальном исчислении высказываний
- •(В): (введение квантора ), (в): (введение квантора ),
- •Примеры доказательств в формальном исчислении предикатов
- •Аксиомы равенства:
- •Аксиомы операций сложения и умножения:
- •Примеры теорем формальной арифметики
- •§ 2. Непротиворечивость аксиоматических теорий
- •§ 3. Полнота аксиоматических теорий
- •§ 4. Разрешимость аксиоматических теорий
- •§ 5. Независимость системы аксиом теории
- •§ 6. Формальное исчисление высказываний
- •Приложение: формальная теория множеств
- •§ 1. Азы наивной теории множеств
- •Основные операции над множествами
- •§ 2. Аксиоматика Цермело-Френкеля теории множеств
- •40. Аксиома существования булеана (множества всех подмножеств) :
- •50. Аксиома (неупорядоченной) пары :
- •§ 3. Формальная теория множеств: райские кущи или адские дебри ?
- •А) основная литература:
- •Б) дополнительная литература:
- •Список основных обозначений
- •Предметный указатель
- •Алексей Игоревич Валицкас
§ 7. Логическое следование
Понятие логического следования является одним из важнейших в математической логике и имеет непосредственное отношение к жизни. Нам часто приходится обосновывать те или иные утверждения: это значит, что на основании нескольких высказываний a1 , … , an – посылок, делается вывод: “следовательно, верно утверждение (заключение) а”. Такой вывод является корректным в том и только том случае, если из истинности всех посылок следует истинность заключения, т.е. если истинно высказывание “если a1 и a2 , и … , и an , то a”. Это приводит к следующему определению логического следствия.
Пусть А1 , … , An , A – формулы исчисления высказываний от переменных x1 , … , xk , Г = {А1 , … , An }. Говорят, что формула А является логическим следствием множества формул Г (или просто формул А1 , … , An) , если при любых интерпретациях = (1 ; … ; k ) со свойством A1() = … = An() = 1 выполнено условие A() = 1. В этом случае пишут А1 , … , An A или кратко Г А. Последнее обозначение используется и в случае Г = : пишут А, понимая под этим, что А – закон логики.
Примеры: 1. Будет ли a b логическим следствием формул ,b ?
a |
b |
a b | |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
2. Будет ли формула a b с логическим следствием формул ,a b, b c ?
Аналогично предыдущему, строим таблицу истинности и замечаем, что ровно
a |
b |
c |
a b |
b c |
b c |
a b с | |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Теорема (критерий логического следования). Для формул А1 , … , An и А условие А1 , … , An A выполнено тогда и только тогда, когда формула (А1 … An) A является законом логики.
Доказательство. Пусть выполнено А1 , … , An A. Докажем, что формула (А1 … An A) – закон логики. При каких интерпретациях = (1 ; … ; k) рассматриваемая формула может быть ложна ? Только при тех, для которых верно (А1 … An)() = 1, но А() = 0. Это значит, что A1( ) = … = An() = 1, но A() = 0 – противоречие с условием А1 , … , An A. Поэтому рассматриваемая формула (А1 … An A) не может принимать значения 0, т.е. является законом логики, что и требовалось.
Пусть теперь (А1 … An A) – закон логики. Рассмотрим любую интерпретацию = (1 ; … ; k) со свойством A1() = … = An() = 1. Тогда
1 = (А1 … An A)() = (А1() … An() A()) = (1 A()),
и по аксиоме вычисления импликации A() = 1. Таким образом, А1 , … , An A.
Теорема доказана.
Теорема (о дедукции). Для любого множества формул Г и формул А, B условие Г, А В выполнено тогда и только тогда, когда ГA B.
Доказательство. Условие Г, А В, где Г = {A1 , … , An } (n 0), имеет место (по доказанной выше теореме) в случае, когда (A1 … An A B) – закон логики. Имеем ((A1 … An A B) 1) (( B) 1) {де Морган} (( B) 1) (( (A B)) 1) ((A1 … An (A B)) 1). Таким образом, (A1 … An A B) – закон логики тогда и только тогда, когда законом логики является формула (A1 … An (A B)), а это (по критерию логического следования) и означает, что Г, А Вимеет место тогда и только тогда, когда Г A B.
Теорема доказана.
В течение тысячелетий человечеством накоплен опыт построения правильных выводов. Соответствующие правила на математическом языке обычно записывают так: , гдеА1 , … , An – посылки, а А – заключение. Такое правило означает, что из справедливости посылок А1 , … , An логически следует справедливость заключения А . На самом деле правила (логического) вывода представляют из зебя схемы правил: они зависят от переменных-параметров, вместо которых можно подставлять любые формулы исчисления высказываний. Эти параметры будем выделять курсивом.
Пример. Правило modus ponens – “мост ослов”: 2 .
Здесь А , В – любые формулы языка исчисления высказываний. Докажем это правило. Для этого проверим, что А, А В В . Имеем (А, А В В ) (А В , А В ) (А В А В ) (((А В ) (А В )) 1), что справедливо.
Знак здесь, как обычно, следует понимать как синоним выражения “тогда и только тогда, когда”.
Теорема (об основных правилах логического вывода). Справедливы следующие основные правила логического вывода:
–расширение modus ponens, – правила дедукции, – правило расширения посылок, –правило перестановки посылок, – правила объединения и разделения посылок, – правила удаления конъюнкции, – правила введения дизъюнкции, – правило введения конъюнкции, – правила силлогизма, – modus tollens 3, – правило опровержения, – правило контрапозиции, – правило резолюций.
Доказательство. Правила расширение modus ponens доказывается аналогично его основному варианту. Правило дедукции уже доказано в теореме о дедукции. Остальные правила доказываются примерно так же.
Правило расширения посылок . Действительно, условиеГ B означает, что формула B принимает значение 1 на всех наборах значений переменных, при которых все формулы из Г имеют значения 1. Значит B принимает значение 1 и на всех наборах значений переменных, при которых имеют значения 1 формула A и все формулы из Г , т.е. Г, A B , что и требовалось доказать.
Правило перестановки посылок: . ДаноГ A (B C ), т.е. (по теореме о дедукции) Г, A B C или Г, A , B C , что равносильно утверждению Г, B , A C . По теореме о дедукции, получим Г, B A C , и далее Г B (A C ), что и требовалось.
Правило объединения и разделения посылок . Можно рассудить иначе, чем раньше: нетрудно заметить, чтоA (B C ) (A B) C . Поэтому если любая из этих формул истинна при любых значениях пропозициональных переменных, при которых истинны все формулы множества Г, то это же верно и для второй формулы. Таким способом можно доказать и предыдущее правило вывода.
Правила удаления конъюнкции . Если при любых значениях пропозициональных переменных, при которых истинны все формулы множества Г, истинна формула A B, то это верно и для формул A и B .
Правила введения дизъюнкции ивведения конъюнкции докажите самостоятельно.
Правила силлогизма: . Первое из правил следует из того, что еслиГ B и (B C) – закон логики, то при любых наборах значений пропозициональных переменных, при которых истинны все формулы из множества Г, истинны B и B C , а значит и C , что и требовалось.
Второе правило можно вывести так: если Г , A B и Г , B C , то (по теореме о дедукции) Г A B и Г B C , и по правилу введения конъюнкции верно Г (A B) (B C). Закон логики (A B) (B C ) (A C) позволяет по первому правилу силлогизма (?!) получить Г A С , а значит, Г , A С по теореме о дедукции, что и требовалось.
Правило modus tollens . Действительно, из Г A B и Г по правилу введения конъюнкции следует Г (A B ) . Учитывая закон логики (A B ) , по первому правилу силлогизма получаем (?!) Г , что и требовалось.
Правило опровержения можно вывести изГ A B , Г A и равносильности (A B ) (A ) (восстановите детали самостоятельно).
Правило контрапозиции следует из Г A B , теоремы о дедукции и закона контрапозиции.
Правило резолюций : если оно не верно, то для некоторой интерпретацииx1 = 1 , … , xn = n , при которой все формулы из Г имеют значение 1, будет A() = 0 = C(), что немедленно ведёт к противоречию: B() = (A() B()) = 1 = (C() ()) = ().
Теорема доказана.
Упражнение: Докажите все правила логического вывода при Г = .