Самостоятельная работа тема: Алгебра предикатов, понятия формулы обратной связи. Вариант-20 Студента группы

Применение языка логики предикатов в математике
Язык логики предикатов удобен для записи математических предложений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства.
Приведем примеры записи определений математического анализа в виде предикатных форму.
Примечание.
При записи определений используется символ " ", который читается " по определению…, если… ".
1) Определение числовой последовательности:
, ("по определению число есть предел последовательности , если для любого положительного числа найдется такое натуральное число , что для всех натуральных чисел из выполнения неравенства следует, что "),
где , , - член последовательности с номером , предикат – трехместный предикат, представляющий импликацию двуместных предикатов, , .
2) Определение возрастающей функции.
Пусть . По определению есть возрастающая на множестве функция, если , (…для любого числа из множества и любого числа из этого же множества неравенство влечет за собой неравенство ).
Двуместный предикат есть импликация двуместных предикатов и .
Многие теоремы математики допускают формулировку в виде условных предложений.
Примеры.
1. Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла.
2. Система линейных алгебраических уравнений имеет решение тогда и только тогда, когда ранг главной матрицы системы равен рангу ее расширенной матрицы.
3. Квадрат гипотенузы равен сумме квадратов катетов. Эту знаменитую теорему можно переформулировать так: " Для того, чтобы треугольник был прямоугольным, необходимо и достаточно, чтобы квадрат длины одной из его сторон был равен сумме квадратов длин других его сторон".
Такие формулировки являются импликациями или эквиваленциями предикатов, переменные в которых связаны кванторами.
Пусть импликация представляет условие и заключение некоторой теоремы. Рассмотрим еще три импликации, которые можно построить из предикатов и :
– обратная импликация,
– противоположная импликация,
– импликация обратная противоположной.
Поскольку для эквиваленции справедливо равенство (см. табл. 5.5), то есть смысл рассматривать лишь противоположную ей эквиваленцию Из таблиц истинности импликации и эквиваленции (см. табл. 5.4, 5.5) получаем таблицы соответствующих высказываний.

Таблица 5.7 Таблица истинности импликаций и эквиваленций
0	0	1	1	1	1	1	1	1	1
0	1	1	0	1	0	0	1	0	0
1	0	0	1	0	1	1	0	0	0
1	1	0	0	1	1	1	1	1	1

Очевидны равносильности: , (логический закон контрапозиции), , .

П
усть , – множества истинности предикатов и соответственно, – множества ложности. В соответствии с таблицей истинности, импликация ложна лишь в том случае, если . Такое соотношение невозможно, если (см. рис. 5.2).
Пусть ("для любого из истинности следует истинность ", или "при любом истинность является достаточным условием истинности ") является теоремой. Назовем это утверждении прямой теоремой. Тогда связанные с ней теоремы будут иметь следующие названия:
("для любого из истинности следует истинность ") – обратная теорема,
("для любого из ложности следует ложность ") – противоположная теорема,
("для любого из ложности следует ложность ") – теорема, обратная противоположной.
Если множество истинности условия импликации прямой теоремы есть подмножество множества истинности ее заключения , то импликация тождественно истинна во всей области определения переменных (см. рис. 5.2). Это означает, что высказывание является истинным и следовательно, может быть доказано тогда и только тогда, когда .
В силу закона контрапозиции включение является также условием истинности высказывания или, что то же самое, .
Высказывания и истинны при условии . Если же , но (см. рис 5.2 г), то истинность является необходимым, но не достаточным условием истинности .
Таким образом, теорема может быть прочитана так: "при любом истинность является достаточным условием истинности , а истинность – необходимым условием истинности "
Теорема будет доказана, если доказать включение . Теорема также будет доказана, если доказать включение , т.е доказать теорему, обратную противоположной . Такой метод доказательства носит название "метод от противного".
Чтобы опровергнуть теорему достаточно привести единственный контрпример, в котором истинность импликации нарушена. В самом деле, представив отрицание импликации конъюнктивной нормальной формой , получаем . Высказывание истинно, если найдется хотя бы один , при котором – истина, а – ложь.
Высказывания и истинны, когда выполняются оба включения и , т.е. .
Теорема, содержащая необходимые и достаточные условия, формулируется в виде эквиваленции: . Прочитать такое высказывание можно одним из следующих способов: "при любом истинно тогда и только тогда, когда истинным является ", " при любом истинность является необходимым и достаточным условием истинности ". Для доказательства такой теоремы приходится доказывать прямую и обратную теоремы . Доказательство прямой теоремы, служит доказательством достаточности условия , доказательство обратной – необходимости этого условия. В силу эквивалентности теорем и доказательством необходимости и достаточности условия может являться любой из следующих вариантов:
и – доказательство прямой и обратной теорем,
и – доказательство прямой и противоположной теорем,
и – доказательство теоремы обратной и теоремы противоположной обратной,
и – доказательство теоремы противоположной и теоремы противоположной обратной.
Примеры.
1. Диагонали ромба взаимно перпендикулярны.
Переформулируем теорему в виде условного предложения: "Пусть – плоский выпуклый четырехугольник, и – отрезки. Если – ромб и , – диагонали , то и взаимно перпендикулярны".
Первое предложение в этой формулировке является описанием множеств значений переменных: , , где – множество плоских выпуклых четырехугольников, – множество отрезков. Это предложение называют преамбулой теоремы.
Условие теоремы представляет собой конъюнкцию одноместного и двуместных предикатов: , где : " – ромб", : " – диагональ ", : " – "диагональ ". Предикат задан на множестве . Заключение теоремы предикат : " и взаимно перпендикулярны", заданный на множестве .