Логика и доказательство

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

Логика высказываний

Составные высказывания

Отрицание ¬ ̅

Дизъюнкция ∪(∨)+

Эквивалентность⟺
Два составных высказывания, построенные из одних и тех же простых высказываний, но разными способами, называются логически эквивалентными, если они имеют одинаковые таблицы истинности на всех возможных наборах значений истинности простых высказываний, из которых они состоят.

Пример

Импликация→⇒

Пример

Контр-позиция

Конверсия импликации
Высказывание Q→P называется конверсией импликации P→Q или обратной импликацией.
Многие из ошибок в рассуждениях происходят от смешивания высказывания с его конверсией.
Например, можно сказать, что если функция в данной точке имеет экстремум, то ее производная в этой точке равна нулю, но нельзя сказать, что если производная в данной точке равна нулю, то функция в этой точке имеет экстремум (м.б. это точка перегиба).

С импликацией связано понятие необходимых и достаточных условий в математике

Антиоперации

Тождественно истинные и ложные высказывания
Составные высказывания, принимающие истинные значения при любых истинносных значениях своих компонент называются тавтологиями или тождественно истинными.
Составные высказывания, принимающие ложные значения при любых значениях своих компонент называются противоречивыми или тождественно ложными.

Приоритет операций

Следствие и совместность
Из высказывания Р следует высказывание Q, если Q истинно всякий раз, когда истинно Р.
Говорят, что два высказывания являются логически несовместными, если из истинности одного необходимо следует ложность другого.
Для проверки совместности высказываний по таблице истинности смотрят, есть ли хоть одна строка, где все составные высказывания истины, и если есть, то они совместны.

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

Предикаты

Кванторы

Пример

Примеры

Отрицание кванторов

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

Типы доказательств

Примеры

Решения

Решения

Метод математической индукции

Пример

Решение

Принцип математической индукции
Проверить справедливость утверждения при n=1.
Предположив, что утверждение верно при n=k, доказать, что оно верно при n=k+1.
Тогда утверждение верно ∀ n ∈ N.

1+2+3+…+100= 1+2+…+n=
Рачинский «Устный счет»
(102+112+122+122+142)/365

Пример

Решение

КОРРЕКТНОСТЬ АЛГОРИТМОВ
Приложение.

Корректность простого оператора

Пример

Корректность составного оператора

Пример

Решение

Корректность условного оператора

Пример

Корректность циклов

Пример