§ 21. Основные виды теорем
Теорема рассматривается как предложение, истинность которого должна быть обоснована строгим логическим доказательством. Доказательство – это демонстрация истинности утверждения путём применения аксиом, доказанных уже ранее теорем и следствий из них, вспомогательных предложений (лемм), а также логических законов. Такой подход позволяет строить обоснованную последовательность рассуждений (с возможным использованием формул, таблиц, графиков и т.п.), приводящих от условий теоремы к выводу о справедливости её утверждения. Сами условия теоремы – это совокупность исходных тезисов или посылок, которые характеризуют содержание теоремы, возможности её выполнения и предполагаемые действия при доказательстве. Формулировка теоремы – это утверждаемый тезис, требующий доказательства, а вывод рассматривается как последовательность формул и рассуждений, приводящих к самому доказательству.
Исходные тезисы
или посылки сами являются высказываниями
из данного универсума W.
Обозначим эти посылки
Формула посылки имеет вид
Эта формула имеет область истинности
и область ложности, которые мы обозначим
соответственно
(
)
и
Очевидно, что
(
)
+
= W.
(21.1)
Формулировка
теоремы является данной логической
функцией T
от нескольких утверждений (высказываний)
,
которые сами связаны известными
логическими функциями с исходными
тезисами:
Следовательно,
утверждение теоремы также содержит
указанные высказывания, но под знаком
сложной логической формулы
.
Для неё области истинности и ложности
обозначим аналогично предыдущему:
(
)
и
Теперь перейдём
к видам теорем, которые обычно применяются
в математической логике. Первый вид –
это прямая теорема: «Из посылки
следует
утверждение
».
При этом требование доказательности
имеет простой вид:
(
)
(
)
. (21.2)
Это условие проще всего проверять табличным методом: с помощью матриц Карно соответствующего вида. Прямая теорема может быть записана в форме правила вывода:
|
условие доказательности: |
( ) ( ) |
|
Вторым видом является обратная к исходной теорема, в которой исходные посылка и утверждение меняются местами: «Из посылки следует утверждение ». Требование доказательности в этом случае имеет вид:
( ) ( ) . (21.3)
Мы не будем записывать её в форме правила вывода. Если выполняется равенство для областей истинности:
( ) = ( ), (21.4)
то мы приходим к понятию необходимых и достаточных условий, то есть, эквивалентности данных формул:
. (21.5)
Третьим видом рассматривается теорема, противоположная данной: «Из отрицания посылки следует отрицание утверждения ».
Для этого вида теоремы условия доказательности записываются с применением областей ложности данных формул:
(21.6)
Соответственно этому можно записать форму правила вывода:
|
условие доказательности: |
|
|
Четвёртым видом является теорема, противоположная обратной, которая имеет вид: «Из отрицания посылки следует отрицание утверждения ». В условии доказательности по сравнению с предыдущим меняются местами левая и правая части:
. (21.7)
В этом случае мы также не будем записывать соответствующее правило вывода ввиду его очевидности.
Контрольные вопросы:
1. Понятие о доказательствах, их виды.
2. Структура условий теоремы.
3. Формулировка теоремы.
4. Формулы для посылки и утверждения теоремы.
5. Структура прямой исходной теоремы.
6. Схемы и формы вывода.
7. Структура теоремы, обратной исходной.
8. Понятие о необходимых и достаточных условиях.
9. Теорема, противоположная для исходной.
10. Теорема, обратная для противоположной.
ПРИЛОЖЕНИЯ
Контрольная работа № 1
Билет № 1
C |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A & B) →C
1.3. Доказать: A \ ( B U C ) = ( A \ B ) & ( A \ C )
Билет № 2
2.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
универсуме, если значения
D заданы в таблице.
2.2.. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = A & ( B U C )
2.3. Доказать:
A & ( B U C ) = ( A & B) U ( A & C )
Билет № 3
3.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
универсуме, если значения
D заданы в таблице.
3.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A → B ) U C.
3.3. Доказать:
A U ( B & C ) = ( A U B ) & ( A U C ).
Билет № 4
4.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
универсуме, если значения
D заданы в таблице.
4.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A → B ) & C.
4.3. Доказать:
A & ( B U C ) = ( A & B ) U ( A & C ).
Билет № 5
5.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
универсуме, если значения
D заданы в таблице.
5.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A U B ) → C.
5.3. Доказать:
A & ( B U C ) = ( A & B ) U ( A & C ).
Билет № 6
6.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
универсуме, если значения
D заданы в таблице.
6.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A → B ) → C.
6.3. Доказать:
A U ( B & C ) = ( A U B ) & ( A U C ).
Билет № 7
7.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
универсуме, если значения
D заданы в таблице.
7.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D = ( A → B ) U C.
7.3. Доказать:
A & ( BU C ) = ( A & B ) U ( A & C ).
Билет № 8
8.1. Найти формулу и указать
C |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
B |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
A |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
D |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
универсуме, если значения
D заданы в таблице.
8.2. Построить таблицу значений и указать конструкцию множества на универсуме, если
D
= A
&
(
C).
8.3. Доказать:
A & ( B U C ) = ( A & B ) U ( A & C ).
Контрольная работа № 2
Билет № 1
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 2,4,7,8}, P = {1,2,5,6}, Q = {1,4,6,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 2
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,4,6,7}, P = {1,2,5,6}, Q = {2,3,6,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 3
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,4,6,8}, P = {1,2,4,6}, Q = {2,3,5,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 4
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,7}, P = {1,2,3,5}, Q = {2,4,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 5
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,7}, P = {1,2,3,5}, Q = {2,4,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
.
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 6
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,7}, P = {1,2,3,5}, Q = {2,4,5,6}.
Виды операций:
.
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 7
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,2,5,7}, P = {1,2,3,5}, Q = {2,4,5,8}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
.
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 8
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,2,6,7}, P = {1,2,4,5}, Q = {2,4,5,7}.
Виды операций:
.
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 9
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,8}, P = {1,2,4,5}, Q = {2,3,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
.
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 10
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,2,6,7}, P = {1,2,4,5}, Q = {2,3,5,6}.
Виды операций:
.
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 11
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,8}, P = {1,2,3,8}, Q = {2,3,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
.
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 12
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,4,7}, P = {1,2,3,6}, Q = {2,4,5,8}.
Виды операций:
.
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 13
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 2,4,6,8}, P = {1,2,4,6}, Q = {2,4,6,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 14
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,4,6,8}, P = {1,2,5,7}, Q = {2,3,6,8}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 15
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,4,5,8}, P = {1,2,3,6}, Q = {2,3,4,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 16
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,3,6,8}, P = {1,2,3,6}, Q = {3,4,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 17
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 3,4,5,7}, P = {1,2,3,5}, Q = {1,3,4,7}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
Билет № 18
1. Найти и построить результат бинарных и тернарных операций для дискретных множеств:
U = {1,2,3,4,5,6,7,8} – исходный универсум,
M = { 1,2,5,8}, P = {1,2,5,6}, Q = {1,2,5,6}.
Виды операций:
2. Найти таблицу и функцию истинности бинарной операции:
а)
3. Построить таблицу и функцию истинности тернарной операции:
4.Построить таблицу истинности и поле Канта квадра-операции:
ПРОГРАММА КУРСА «МАТЕМАТИЧЕСКАЯ ЛОГИКА»
Тема 1. ПРОСТЫЕ ВЫСКАЗЫВАНИЯ. Основные виды логических форм: понятие, суждение, умозаключение. Логические знаки и служебные слова. Простое суждение и его строение. Виды простых суждений. Переход от простого предложения к простому суждению. Формализация и семантическая значимость простого суждения. Формула простого суждения. Истинность простого суждения. Представление о высказывании. Универсум высказываний и его строение. Логический квадрат и логический куб, их применение. Виды отрицания высказываний. Преобразование высказываний, условия сравнения высказываний, переформулировка высказываний.
Тема 2. БИНАРНЫЕ ОПЕРАЦИИ С ВЫСКАЗАВАНИЯМИ. Построение сложных высказываний, их основные виды. Бинарные операции над высказываниями. Основные и взаимные бинарные операции. Конъюнкция и её основные свойства. Дизъюнкция и её основные свойства. Импликация и её основные свойства. Эквиваленция и её основные свойства. Композиции бинарных операций с отрицанием. Таблицы и функции истинности бинарных высказываний. Правило четырёх блоков и его применение. Взаимосвязи между бинарными операциями, понятие о двойственности и его применение.
Тема 3. ЛОГИЧЕСКИЕ ОПЕРАЦИИ ВЫСОКИХ ПОРЯДКОВ. Тернарные операции, их основные виды и способы построения. Композиции тернарных операций с отрицанием. Сложные тернарные операции, методы их анализа. Применение тернарных операций. Матрица Карно и поле Канта, их применение в тернарных операциях. Симметричные тернарные операции. Квадратичные логические операции, их основные виды. Методы анализа квадратичных операций. Специальные виды сложных высказываний: силлогизмы и другие случаи. Применение специальных видов сложных высказываний в анализе текстов.
Тема 4. ЛОГИЧЕСКИЕ ЗАКОНЫ. Понятие об уровнях логических законов. Логические законы первого уровня, их применение. Логические законы второго уровня. Примеры доказательства этих законов. Основные законы третьего уровня и методы их доказательства. Примеры законов более высоких порядков. Проблема универсалий в логике. Примеры доказательства универсалий и их применение.
Тема 5. НОРМАЛЬНЫЕ ФОРМЫ. Нормальные формы и их виды. Дизъюнктивные нормальные формы и методы их анализа. Конъюнктивные нормальные формы и методы их анализа. Преобразование видов нормальных форм, взаимосвязь между ними. Приведение высказывания к нормальной форме. Табличные и функциональные методы в анализе нормальных форм. Существование и единственность совершенной нормальной формы. Применение типов тернарных и квадратичных операций к исследованию нормальных форм. Карты Карно и структурные формулы в анализе нормальных форм многослойных логических операций.
Тема 6. ОСНОВЫ ТЕОРИИ ДОКАЗАТЕЛЬСТВ. Понятие о теореме. Основные виды теорем. Логическая обоснованность строения и формулировки теоремы. Виды доказательств и их структуры. Демонстративные методы доказательства. Особенности недемонстративных методов доказательства. Виды обоснования формулировки теоремы и тезисов при доказательстве, основные способы аргументации, формы доказательства.
Классификация видов теорем: прямая и противоположная, обратная и противоположная ей теоремы, взаимосвязь между ними. Логические следствия, их основные виды и методы обоснования, виды актов доказывания и их применение. Виды и средства логики при оперировании законами. Математические методы доказательств в логике, основные виды теорем. Применение доказательств в различных отраслях научного знания.
ЛИТЕРАТУРА:
В.П.Малахов. Формальная логика. М. «Акад. Проект». 2001
Ю.Л.Ершов, Е. А. Палютин. Математическая логика. СПб, «Лань»,2005.
А.Н.Колмогоров, А.Г.Драгалин. Математическая логика. М. «Урос». 2004.
А.И.Мальцев. Алгоритмы и рекурсивные функции. М. «Наука». 1996.
И.А. Лавров, Л.Л.Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. М. «Физматлит».
6. Дж. Шенфилд. Математическая логика. М. «Наука».1975.
7. В.И.Игошин. Задачи и упражнения по математической логике и теории алгоритмов. М. «Академия». 2006.
8. В.И.Евсеев. Логика. Учебное пособие. Изд. ТАРИ. Казань. 2001.
9. Н.Н.Нурмеев, Д.А.Роганов. Математическая логика и теория алгоритмов. Учебно-методическое пособие. Изд. «ТИСБИ». Казань.2006.
10. Фролов А.Н., Кочкарев Б.С. Система индивидуальных заданий по математической логике. Изд. ТГГПУ. Казань. 2006.
11. В.А.Бочаров, В.И.Маркин. Введение в логику. М. ИД «Форум». 2008.
