Проверки индукцией: Обобщенные правила де Моргана и распределения
РЕЗЮМЕ
В этом занятии рассматривается тема проверок индукцией в математике и пропозициональной логике. Объясняются два типа проверок: внутренние или дедуктивные проверки, основанные на правилах логики, и внешние или метаматематические проверки, которые необходимы для доказательства утверждений, касающихся самой логики. Вводится математическая индукция как метод доказательства, позволяющий доказать, что определенные утверждения справедливы для всех натуральных чисел. Приводится пример с соответствующим доказательством, а также объясняются обобщенные формы законов де Моргана и распределительных законов в пропозициональной логике вместе с соответствующими доказательствами по индукции. Это занятие имеет большое значение для понимания основ математики и логики, а также для их применения в различных областях знаний.
ЦЕЛИ ОБУЧЕНИЯ:
По окончании этого занятия студент будет способен:
- Распознавать два типа проверок, которые необходимо различать: внутренние или дедуктивные проверки и внешние или метаматематические проверки.
- Применять математическую индукцию для доказательства утверждений о натуральных числах и в пропозициональной логике.
- Использовать обозначения конъюнкций и дизъюнкций для записи выражений пропозициональной логики.
- Понимать обобщенную форму законов де Моргана и распределительных законов в пропозициональной логике.
- Понимать концепцию индукционной гипотезы и её роль в доказательстве по индукции.
ОГЛАВЛЕНИЕ
ВНУТРЕННИЕ И ВНЕШНИЕ ПРОВЕРКИ
ПРОВЕРКИ ПО МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
ПРОВЕРКИ ПО ИНДУКЦИИ В ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ
ОБОБЩЕННАЯ ФОРМА ЗАКОНОВ ДЕ МОРГАНА
ОБОБЩЕННАЯ ФОРМА РАСПРЕДЕЛИТЕЛЬНЫХ ЗАКОНОВ
Внутренние и внешние проверки
Существуют два типа проверок, которые необходимо различать. До сих пор мы видели много примеров формальных проверок. Такие проверки возникают из правил логики. Эти проверки происходят «внутри логики», поэтому их также называют «внутренними» или дедуктивными проверками. Такие формальные проверки имеют ограниченный подход, так как они служат только для доказательства утверждений, которые могут быть записаны на языке логики. Однако, возможно, мы захотим проверить некоторые вещи о самой логике. Мы могли бы захотеть доказать, что все утверждения пропозициональной логики обладают определенным свойством. Такие утверждения, касающиеся самой логики, не могут быть ни установлены, ни доказаны внутри самой логики. Для доказательства таких утверждений мы используем внешние проверки. Внешние проверки иногда называют «метаматематическими», и мы уже сталкивались с такими вещами, как (мета)теорема дедукции. Здесь мы и вводим контекст для индуктивных проверок.
Проверки по математической индукции
Математическая индукция — это метод доказательства, который позволяет доказать, что некоторые утверждения справедливы для всех натуральных чисел.
ПРИМЕР:
Возможно доказать, что любое число вида 11^n - 4^n, где n — любое натуральное число, всегда делится на 7.
ДОКАЗАТЕЛЬСТВО: Если мы посмотрим на случай n=1, то увидим, что:
11^1 - 4^1 = 7
что, очевидно, делится на 7.
Теперь предположим, что 11^n - 4^n делится на n=k. Исходя из этого, мы докажем, что следовательно, это выражение также будет справедливо для n=k+1. Это можно сделать следующим образом:
Следовательно, если 11^k - 4^k делится на 7, то, следовательно, будет делиться и 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}, что эквивалентно утверждению, что 11^{k+1} - 4^{k+1} делится на 7. Таким образом, если 11^k - 4^k делится для k=1, то оно будет делиться для k=2, k=3, k=4,\cdots и так далее, и, следовательно, делиться для любого n\in\mathbb{N}. Когда это происходит, мы говорим, что индукция завершена. ■
Проверки по индукции в пропозициональной логике
Для проверок по индукции, которые мы будем проводить далее, сначала необходимо ввести следующее соглашение о нотации
НОТАЦИЯ: Пусть F_1,\cdots, F_n — конечный набор любых выражений пропозициональной логики. Вводятся конъюнкции и дизъюнкции этих выражений через:
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
С помощью этого мы теперь можем рассмотреть следующие две обобщенные формы.
Обобщенная форма законов де Моргана
Данный конечный набор выражений пропозициональной логики F_1,\cdots, F_n, всегда будет обладать следующими двумя свойствами:
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
ДОКАЗАТЕЛЬСТВО: Сначала мы докажем по индукции для n, что \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
Сначала необходимо проверить, что происходит в начальном случае n=1. В этом случае очевидно, что \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Теперь предположим, что свойство выполняется для некоторого n=k; то есть, что для данного конечного набора выражений F_1, F_2, \cdots, F_k выполняется следующее:
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Тогда мы докажем, что следовательно, верно
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
Используя определение конъюнкции, мы получаем:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
На это выражение можно применить законы де Моргана (обычные для двух членов), чтобы получить:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Теперь, если применить индукционную гипотезу, мы получим:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
И поэтому индукция завершена, и свойство выполняется для любого n в общем. Второе соотношение можно получить совершенно аналогичным образом, поэтому я оставлю это как упражнение для читателя, ха-ха!
Обобщенная форма распределительных законов
Аналогично законам де Моргана, законы распределения можно обобщить следующим образом. Пусть \{F_1, \cdots, F_n\} и \{G_1,\cdots, G_m\} два конечных множества произвольных выражений, тогда выполняются следующие эквивалентности:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
ДОКАЗАТЕЛЬСТВО: Чтобы построить это доказательство, необходимо провести двойную индукцию по n и m. Далее я проведу индукцию сначала по n, а затем по m для выражения \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
Если взять m=1, тогда это выражение записывается как
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
Что эквивалентно утверждению:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Теперь мы докажем это выражение по индукции по n.
Если взять n=1, тогда выражение сводится к
F_1 \vee G_1 \equiv F_1 \vee G_1.
Что уже известно, как верное. Теперь предположим, что оно выполняется для любого n=k; то есть индукционная гипотеза будет:
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Тогда, исходя из этого, покажем, что оно выполняется для n=k+1.
По определению конъюнкции имеем:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
Теперь, используя \vee-распределение, получим:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
И в этот момент можно использовать индукционную гипотезу, чтобы получить:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
Таким образом, мы доказали по индукции, что для любого n\in\mathbb{N} выполняется
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
Завершив индукцию по n, мы подтвердили, что начальный случай для m=1, выполняется, теперь остается завершить индукцию по m. Для этого установим индукционную гипотезу для некоторого m=l, то есть, что выполняется
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
и на основе этого мы докажем, что оно также выполняется для m=l+1.
Как обычно, начиная с определения конъюнкции, мы имеем
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
Теперь, используя \vee-распределение, получаем
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Следовательно, используя индукционную гипотезу, можно написать
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
И если теперь принять результат индукции по n
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
Что, наконец, по определению конъюнкции остается
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
Таким образом, индукция по m завершена, и выражение
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
действительно для любого n,m\in\mathbb{N}.
Этот обзор доказательств индукцией продемонстрировал, как можно применять строгие математические методы доказательства не только в области натуральных чисел, но и в пропозициональной логике. С помощью индукции нам удалось установить достоверность обобщенных форм законов де Моргана и распределительных законов, укрепляя тем самым понимание логических основ, лежащих в основе различных областей математического знания. Этот подход не только важен для развития навыков абстрактного мышления, но и служит мощным инструментом для решения сложных проблем в математике и за её пределами.