Понятие об аксиоматической теории

Одной из особенностей математики двадцатого столетия является построение аксиоматических теорий во многих ее об­ластях. Аксиоматический подход использовался еще Евклидом в его "Началах" при изложении основ классической геометрии, но лишь в двадцатом столетии он получил широкое распространение. "Начала" Евклида построены следующим образом. Сначала были выделены так называемые первичные объекты, точка, прямая и плоскость. Затем сформировались предложения, описывающие отношения между первичными объектами. Некоторые из них он назвал аксиомами, другие - постулатами. Далее с помощью первичных объектов определялись некоторые другие вспомогательные понятия, затем из аксиом и постулатов выводились новые свойства первичных и определенных с их помощью объектов. Эти свойства назывались теоремами.  Евклид считал, что значения таких терминов, как “точка”, "прямая" и "плоскость" достаточно ясны, и относящиеся к ним аксиомы - "самоочевидные истины". Такое толкование термина "аксиома" широко распространено и в наше время в нематематических текстах. Внутри самой математики это понятие претерпело значительную эволюцию. Первым шагом в этом направлении было открытие Н.И.Лобачевским и (независимо от него) венгерским математиком Я.Бойаи неевклидовой геометрии. Список аксиом этой геометрии получается из списка аксиом евклидовой геометрии заменой аксиомы параллельности (пятого постулата) ее отрицанием. А именно, этот постулат в геометрии Лобачевского формули руется следующим образом: Если на плоскости точка А не лежит на прямой l, то существует более чем одна прямая, проходящая через А и параллельная l. Мы хорошо знаем, сколь велико было сомнение современников Н.И.Лобачевского в "истинности" новой геометрии. Подробное освещение исторических фактов, связанных с развитием и становлением геометрии Лобачевского, выходит за рамки этой книги. Скажем лишь, что впоследствии, в связи с построением различных интерпретаций неевклидовой геометрии, изменилось отношение к аксиоматической теории и ее роли в математике.

Аксиоматическая теория строится следующим образом.

Фиксируется некоторое множество S логических формул, например, формул исчисления высказываний. Никакого значения истинности заранее этим формулам не приписывается. Без ущерба для общности в дальнейшем вместо слов "логическая формула" будем употреблять термин "высказывание". Формулы, входящие в S, называются аксиомами (первичные предложения).

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

                                  (*)

удовлетворяющие специальным требованиям: каждое высказывание, входящее в последовательность (*), является либо аксиомой, то есть принадлежит исходному множеству S, либо тавтологией, либо получается из предыдущих высказываний последовательности (*) по некоторым правилам (схемам) вывода.

Правила вывода фиксируются заранее. Они устроены таким образом, что в процессе их применения из предложений, к которым они применяются, получается их логическое следствие. Любая последовательность высказываний , построенная описанным выше способом, называется доказательством или логическим выводом из S. В некоторых случаях аксиомы, входящие в логический вывод, называются посылками (этого вывода).

Любое высказывание А, которое входит в некоторое доказательство (то есть совпадает с одним из высказываний  последовательности (*)), называется выводимым из S или теоремой теории, аксиомами которой служат высказывания, входящие в исходное множество S.

Таким образом, под теорией подразумевается множество всех предложений, выводимых из данного множества Sаксиом

Сделаем несколько очевидных следствий из определения логического вывода.

1. Любая аксиома данной теории является теоремой. Это утверждение справедливо и для любой тавтологии.

2. Очевидно, если в логическом выводе, начиная с некоторого номера i, отбросить все высказывания, то снова получится вывод из S, то есть, если - логический вывод из S, то также является логическим выводом из S. Поэтому наряду с приведенными определениями можно встретить следующее: "Высказывание В называется выводимым из множества высказываний S, если существует логический вывод , последним звеном которого служит это высказывание".

3. Если - вывод из S, то эта последовательность является выводом из множества , где   есть множество всех аксиом, входящих в данный логический вывод.

