Понятие теоремы в алгебре высказываний

В математике утверждения, выводимые из аксиом, определений и ранее доказанных утверждений, называются теоремами. В алгебре высказываний теоремой называют истинное высказывание вида . В теореме высказывание называется условием теоремы, высказывание - заключением теоремы.

Различают простые и составные теоремы. Теорема называется простой, если высказывания и являются простыми. Теорема называется составной, если хотя бы одно из высказываний или является составным. Поскольку понятие простого (составного) высказывания является относительным, то и понятие простой (составной) теоремы является относительным.

Иногда доказательство составной теоремы можно свести к доказательству нескольких простых теорем.

Теорема 4. Пусть - теорема и . Тогда .

Доказательство. Используя равносильные преобразования формул АВ, получим . Теорема доказана.

Теорема 5. Пусть - теорема и . Тогда .

Доказательство. Используя равносильные преобразования формул АВ, получим . Теорема доказана.

Взаимно обратные и взаимно противоположные теоремы

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

Пусть - теорема. Если в теореме условие заменить на заключение , то получим теорему , т.е. теорема является обратной теореме . Поэтому теоремы и называют взаимно обратными теоремами.

Если в теореме условие заменить его отрицанием , а заключение заменить отрицанием , то получим утверждение, которое называется утверждением, противоположным теореме , и обозначается , т.е. . Если утверждение является теоремой, то она называется теоремой, противоположной теореме .

Пусть - теорема. Если в теореме условие заменить его отрицанием , а заключение заменить отрицанием , то получим теорему , т.е. теорема является противоположной теореме . Поэтому теоремы и называют взаимно противоположными теоремами.

Рассмотрим утверждения, обратное противоположному и противоположное обратному:

; .

Таким образом, .

Замечание 1. Поскольку , т.е. утверждения и равносильны, то утверждение, обратное противоположному теореме , всегда является истинным.

Замечание 2. Поскольку , то утверждение, обратное теореме , является истинным тогда и только тогда, когда утверждение, противоположное теореме , является истинным.

Необходимые и достаточные условия в теореме

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

Пример 1. Сформулируем теорему «Если целое число a делится на 9, то число а делится на 3» с использованием слов «необходимо» и «достаточно»:

- «Для того, чтобы целое число а делилось на 3, достаточно, чтобы число а делилось на 9»;

- «Для того, чтобы целое число а делилось на 9, необходимо, чтобы число а делилось на 3».

Замечание 3. Если утверждение является теоремой, то в теореме высказывание также является и необходимым условием для (а является достаточным условием для ), т.е. - необходимое и достаточное условие для (а также, - необходимое и достаточное условие для ). Высказывание в этом случае называют критерием (для ).