ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.04.2021
Просмотров: 882
Скачиваний: 9
23
1.3.7. Примеры доказательств с разветвлением
.
Следующее табличное доказательство (левая таблица), в отличие от преды-
дущего, состоит не из одной строки истинностных значений, а из двух, по-
скольку на третьем шаге произошло
разветвление
процесса поиска контрпри-
мера.
?
(
) |
(
)
(
)
?
3 1
4 6
2 5 7
\
3 1 5 4 6
9 7 2
10 8
A
B
C
A
B
A
C
и и
да и и
л и и
л и и и и
и и л
и и
?
(
) |
(
)
(
)
?
?
3 1 11 10 9
4 6 12 2 5 7 8
A
B
C
A
B
A
C
и и и л л нет и и и л и л л
Дело в том, что после шага 1 (дизъюнкция истинна) и шага 2 (конъюнк-
ция ложна) мы не можем сделать определённого вывода о значениях операндов.
На третьем шаге вопросительным знаком отмечено
предположение
, исходя из
которого происходит дальнейшее заполнение строки, приводящее в конце к
противоречию между 2, 6 и 7 шагами. Отметим, что на шагах 6 и 7 значение
дизъюнкции найдено по значению
одного
операнда – поскольку он оказался ис-
тинным, дизъюнкция будет истинна независимо от значения второго операнда.
Рассмотрение альтернативного значения для
A
проведено в следующей
строке. Значения первых двух шагов перенесены из предыдущей строки, а на
третьем шаге косой чертой отмечено начало рассмотрения нового случая. По-
скольку и здесь получено противоречие (между шагами 2, 9 и 10), можно сде-
лать окончательный вывод о том, что заключение следует логически из посыл-
ки; это отмечено словом «
да
» под знаком логического следствия.
На правой таблице изображена направленная табличная процедура для
несколько изменённого умозаключения: в последней скобке вместо дизъюнк-
ции поставлена конъюнкция. Отличие от предыдущей таблицы начинается с
шага 7: из шагов 2 и 6 мы сделали вывод, что конъюнкция ложна, а затем (шаг
8), что
С л
. На шаге 11 вновь пришлось сделать предположение, поскольку
предыдущие шаги не определяют однозначно значение
B
. Результатом в этом
случае явился контрпример:
,
A
B
и C л
, так как никаких противоречий не
появилось. Поскольку одного контрпримера достаточно для обоснования отри-
цательного ответа, рассматривать прочие значения для
A
и
B
уже не нужно,
построение таблицы на этом закончено.
1.3.8. Упражнение.
Проверить, является ли заключение логическим следстви-
ем посылок.
1.
A
(B
C)
= A
B
C.
5.
A
B
C, C
B
= A
B.
2.
A
B
C
=
B
A.
6.
A
C, B
C
A
= B
C.
3.
(A
B)
= A
B.
7.
A
B, B
C
=
C
A.
4.
C
(
A
B)
= A
(B
C).
8.
A
B,
C
B
=
A
C.
24
1.3.9. Упражнение.
Формализовать умозаключения и проверить их логич-
ность.
1.
Число
n
меньше 100 или неверно, что
n
делится на 2 и на 3. Если
n
меньше
100, то
n
– двузначное число. Следовательно, чтобы число
n
не было двузнач-
ным, необходимо, чтобы
n
не делилось на 2 или не делилось на 3.
2.
Если сумма
n
m
не делится на 3, то
n
не делится на 3 или
m
не больше 2.
Сумма
n
m
не делится на 3 или
n m
больше 4. Следовательно, чтобы
n
де-
лилось на 3, а
m
было больше 2, необходимо, чтобы
n m
было больше 4.
3.
Число
n
не является простым или
100
n
. Если
100
n
, то
k
делится на 2 и
больше 3. Следовательно, чтобы
n
не было простым, достаточно, чтобы
k
не
делилось на 2 или было не больше 3.
4.
Для того, чтобы произведение
n m
делилось на 6, достаточно, чтобы
n
де-
лилось на 2, а
m
– на 3. Если
m
не больше 2, то
n m
не делится на 6. Следова-
тельно,
n
не делится на 2, или
m
не делится на 3, или
m
больше 2.
5.
Если
x
y
– четное число, то
3
x
или
7
y
. Если
3
x
, то
7
y
. Для ра-
венства
7
y
необходима четность суммы
x
y
. Следовательно,
x
y
четно
тогда и только тогда, когда
7
y
.
6.
Верно, что
0
x
, или
0
x
, или
0
x
. Если
0
x
или
0
x
, то
0
x
. Для
равенства
0
x
необходимо, чтобы условие
0
x
было нарушено. Следова-
тельно, условие
0
x
нарушается тогда и только тогда, когда
0
x
.
7.
Если
x
– не натуральное число, то
0
x
или
1/ 2
x
.
1/ 2
x
или неверно,
что
0
x
. Если
1/ 2
x
, то
x
- не натуральное число. Следовательно, для того,
чтобы равенство
1/ 2
x
не выполнялось, необходимо и достаточно, чтобы
x
было натуральным числом.
8.
Число
x
делится на 8, или сумма его цифр равна 13, или
0
x
. Если равен-
ство
0
x
не выполнено, то сумма цифр числа
x
не равна 13. Если
0
x
, то
x
делится на 8. Следовательно, для справедливости равенства
0
x
необходимо и
достаточно, чтобы
x
делилось на 8.
1.3.10. Определение логической эквивалентности, тавтологии и противо-
речия.
Как уже отмечалось в п.1.3.4, предикаты
A
и
B
называются
логически экви-
валентными
(
| |
A
B
), если
|
A
B
и
|
B
A
.
Предикат
B
называется
тавтоло-
гией
(|
B
), если он истинен в любой интерпретации.
Например, очевидно,
|
A
A
.
Список предикатов
S
называется
логически противоречивым
(или
противоречием
), если входящие в него предикаты не могут быть одновременно
истинными ни в какой интерпретации. Обозначение:
S
= .
Например,
,
|
A
A
.
В следующих трёх таблицах показано применение направленной табличной
процедуры для доказательства логической эквивалентности, тавтологии и про-
тиворечия. Первая состоит из доказательства двух логических следствий, про-
ведённого в единой таблице. Во второй и третьей таблицах отличие от доказа-
тельства логического следствия заключается в том, что при доказательстве тав-
25
тологии на первом шаге всему предикату присваивается значение «
л
», а при до-
казательстве противоречия на первых шагах каждому из предикатов данного
списка присваивается значение «
и
».
| |
|
7 1 8
3 5 2 4 6
|
3 2 4
7 5 1 8 6
A
B
B
A
и и л
и л л л и
да
и л л
и л и л и
да
|
(
)
7 2 8 1 4 6 3 5
A
B
A
B
да л и л л и л л л
,
|
3 1 4 7 5 2 8 6
A
B
A
B
и и и л и и л и да
1.3.11. Упражнение.
Проверить логическую эквивалентность.
1.
(A
B)
=
A
B.
2. A
(B
C)
=
(A
B)
C.
3. A
B
=
A
B.
4. A
B
=
B
A.
5. A
B
=
(A
B)
(B
A).
6. A
(B
C)
=
(A
B)
(A
C).
7. A
(B
C)
=
(A
B)
C.
8. A
B
C
=
(A
B)
(A
C).
1.3.12. Упражнение.
Проверить, является ли формула тавтологией.
1.
=
(A
B)
(
A
B
C).
2.
= (A
B
C)
(
C
A
B).
3.
=(
A
B
C)
(C
B)
(A
B).
4.
= (A
C)
(
B
C)
(A
B).
1.3.13. Упражнение.
Проверить, противоречив ли данный набор формул.
1.
(A
B),
B
A
= .
2. A
B,
A
B
= .
3. (A
B)
C,
C
(
A
B)
= .
4. A
(B
C), B
(
C
A)
= .
1.3.14. Свойства логического следствия, эквивалентности, тавтологии и
противоречия.
Пусть
, ,
A B C – предикаты,
S – список предикатов (возмож-
но, пустой). Тогда справедливы следующие утверждения.
1.
( , , |
)
(
, |
)
A B S
C
A
B S
C
(
объединение посылок
).
2.
( , , |
)
( , |
)
A B S
C
B S
A
C
(
перенос посылки, теорема о дедукции
).
3.
( |
)
(|
)
A
B
A
B
(
сведение следствия к тавтологии
).
4.
( |
)
( ,
| )
A
B
A
B
(
сведение следствия к противоречию
).
5.
(|
)
(
| )
B
B
(
сведение тавтологии к противоречию
).
6.
(|
)
( |
)
B
A
B
(
тавтология следует из любой посылки
).
7.
( | )
( |
)
S
S
B
(
из противоречия следует любое заключение
).
8.
( |
)
( |
)
( |
)
A
B
B
C
A
C
(
транзитивность логического следствия
).
9.
( | | )
( | | )
( | | )
A
B
B
C
A
C
(
транзитивность логической эквивалентности
).
Например, докажем утверждение 2. Пусть верна левая часть двойной импли-
кации, а правая ложна. Тогда найдется интерпретация, в которой предикаты
,
B S
истинны, а импликация
A
C
ложна. Последнее означает, что
A
истин-
но, а
C
ложно. Итак, в найденной интерпретации все предикаты в левой части
соотношения , , |
A B S
C
истинны, а
C
ложно. Мы получили противоречие с
тем, что левая часть двойной импликации верна.
Наоборот, пусть , |
B S
A
C
, но , , |
A B S
C
. Тогда существует интер-
претация, в которой , ,
A B S
истинны, а
C
ложно. Но в этой интерпретации
14
ложна и импликация
A
C
при истинных ,
B S
, чего не может быть по предпо-
ложению. Утверждение 2 доказано.
1.3.15. Упражнение.
Доказать остальные свойства. Сформулировать и дока-
зать аналогичные свойства следствия, эквивалентности, истинности и про-
тиворечия в теории.
1.4. Основные теоремы логики высказываний
В следующих двух теоремах собраны соотношения логики высказываний,
наиболее часто встречающиеся в практике математических рассуждений.
1.4.1. Теорема об отрицании, конъюнкции и дизъюнкции.
1)
Закон тождества:
A
= A.
2)
Закон двойного отрицания:
A
=
A.
3)
Правила удаления и введения
и
:
A
B
= A,
A, B
= A
B,
A
B,
A
= B,
A
= A
B,
A
A
=
A
A
=
A
A.
4)
Действия с константами – тавтологией
(и)
и противоречивым предикатом
(л):
A
л
=
л,
A
и
=
A,
A
и
=
и,
A
л
=
A.
5)
Коммутативность
:
A
B
=
B
A,
A
B
=
B
A.
6)
Ассоциативность:
A
(B
C)
=
(A
B)
C,
A
(B
C)
=
(A
B)
C.
7)
Дистрибутивность:
A
(B
C)
=
(A
B)
(A
C), A
(B
C)
=
(A
B)
(A
C).
8)
Законы де Моргана:
(A
B)
=
A
B,
(A
B)
=
A
B.
9)
Закон противоречия:
A,
A
= .
10)
Закон исключенного третьего:
= B
B.
1.4.2. Теорема об импликации и двойной импликации.
1)
Правила удаления и введения:
A
B, A
= B,
B
= A
B,
A
A
=
и.
A
B
=
(A
B)
(B
A).
2)
Действия с константами:
A
и
=
и, и
A
=
A,
л
B
=
и, A
л
=
A,
15
3)
Закон контрапозиции:
A
B
=
B
A.
4)
Выражение
через
и
:
A
B
=
A
B.
5)
Транзитивность:
A
B, B
C
= A
C,
A
B, B
C
= A
C.
1.4.3. Упражнение.
Доказать сформулированные утверждения.
1.4.4. Замечания об истории, терминологии и обозначениях.
Основы логики как
науки
о формах правильных умозаключений
заложены в
трудах Аристотеля в четвёртом веке до новой эры. Используя современный
язык, можно сказать, что основные исследования Аристотеля относились к ло-
гике предикатов, которая излагается во второй главе данного курса. Найденные
Аристотелем и некоторыми его последователями
фигуры силлогизмов
(пра-
вильных логических умозаключений) были настолько простыми и общими, что
до середины девятнадцатого столетия логика считалась наукой завершённой и
преподавалась практически в неизменном виде.
В середине 19 века в работах ирландского математика Джорджа Буля и шот-
ландского математика Августа де Моргана для описания и исследования логи-
ческих законов начинает применяться алгебраическая символика. Появляется
алгебра логики,
которая позже становится
математической логикой,
т.е. теори-
ей логических доказательств, широко применяющей математическую символи-
ку и математические методы и направленной, главным образом, на исследова-
ние
оснований математики.
Существует очевидная аналогия между алгеброй высказываний и алгеброй
множеств. Подобного рода
булевы
структуры имеют в настоящее время разви-
тую общую теорию и разнообразные приложения.
В начале 20 века математика переживала
кризис оснований
, связанный с от-
крытием и исследованием
парадоксов теории множеств.
В этот период логи-
ческие законы подверглись всестороннему критическому обсуждению, которое
и привело к созданию современной математической логики как
теории дока-
зательств
. Оживлённые дискуссии велись, в частности, по вопросу о границах
применимости закона исключённого третьего, на котором основываются в ма-
тематике многочисленные неконструктивные теоремы о существовании тех или
иных объектов.
Со второй половины 19 века математическая логика начинает применяться
для описания и исследования таких технических объектов, как
контактные
схемы, схемы из функциональных элементов, конечные автоматы.
В технических приложениях формулы логики высказываний рассматривают
как
двузначные функции от нескольких двузначных переменных
- функции и их
аргументы принимают значения в множестве {
и, л
}. Такие функции и перемен-
ные называются
булевскими
(
булевыми
). При рассмотрении булевых функций
часто вместо “
и
”, ”
л
” пишут, соответственно, “1” и ”0”, конъюнкцию
A
B