4. Чрезвычайно важным обстоятельством является следующий факт, который легко усматривается из определения логического вывода: каждое высказывание, входящее в любой вы­вод из данной системы S аксиом, является логическим следствием из данной системы аксиом.

Отсюда вытекает: если каждая аксиома из 3 истолкована каким-либо способом как истинное предложение о некоторой совокупности объектов, то каждая теорема в теории (для которой S служит системой аксиом) также будет истинным утверждением о тех же объектах.

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

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

1. Правило отделения (modus ponens)

Выглядит оно следующим образом:

A, A®B├B

В словесной формулировке оно звучит так: "Если оба высказывания А и А ® В- истинны, то и В истинно". Это правило основано на тавтологии (X): А Ù (А ® В) ® В. Из нее согласно (1) имеем

А Ù(А ®В)├ B,

откуда, ввиду (2), получим A, (A®B)├B

2. Правило контрапозиции

А ® B├ Ø В ® Ø А.

В основе его лежит закон контрапозиции (XV): А ® В ≡ ØВ ®Ø A. Действительно, согласно (XV) формула А ® В ® ØВ ®Ø A является тавтологией, откуда, в силу (2), А ® B├ Ø В ® Ø А.

Например, правильность рассуждения: "В параллелограмме диагонали точкой пересечения делятся пополам. Следовательно, если в четырехугольнике диагонали точкой пересечения не делятся пополам, то четырехугольник не является параллелограммом" - гарантируется законом контрапозиции.

3. Правило силлогизма

Позволяет в любом логическом выводе при наличии в нем высказываний А ® В и В ® С поставить высказывание А ® С. Это правило основано на законе силлогизма (XI). Оно может быть записано в следующем виде:

А ® В, В ® С├ А ® С

 

Другие правила будут приведены в упражнениях (см. с. 34).

О методах доказательств. При проведении математических рассуждений часто применяются различные "процедуры" позволяющие избегать "излишних" построений при решении вопроса, является ли данное высказывание логическим следствием конкретной системы посылок. Некоторые из таких наиболее часто применяемых процедур получили название метода доказательств.

1.    Одним из таких методов является метод вспомогательной гипотезы. Он основан на следующем свойстве логического следствия: ├ A® В тогда и только тогда, когда

├ В

Это свойство обычно называют "теоремой дедукции". Справедливость легко устанавливается с помощью определений логического следствия и операции импликации.

В практике чаще всего "теорема дедукции" используется следующим образом: для построения вывода из посылок  теоремы, имеющей форму импликации А ® В, достаточно построить вывод высказывания В из посылок

Тогда в силу "теоремы дедукции" высказывание А ® В является логическим следствием посылок : Таким образом, высказывание А в этой ситуации оказывается в числе посылок (гипотез). Этим и объясняется название метода.

2.    Метод " от противного". По установившейся традиции тождественно-ложное высказывание вида СÙØСбудем называть "противоречием".

Основанием метода "от противного" служит следующее предложение: Для вывода высказывания В из посылок  достаточно показать, что из посылок логически следует некоторое "противоречие"'.

Действительно, пусть ├ С ÙØ С

Тогда по "теореме дедукции" ├ØB® С ÙØ С.

Допустим теперь, что каждая из посылок принимает значение И. Тогда импликация ØB® С ÙØ С обязана принимать значение И, откуда, поскольку С ÙØ С принимает значение Л, следует, что ØВ ложно и, значит, В истинно. Таким образом, ├ B.

Метод "от противного" чаще всего применяется в сочета­нии с методом введения вспомогательной гипотезы по следу­ющей схеме.

Допустим, что надо установить

├                                                   (3)

По "теореме дедукции" достаточно показать, что

Для этой цели в соответствии с методом "от противного" достаточно проверить, что для некоторого высказывания С выполняется       

├

Таким образом, для установления логического следствия (3) достаточно к системе посылок добавить посылки А ® В и из новой системы посылок вывести "противоречие".

