Множества, отображения, логика (стр. 6 )

4.15. Операции над предикатами — конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание — выполняются по аналогии с операциями над высказываниями.

4.16. Теоремы. Теорему можно записать в виде «Для любого х, если Р(х), то Q(х)» или ("х) Р(х) Þ Q(x). Это означает, что получившееся высказывание является истинным, т.е. теорема верна. Высказывание ("х) Р(х) называется посылкой, а высказывание ("х) Q(x) — заключением теоремы.

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

·          обратную ,

·          противоположную

·          обратную противоположной .

С помощью таблицы истинности легко доказать закон контрапозиции:

.

Это означает, что если верна теорема , то верна и теорема, обратная противоположной, .

4.17. Пример 4. Рассмотрим (см. п. 1.7) два одноместных предиката: А(n) = «Целое число n делится на 4», В(n) = «Целое число n делится на 2». Предикат  является тождественно истинным на множестве Z целых чисел, т.е. высказывание ("nÎZ) A(n) Þ B(n) истинное. Записав четыре теоремы:

(1) ,

(2) ,

(3) ,

(4) ,

видим, что (1) и (4) — верные, а (2) и (3) — неверные теоремы. Таким образом, для данной теоремы обратная теорема не всегда верна.■

4.18. Необходимые и достаточные условия. Рассмотрим импликацию A(n) Þ B(n) предикатов A(n), B(n) из примера 4.17. Прежде всего, заметим, что множество истинности предиката А(n) есть множество

,

состоящее из целых чисел, кратных 4, множество истинности предиката В(n) есть множество

,

элементами которого являются все четные числа. Легко убедиться, что [A(n)] Ì [B(n)]. В таких случаях говорят, что A(n) является достаточным условием для B(n), а В(n) является необходимым условием для А(n).

Таким образом, если теорема сформулирована в виде А Þ В, то ее можно прочесть словесно следующими равносильными способами:

·     если А, то В

·     для того чтобы В, достаточно А

·     для того чтобы А, необходимо В

·     из А с необходимостью следует В.

Если предикат А является одновременно необходимым и достаточным условием для В, то верна теорема А Þ В и обратная ей теорема В Þ А, т.е. теорема (А Þ В) Ù (В Þ А), которая равносильна (см. п. 4.8) теореме А Û В; последняя читается одним из следующих способов:

·     для того чтобы А, необходимо и достаточно В

·     А, если и только если В

·     А в том и только в том случае, когда В.

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

Примем два (исходных) правила вывода:

1)    из А и А Þ В выводимо В,

2)    из Р(х) выводимо ("х) Р(х).

Правило 1) называется Modus Ponens или правилом заключения, правило 2) — правилом обобщения или правилом связывания квантором общности. Правило заключения символически записывается следующим образом:

.

Пример 5. Металл — проводник; железо — металл. Следовательно, железо — проводник. Это умозаключение символически запишется так:

 

металл — проводник, железо — металл

железо — проводник.■

 

Из основных правил вывода 1), 2) можно вывести и другие правила, которые упростят доказательства:

3)    правило введение конъюнкции

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

5)    правило силлогизма

6)    правило отрицания

7)    правило контрапозиции

8)    правило расширенной контрапозиции

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

10)  правило сведения к абсурду .

4.20. Доказательство методом от противного основано на правиле отрицания. Пусть мы хотим доказать теорему А Þ В, исходя из того что А — истина. Делаем предположение, что  — истина. Затем логическими средствами приходим к тому, что  — истина. Появление двух противоречащих друг другу высказываний А и  свидетельствует о наличии противоречия, которое может быть снято только отказом от сделанного предположения:  — ложь, следовательно, В — истина.

4.21. Определения. Как отмечалось в п. 1.2, определения имеют специальную структуру. Для формулировки определения понятия математического объекта (например, прямоугольника) должны быть выполнены следующие условия:

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

2) формулируется характеристическое свойство, видовое отличие, b (наличие прямого угла в параллелограмме)

3) выделяется подмножество K Ì М объектов (называемых прямоугольниками) со свойством b.

Другой пример: животное и лошадь; понятие «животное» — род, а понятие «лошадь» — вид. Прикольный пример: люди и зайцы; люди — род, зайцы — вид.

С теоретико-множественной точки зрения множество K определяемых объектов (всех прямоугольников) является подмножеством множества М (всех параллелограммов):

х обладает свойством b},

при этом слева от вертикальной черты указан родовой признак (х является параллелограммом), а справа — видовое отличие, характеристическое свойство b (параллелограмм х имеет прямой угол).

Логическая структура определения имеет вид высказывания:

("x Î M) A(x) Û B(x),

где М — род — множество всех параллелограммов, А(х) = «х называется прямоугольником» — предикат, вводящий новое понятие, В(х) = «в параллелограмме х все углы — прямые» — предикат, содержащий характеристическое свойство. Это высказывание звучит так: «Параллелограмм х называется прямоугольником тогда и только тогда, когда у параллелограмма х имеется прямой угол». После литературной обработки определение становится более благозвучным: «Прямоугольником называется параллелограмм с прямым углом».

Определения должны удовлетворять трем требованиям:

·          они не должны приводить к порочному кругу,

·          каждое понятие должно определяться один раз,

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

4.22. Двоичная арифметика. В позиционной системе счисления с основанием р любое натуральное число х Î N записывается последовательностью  цифр  (см. п. 3.14), что означает