Математическая логика

МЫСЛИТЕЛЬНАЯ ДЕЯТЕЛЬНОСТЬ

логика
интуиция
интуиция-суждение
интуиция-догадка
«Таким образом, логика и

λογος (греч.)– слово, смысл
Математическая логика:
предмет – логика
метод – математика
Язык:
предметный (язык –

(древнегреч.) Аристотель (384-322 до н.э.): теория дедукции – логического вывода
Евклид (330–275

НАПРАВЛЕНИЯ ОБОСНОВАНИЯ МАТЕМАТИКИ

логицизм
((нем.) Фреге(1848-1925), Пирс, (ит.) Пеано (1858-1932),

АКСИОМАТИЧЕСКИЙ МЕТОД: 3 СТАДИИ РАЗВИТИЯ

ЛОГИКА ВЫСКАЗЫВАНИЙ

ВЫСКАЗЫВАНИЕ

Высказывание – исходное понятие (не определяется через другие)
Форма существования высказывания

ПРОСТЫЕ ВЫСКАЗЫВАНИЯ

Примеры:
Земля – планета солнечной системы
5×7=35
простые (атомарными, элементарными) истинные высказывания
3×7=22
Рим –

Всякий важный двигатель работает без бензина
Земля вращается быстро
Который

СВОБОДНЫЕ И СВЯЗАННЫЕ ВХОЖДЕНИЯ ПЕРЕМЕННОЙ

переменная называется связанной, если подстановка в нее

А – посылка, антецедент импликации, В – заключение, консеквент ⟷ ⟺

ТАБЛИЦЫ ИСТИННОСТИ СВЯЗОК 0, Л, f, ⏊ 1, И, t, ⏉

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

инверсия, отрицание (НЕ, NOT)
конъюнкция (И, AND)
дизъюнкция (нестрогая, неисключающая)
(ИЛИ,

ПРОПОЗИЦИОНАЛЬНЫЕ ПЕРЕМЕННЫЕ АЛФАВИТ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Пропозициональные переменные назовем элементарными формулами, или атомами.
Алфавит алгебры

ПРОПОЗИЦИОНАЛЬНЫЕ ФОРМУЛЫ

А, В – метазнаки (произв. формулы)
Формулы в определении:
1) – элементарные

ФОРМАЛИЗАЦИЯ И ИНТЕРПРЕТАЦИЯ

Метаязык – это язык, служащий для объяснения другого

КЛАССИФИКАЦИЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

выполнимые
( = 1 хотя бы

ЛОГИЧЕСКАЯ РАВНОСИЛЬНОСТЬ

Два высказывания равносильны, если они одновременно истинны или одновременно ложны.
Две

ПРОВЕРКА ОБЩЕЗНАЧИМОСТИ

KLEENE ВВЕДЕНИЕ В МЕТАМАТЕМАТИКУ ОСНОВНЫЕ ТАВТОЛОГИИ

KLEENE ВВЕДЕНИЕ В МЕТАМАТЕМАТИКУ ОСНОВНЫЕ ТАВТОЛОГИИ

KLEENE ВВЕДЕНИЕ В МЕТАМАТЕМАТИКУ ОСНОВНЫЕ ТАВТОЛОГИИ

KLEENE ВВЕДЕНИЕ В МЕТАМАТЕМАТИКУ ОСНОВНЫЕ ТАВТОЛОГИИ

БУЛЕВЫ ФУНКЦИИ

Если формула содержит n переменных, то она задает некоторую функцию

НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Переход к равносильной формуле, содержащей только

НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Дизъюнктивным одночленом от переменных
называется

НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ
Конъюнктивной нормальной формой называется конъюнкция дизъюнктивных

СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Одночлен от переменных
называется

СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

СПОСОБЫ ПРИВЕДЕНИЯ ФОРМУЛЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ К СН-ФОРМЕ
СДН-форма:
СКН-форма:

СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ ДЛЯ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Теорема (о представлении формул

СПОСОБЫ ПРИВЕДЕНИЯ ФОРМУЛЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ К СН-ФОРМЕ
СИН-форма:

БУЛЕВЫ ФУНКЦИИ ОДНОГО АРГУМЕНТА

БУЛЕВЫ ФУНКЦИИ ДВУХ АРГУМЕНТОВ

БУЛЕВЫ ФУНКЦИИ n АРГУМЕНТОВ

ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

ТЕОРЕМА О ДЕДУКЦИИ

ПРАВИЛА ЛОГИЧЕСКИХ УМОЗАКЛЮЧЕНИЙ (ПРИМЕРЫ СТРУКТУР ПРАВИЛЬНОГО МЫШЛЕНИЯ)
Правило вывода:

ПРАВИЛА ЛОГИЧЕСКИХ УМОЗАКЛЮЧЕНИЙ (ПРИМЕРЫ СТРУКТУР ПРАВИЛЬНОГО МЫШЛЕНИЯ)

АЛГЕБРА ВЫСКАЗЫВАНИЙ И МАТЕМАТИЧЕСКИЕ ТЕОРЕМЫ

Логическая структура
- условие,
достаточное

АЛГЕБРА ВЫСКАЗЫВАНИЙ И МАТЕМАТИЧЕСКИЕ ТЕОРЕМЫ

Пусть теорема имеет форму
Тогда утверждение
называют обратным,

АЛГЕБРА ВЫСКАЗЫВАНИЙ И МАТЕМАТИЧЕСКИЕ ТЕОРЕМЫ
Теорема
Тогда противоположное утверждение

СПОСОБЫ ДОКАЗАТЕЛЬСТВА МАТЕМАТИЧЕСКИХ ТЕОРЕМ
косвенного доказательства,
доказательства разбором случаев,
от противного (приведения

ДЕДУКТИВНЫЕ И ИНДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

Умозаключение – переход от посылок к заключению (следствию)
(логическая

ДЕДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

ИНДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

ЛОГИКА ПРЕДИКАТОВ

ПОНЯТИЕ ПРЕДИКАТА

ПОНЯТИЕ ОДНОМЕСТНОГО ПРЕДИКАТА (ВЫРАЖАЕТ СВОЙСТВО)

ПРИМЕРЫ ОДНОМЕСТНЫХ ПРЕДИКАТОВ

ПОНЯТИЕ МНОГОМЕСТНОГО ПРЕДИКАТА (ВЫРАЖАЕТ ОТНОШЕНИЕ)

КЛАССИФИКАЦИЯ ПРЕДИКАТОВ

КВАНТОРЫ

КВАНТОРЫ

КВАНТОРЫ: ПРИМЕРЫ

РАВНОСИЛЬНОСТЬ ПРЕДИКАТОВ

СЛЕДОВАНИЕ ПРЕДИКАТОВ

РАВНОСИЛЬНЫЕ ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ

РАВНОСИЛЬНЫЕ ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ

ЛОГИЧЕСКИЙ КВАДРАТ

ЛОГИЧЕСКИЙ КВАДРАТ

ПРИМЕРЫ ОПЕРАТОРОВ, СВЯЗЫВАЮЩИХ ПЕРЕМЕННЫЕ

ПРИВЕДЕННАЯ ФОРМА

ПРЕДВАРЕННАЯ НОРМАЛЬНАЯ ФОРМА

ПРОБЛЕМА РАЗРЕШЕНИЯ ДЛЯ ОБЩЕЗНАЧИМОСТИ И ВЫПОЛНИМОСТИ

ИСЧИСЛЕНИЯ

ИСЧИСЛЕНИЕ (ФОРМАЛЬНАЯ ТЕОРИЯ)

ДОКАЗАТЕЛЬСТВО

ДОКАЗАТЕЛЬСТВО: ПОЛНОТА ТЕОРИИ

ДОКАЗАТЕЛЬСТВО: НЕПРОТИВОРЕЧИВОСТЬ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ

ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ

ТЕОРЕМА ГЁДЕЛЯ О НЕПОЛНОТЕ
Логика второго порядка в математической логике – формальная система,

ЛОГИКА В ШКОЛЬНОЙ МАТЕМАТИКЕ

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Свойство считают существенным для объекта, если оно присуще этому объекту

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Пример:
Объем понятия «прямоугольник» – это множество различных прямоугольников,
содержание

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

если увеличивается объем понятия, то уменьшается его содержание, и наоборот.

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Видовое отличие – это свойства (одно или несколько), которые позволяют

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Если понятие а определено через род и видовое отличие, то

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Одно и то же понятие определить через род и видовое

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ

Первичные понятия косвенно определяются через систему аксиом математической теории
Пример:
В элементарной

ОПРЕДЕЛЕНИЯ: СТРОЕНИЕ
В определении только Q(x) является высказывательной формой
Само определение – это

ОПРЕДЕЛЕНИЯ И ТЕОРЕМЫ: СТРОЕНИЕ

Внешний квантор общности в определении и теореме часто

МАТЕМАТИЧЕСКИЕ ПРЕДЛОЖЕНИЯ

А(х) => В(х),
можно прочитать по разному:
Из А(х)

МАТЕМАТИЧЕСКИЕ ПРЕДЛОЖЕНИЯ

«число х кратно 4» => «число х кратно 2»
Всякое

МАТЕМАТИЧЕСКИЕ ПРЕДЛОЖЕНИЯ
Данное
Обратное данному
Противоположное данному
Контрапозитивное данному (обратное противоположному)

МАТЕМАТИЧЕСКИЕ ПРЕДЛОЖЕНИЯ

Примеры:
Дана теорема: «если число делится на 3 и 4, то

МАТЕМАТИЧЕСКИЕ ПРЕДЛОЖЕНИЯ

Дана теорема: «во всяком прямоугольнике диагонали равны».
Обратное: «если диагонали

ДЕДУКТИВНЫЕ И ИНДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

Умозаключение – переход от посылок к заключению (следствию)
(логическая

ДЕДУКТИВНЫЕ И ИНДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

Дедуктивным называется умозаключение, в котором посылки и заключение

ПРИМЕРЫ СХЕМ ПРАВИЛЬНЫХ УМОЗАКЛЮЧЕНИЙ

Правило заключения:
Пример:
Если запись числа х оканчивается

ПРИМЕРЫ СХЕМ ПРАВИЛЬНЫХ УМОЗАКЛЮЧЕНИЙ

Правило отрицания:
Пример:
Если запись числа х оканчивается

ПРИМЕРЫ СХЕМ ПРАВИЛЬНЫХ УМОЗАКЛЮЧЕНИЙ

Правило силлогизма:
Пример:
Если число х кратно 12,

МАТЕМАТИЧЕСКИЕ РАССУЖДЕНИЯ

ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

ДЕДУКТИВНЫЕ И ИНДУКТИВНЫЕ УМОЗАКЛЮЧЕНИЯ

Дедуктивным называется умозаключение, в котором посылки и заключение

ПРАВИЛЬНЫЕ РАССУЖДЕНИЯ

Схема рассуждений называется правильной, если всякое рассуждение по этой схеме,

ПРАВИЛЬНЫЕ РАССУЖДЕНИЯ. ПРИМЕР

Схема рассуждений
правильная?

ПРАВИЛЬНЫЕ РАССУЖДЕНИЯ. ПРИМЕР

Схема рассуждений
правильная?
В рассуждении
посылки истинны, а заключение ложно.
Значит, схема

ПРАВИЛЬНЫЕ РАССУЖДЕНИЯ

Чтобы доказать, что рассуждение является неправильным, достаточно привести пример рассуждения,

БЕСКВАНТОРНЫЕ ПРАВИЛА ДОКАЗАТЕЛЬСТВА

- правила удаления конъюнкции
- правила введения конъюнкции

БЕСКВАНТОРНЫЕ ПРАВИЛА ДОКАЗАТЕЛЬСТВА

- правило удаления импликации
(modus ponens)

КВАНТОРНЫЕ ПРАВИЛА ДОКАЗАТЕЛЬСТВА

- правило конкретизации
- правило доказательства
утверждений

КВАНТОРНЫЕ ПРАВИЛА ДОКАЗАТЕЛЬСТВА

- правило частного заключения
- кванторные правила де

ФОРМАЛИЗАЦИЯ ДОКАЗАТЕЛЬСТВ

В учебниках (школьных, вузовских) доказательства даются как содержательные, поскольку излагаемые

МЕТОДЫ ДОКАЗАТЕЛЬСТВА

Всякое математическое доказательство построено в соответствии с правилами доказательства, т.е.

МЕТОДЫ ДОКАЗАТЕЛЬСТВА. ОБОЗНАЧЕНИЯ
Предложение в квадратных скобках обозначает допущение. Двойная черта означает,

МЕТОД ДОКАЗАТЕЛЬСТВА ПРИВЕДЕНИЕМ К НЕЛЕПОСТИ (REDUCTION AD ABSURDUM)

Пусть А –

МЕТОД ДОКАЗАТЕЛЬСТВА ОТ ПРОТИВНОГО

Пусть А – произвольное предложение. При доказательстве этим

СПОСОБЫ ДОКАЗАТЕЛЬСТВА МАТЕМ. ТЕОРЕМ

косвенного доказательства
доказательства разбором случаев,
от противного (приведения

ЛОГИЧЕСКИЕ ЗАДАЧИ

В таких задачах, как правило, имеется ряд высказываний, относительно

ЛОГИЧЕСКИЕ ЗАДАЧИ

В нашем примере так как два высказывания истинны, то

ЛОГИЧЕСКИЕ ЗАДАЧИ. ЗАДАЧА ПРО ТУРИСТА.

Турист направлялся к озеру и дошел до

ЛОГИЧЕСКИЕ ЗАДАЧИ. ЗАДАЧА ПРО ТУРИСТА.

Решение. Очевидно, что вопрос должен быть составным