На практике это введение новых посылок осуществляю словами: "Пусть А истинно, но В ложно", и далее идет поиск противоречия.

3. Метод разделения случаев опирается на следующее легко проверяемое свойство:

если ├   и ├ , то ├

Доказательство теоремы  с использованием этого метода происходит по следующей схеме:

1. Рассматривается случай, когда А истинно, и доказывается, что тогда и С истинно. Этим самым устанавливается, что 

├

 

2. Затем показывают, что в случае, если В истинно, то
высказывание С также истинно, т.е.

├

3. После этого делается заключение, что

├

Как уже отмечалось, утверждения, рассматриваемые в ма­тематике, имеют, как правило, форму импликации: "Если А, то В". Например, в утверждении: "Если дискриминант , то квадратное уравнение  име­ет два различных действительных корня" высказывание "дис­криминант " является посылкой, а высказывание "квадратное уравнение  имеет два различных действительных корня" - заключением.

Доказательство любого утверждения, имеющего форму им­пликации А ® В, состоит в построении вывода утверждения В из аксиом и утверждения А (см. метод вспомогательной гипотезы). Если такое доказательство осуществимо, то гово­рят, что А является достаточным условием для В, а В - необходимым условием для А. Например, в утверждении: "Если произведение двух натуральных чисел делится на прос­тое число, то на него делится один из сомножителей", высказы­вание "произведение двух натуральных чисел делится на прос­тое число" является достаточным условием для высказывания "на простое число делится один из сомножителей", а второе высказывание - необходимым условием для первого.

Допустим теперь, что справедливы оба утверждения А ® В и В ® А. Тогда каждое из двух высказываний А и В является одновременно и необходимым и достаточным усло­вием для другого, и эти высказывания равносильны. Поэтому утверждение (высказывание), что А является необходимым и достаточным условием для В, записывают в виде . Читается: " А необходимо и достаточно для В ", "А имеет место тогда и только тогда, когда справедливо В ". Например, высказывание "Диагонали четырехугольника точкой их пере­сечения делятся пополам" необходимо и достаточно для выска­зывания "Четырехугольник является параллелограммом".

Построим из высказываний А и В с помощью отрицания и импликации следующие утверждения:

1. (“если A, то B”).

2. (“если B, то A”).

3. (“если не A, то не B”).

4.  (“если не B, то не A”).

Утверждения 1, 2, так же, как и утверждения 3 и 4, назы­ваются взаимно обратными.

Утверждения 1 и 3 (значит, и утверждения 2 и 4) назы­ваются взаимно противоположными.

Простые примеры показывают, что истинность или лож­ность одного из двух взаимно обратных (или противополож­ных) утверждений не влечет за собой, вообще говоря, ни ис­тинности, ни ложности другого высказывания. Например, ес­ли А- утверждение "четырехугольник является ромбом",  В- утверждение "диагонали четырехугольника взаимно пер­пендикулярны", то утверждение истинно в то время, как утверждение - ложно, утверждение - истинно, а утверждение - ложно.

Заметим, что по закону " контрапозиции" высказывания 1 и 4, а также 2 и 3 равносильны между собой.

Ясно, что если утверждение А ® В есть теорема, то обратное утверждение В ® Аравносильно первому тогда и только тогда, когда В есть необходимое и достаточное условие для А. В этом случае все четыре утверждения равносиль­ны, т.е. являются теоремами и носят следующие названия:

- прямая теорема;

- обратная теорема;

- теорема, противоположная прямой;

- теорема, противоположная обратной.

§ 8. Предикаты

Рассмотрим предложение "х есть четное число". Его нельзя назвать высказыванием, поскольку невозможно решить вопрос, является ли это предложение истинным или ложным. Но оно становится высказыванием, как только переменная x принимает какое-нибудь конкретное значение.

Таким образом, данное предложение определяет некоторую функцию, заданную на множестве Z целых чисел со значениями во множестве {И, Л}.

В более общей ситуации будем говорить, что на множестве X задан предикат, от переменных   или n-местный предикат , если каждому набору значений этих переменных поставлено в соответствие впол­не определенное значение истинности: И или Л.

Примеры:

1. На множестве N натуральных чисел задан предикат Р(х): "х есть простое число". Тогда, например, запись P(3) -И будет означать, что предикат при х = 3 превращается в истинное высказывание, т.е. "3 - простое число", а Р(6)-Л означает, что число 6 не является простым.

2. На множестве рассмотрим предикат Q (х,у): "х явля­ется делителем у ". Очевидно, что Q (2, 6) - И, а Q (3,10) - Л.

Если на множестве X задан п- местный предикат , то множество

всех наборов , при которых предикат превращает­ся в истинное высказывание, называется областью истинно­сти данного предиката.

Очевидно, что для задания предиката на множестве X до­статочно указать его область истинности.

Логические операции над предикатами. К предика­там применимы все операции логики высказываний. Это об­стоятельство дает возможность образовывать из некоторых фиксированных предикатов новые, более сложные.

Например, пусть на множестве X заданы два предиката P(x) и Q(х). Тогда дизъюнкцией их называется предикат P(x) Ú Q(х),  который превращается в ложное высказывание при тех и только тех значениях переменного х Î X, при которых каждый из предикатов P(x), Q(х) превращается в ложное высказывание.

Аналогично определяются операции: отрицание, конъюнк­ция, импликация и эквиваленция.

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

Пусть предикат Р(x) задан на множестве А. Тогда Р(x) называется тождественно истинным, если его область истин­ности совпадает с областью определения А, т.е. Р(а) - И при любом значении а Î А.

Предикат называется тождественно ложным, если его об­ласть истинности пуста, т.е. Р(а) - Л для любого элемента а Î А.

Кванторы. Всякому одноместному предикату Р(х) на множестве А поставим в соответствие высказывание , которое считается истинным тогда и только тогда, когда об­ласть истинности предиката Р(х) не пуста. Другими слова­ми, высказывание  ложно тогда и только тогда, ког­да Р(х) - тождественно ложный предикат на множестве А. Высказывание читается так: "Существует х Î А такое, что Р(х) ". Логический знак  называется квантором существования.

Из предиката Р(x) можно построить другое высказывание , читается: "Для всех х справедливо Р(x) " или, более кратко: "Для всех х Р(х) ".

Высказывание считается по определению истин­ным тогда и только тогда, когда Р(х) - тождественно ис­тинный предикат на множестве А.

Знак  называется квантором общности. Пусть, напри­мер, предикат определен на множест­ве целых чисел Z. Тогда высказывание - истинно, а - ложно. Приписывание к предикату одного из знаков ,  называется операцией навешивания квантора или связы­вания квантором.

Применение этой операции к одноместному предикату по определению превращает этот предикат в высказывание.

Навешивание квантора на многоместный предикат пони­жает местность этого предиката на единицу.

Например, если на множестве А задан двухместный преди­кат Р(х, у), то предложение  является одноместным предикатом от переменной у. Переменная x в этом предикате уже не играет роли переменной, поскольку истинность предложения зависит только от значения у.

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

Кванторы  и  широко используются в математике для сокращенной записи математических предложений.

Например, пусть f(x) - функция действительного перемен­ного. Тогда истинность высказывания

означает, что Т - период функции f(x).

 Если высказывание

истинно, то b является пределом функции f(x) в точке x.

Законы логики предикатов. Пусть Р(х) и Q(x) - пре­дикаты, определенные на множестве A. Будем говорить, что предикат Р(х) равносилен предикату Q(x), и записывать Р(х) = Q(x), если они принимают одинаковые значения ис­тинности при любом значении переменного х Î А.

Аналогично определяется отношение равносильности для многоместных предикатов. Очевидно, что предикаты Р(х) и Q(х) равносильны тогда и только тогда, когда их эквиваленция Р(х) «Q(x) является тождественно истинным преди­катом.

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

1. " х " уР(x,у) ≡ " у " хР(х,у), $ х $ уР(х,у) ≡ $ у $ хР{х,у) (перестановочность одноименных кванторов).

2. " х (Р(x) Ù Q (x)) ≡" x Р(х) Ù" xQ(x) (дистрибутивность квантора общности относительно конъюнкции).

3. $ х (Р(x) Ú Q (x)) ≡$ x Р(х) Ú$ xQ(x) (дистрибутивность квантора относительно конъюнкции).

4. Ø" xP(x) º$ x Ø P(x) (закон отрицания квантора общности).

5. Ø$ х Р(х) º" x Ø P(x) (закон отрицания квантора существования).

Равносильности 4 и 5 по традиции называются законам де Моргана логики предикатов.

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

В качестве примера убедимся в справедливости закона отрицания квантора существования 5.

Пусть, например, высказывание Ø$ х Р(х) истинно. Том да высказывание $х Р(х) ложно. Это означает, что Р(х) - тождественно ложный предикат, а значит, Ø Р(х)- тождественно истинный предикат. Следовательно, высказывание " x Ø Р(x) истинно.

Обратно, пусть " x Ø Р(x) - истинное высказывание. Проделав предыдущие рассуждения в обратном порядке, получим что высказывание Ø$ х Р(х) также истинно.

Таким образом, Ø$ х Р(х) º " x Ø Р(x).

Упражнения:

1. Докажите справедливость утверждения: формулы F и Y логики высказываний равносильны тогда и только тогда, когда их конъюнкция Ф «Y является тавтологией.

2. Докажите равносильности I-ХV, указанные на с. 21.

3. Докажите справедливость утверждений для любых формул логики высказываний:

(а) если ├ F,..., ├ Ф, то ├ Ф; (Ь) если Ф

(б) если Ф├ ,…, Ф├  то Ф├ Ù…Ù .

4. F º Y тогда и только тогда, когда Ф ├ Y и Y├Ф.

5. Если Ф ├ Y и Y ├ Q, то Ф ├ Q.

6. Обосновать следующие правила вывода для любых формул А, В логики высказываний:

a) A ├ A Ú B;

b) А,В├ АÙ В;

c) ØА ├ А ® В;

d) А Ú В, Ø А ├ В;

e) AÙB├A;

f) А ® В, ØВ ├ А.

7. Найти области истинности предикатов, заданных на мно­жестве А = {1,3,4,6,7,9,12}:

a) Р(х): " х - нечетное число";

b) Q(х,у):"х -делитель у";

c) S (х, у, z): "разность (x - у) делится на z ".

 8. На множестве X заданы предикаты Р(x) и Q(x).

a) Сформулировать определение каждой из операций Ø, Ù, Ú, ®, «над предикатами Р(x) и Q(х).

b) Пусть и  - области истинности, соответствен­но, предикатов Р(x) и Q{х). Найти область истин­ности предикатов ØР(х), Р(х) Ú Q(х), Р(х) Ù Q(х), Р(x)®Q(x), Р(х) «Q(х).

9. Пусть - конечное множество и Р(х) - одноместный предикат, заданный на множестве А. До­кажите:

a) ;

b) .

10. Докажите основные равносильности 1-4, приведенные на с. 33.

11. Пусть Р(x, у, z) - предикат, определенный на множестве A.

a) Какие из следующих предикатов являются одномест­ными предикатами и от какой переменной:

b) Какие из предложений, указанных в предыдущей пункте, являются высказываниями?

12.   Докажите, что следующие высказывания являются ис­тинными:

a)

b)

c)

13. Привести пример предиката , для которого высказывания и   не равносильны.

14. Построить отрицания к следующим предложениям:

1. где  - функция действительного переменного;

b.

c.

d.

ГЛАВА II