Одной из особенностей математики двадцатого столетия является построение аксиоматических теорий во многих ее областях. Аксиоматический подход использовался еще Евклидом в его “ Началах“ при изложении основ классической геометрии, 
но лишь в двадцатом столетии он получил широкое распространение. ” Начала“ Евклида построены следующим образом. Сначала были выделены так называемые первичные объекты, точка, прямая и плоскость. Затем сформировались предложения, описывающие отношения между первичными объектами: 
Некоторые из них он назвал аксиомами, другие — постулатами. Далее с помощью первичных объектов определялись некоторые другие вспомогательные понятия, затем из аксиом и постулатов выводились новые свойства первичных и определенньпс с их помощью объектов. Эти свойства назывались теоремами. Евклид считал, что значения таких терминов, как точка“, “ прямая“ и ”плоскость” достаточно ясны, и относяЩиеся к ним аксиомы — ” самоочевидные истины“ . Такое толкование термина ” аксиома“ широко распространено и в наше время в нематематических текстах. Внутри самой математики это понятие претерпело значительную эволюцию. Первым шагом в этом направлении было открытие Н.И.Лобачевским и (независимо от него) венгерским математиком Я.Бойаи неевклидовой геометрии. СПИсок аксиом этой геометрии получается из списка аксиом евклиДовоб геометрии заменой аксиомы параллельности (пятого постулата) ее отрицанием. А именно, этот постулат в геометрии Лобачевского формулируется следующим образом: Если на плоскости точка А не лежит на прямой I , то существует более чем одна прямая, просоДящая через А и параллельная I . Мы хорошо знаем, сколь велико было сомнение современников Н.И.Лобачевского в ” истинности“ новой геометрии. Подробное освещение исторических фактов, связанных с развитием и становлением геометрии Лобачевского, выходит за рамки этой книги. Скажем лишь, что впоследствии, в связи с построением различныс интерпретаций неевклидовой геометрии, изменилось отношение к аксиоматической теории и ее роли в математике.
Аксиоматическая теория строится следующим образом.
Фиксируется некоторое множество S логическис формул, например, формул исчисления высказьтаний. Никакого значения истинности заранее этим формулам не приписывается. Без ущерба для общности в дальнейшем вместо слов логическая формула“ будем употреблять термин ”высказывание” . Формулы, всоДящие в S , называются аксиомами (первичные предложения 
Далее рассматриваются всевозможные конечные последовательности высказываний
удовлетворяющие специальным требованиям: кажДое высказывание, всоДящее в послеДоват.ельность является либо аксиомой, то есть принаДлежит иссоДному множеству S 
либо тавтологией, либо получается из преДыДущис высказываний послеДовательности (*) по некоторым правилам (ссемам) вывоДа.
Правила вывоДа фиксируются заранее. Они устроены таким образом, что в процессе их применения из предложений, к которым они применяются, получается их логическое следствие. Любая последовательность „41 , . . . , Ак высказываний, построенная описанным выше способом, называется Доказательстеом или 
выводом из S . В некоторых случаях аксиомы, входящие в логический вывод, называются посылками (этого вывода) 
Любое высказывание А , которое входит в некоторое доказательство (то есть совпадает с одним из высказываний Ат последовательности (*)), называется вывоДимым из S или теоремой теории, аксиомами которой служат высказывания, входящие в исходное множество S 
Таким образом, под теорией подразумевается множество всес преДложений, вывОДиМЫС из данного множества S аксиом.
Сделаем несколько очевидных следствий из определения логического вывода.
1. Любая аксиома Данной теории является теоремой. Это утверждение справедливо и для любой тавтологии.
2. Очевидно, если в логическом выводе, начиная с некоторого номера i , отбросить все высказывания, то снова получится вывод из S , то есть, если 141, . 
. , Ак — логический вывод из S , то „41, . Ai—1 также является логическим выводом из S . Поэтому наряду с приведенными определениями можно встретить следующее: ”Высказывание В называется выВОДИМЫМ из множества высказываний S , если существует логический вывод А А . , Ак = В , послеДнтим звеном которого служит это высказывание 
З. Если „41, . . , Ак — вывод из S , то эта последователь, ность является выводом из множества S1 С S , где S1 есть множество всех аксиом, входящих в данный логический вывод.
4. Чрезвычайно важным обстоятельством является следующий факт, который легко усматривается из определения логического вывода: кажДое высказывание, всоДящее в любой вывод из Данной системы S аксиом, является логическшм следствием из Данной системы аксиом.
Отсюда вытекает: если кажДая аксиома из S истолкое ана каким-либо способом тсатс истинное преДложение о некоторой совокупности объектов, то кажДая теорема в теории (для КОТорой S служит системой аксиом) также будет истинным утвержДением о тес же объектас.
Данное описание принципов построения аксиоматической теории не претендует на полноту изложения. Глубокое пониМание этих принципов может прийти к читателю лишь после знакомства с конкретными аксиоматическими теориями.
Заметим, что кажДая тавтология является логическим
слеДствием любыс посылок. Поэтому любая тавтология может быть принята за основу некоторого правила вывоДа. Приведем наиболее употребительные правила вывода.
1. Правило отДеления (modus ponens)
Выглядит оно следующим образом:
В словесной формулировке оно звучит так: ” Если оба высказывания А и А —» В— истинны, то и В истинно“ . Это правило основано на тавтологии (Х): А Л (А В) В. Из нее согласно (1) имеем
Ал (А— В) Н В,
откуда, ввиду (2), получим А, (А В) У— В.
2. Правило контрапозиции
В основе его лежит закон контрапозиции (ХУ): А В 
-лВ —тА. Действительно, согласно (XV) формула
(А В) ( -яВ 3,4) является тавтологией, откуда, в силу
Например, правильность рассуждения: ” В параллелограмме диагонали точкой пересечения делятся пополам. Следова тельно, если в четырехугольнике диагонали точкой пересечения не делятся пополам, то четырехугольник не является параллелограммом" — гарантируется законом контрапозиции.
З. Правило силлогизма
Позволяет в любом логическом выводе при наличии в нем высказываний А В и В С поставить высказывание А С . Это правило основано на законе силлогизма (XI). Оно может быть записано в следующем виде:
Другие правила будут приведены в упражнениях (см. с. 34).
О методах доказательств. При проведении математическИХ рассуждений часто применяются различные ” процедуры”, позволяющие избегать ” излишних“ построений при решении вопроса, является ли данное высказывание логическим следствием конкретной системы посылок. Некоторые из таких, наиболее часто применяемых процедур получили название метоДа Доказательств.
1. Одним из таких методов является метод вспомогательной гипотезы. Он основан на следующем свойстве логического следствия: 141 , , Ап Ь— А —» В тогДа и только тогДа, когДа
Это свойство обычно называют ” теоремой дедукции“. Справедливость легко устанавливается с помощью определений логического следствия и операции импликации.
В практике чаще всего теорема дедукции“ используется следующим образом: Для построения еывоДа из посылок „41, . , Ап теоремы, имеющей форму импликации А В 
Достаточно построить вывод высказывания В из посылок
Тогда в силу ” теоремы дедукции“ высказывание А В
является логическим следствием посылок „41, - . . , Ап . Таким образом, высказывание А в этой ситуации оказывается в числе посылок (гипотез). Этим и объясняется название метода.
2. Метод противного“. По установившейся традиции тождественно-ложное высказывание вида С Л -С будем называть ”противоречием“ 
Основанием метода противного“ служит следующее предложение: Для вывоДа высказывания В из посылок 141 , .
Ап Достаточно показать, что из посылок „41, .
Логически слеДует некоторое ”противоречие
Действительно, пусть „41, . , Ап, „В СЛ -С.
Тогда по ” теореме дедукции“ „41, ..,Ап -зВ С Л —С.
Допустим теперь, что каждая из посылок „41, . . , Ап приНимает значение И. Тогда импликация —яВ С л —С обязана принимать значение И, откуда, поскольку С Л —С принимает значение Л, следует, что —тВ ложно и, значит, В истинно. Таким образом, 141, . , Ап В.
Метод ” от противного“ чаще всего применяется в сочетании с методом введения вспомогательной гипотезы по следующей схеме.
Допустим, что надо установить
(з)
По теореме дедукции“ достаточно показать, что
Для этой цели в соответствии с методом ”от противного 
достаточно проверить, что для некоторого высказывания С выполняется
141, . , Ап, „В СЛ -С.
Таким образом, Для установления логического слеДствия
(З) Достаточно тс системе посылок Добавить посылки А и —лВ и из новой системы посылок вывести ”противоречие 
На практике это введение новых посылок осуществляют словами: ” Пусть А истинно, но В ложно и далее идет поиск противоречия.
З. Метод разделения случаев опирается на следующее легко проверяемое свойство:
если „41, . , Ап Ь- В —» С, ТО
Доказательство теоремы А м В С с использованием этого метода происходит по следующей схеме:
1. Рассматривается случай, когда А истинно, и доказывается, что тогда и С истинно. Этим самым устанавливается, что
, Ап А С.
2. Затем показывают, что в случае, если В истинно, то и высказывание С также истинно, т.е.
3. После этого делается заключение, что
Как уже отмечалось, утверждения, рассматриваемые в математике, имеют, как правило, форму импликации: ” Если А, то В ”. Например, в утверждении: ” Если дискриминант Ь — 4ас > 0 , то квадратное уравнение ас 2 + bc + с = 0 имеет два различных действительных корня“ высказывание ” дискриминант Ь — 4ас > 0 ” является посылкой, а высказывание 
квадратное уравнение ас 2 + bc + с О имеет два различных действительных корня“ — заключением.
Доказательство любого утверждения, имеющего форму импликации А —» В, состоит в построении вывода утверждения В из аксиом и утверждения А (см. метод вспомогательной гипотезы). Если такое доказательство осуществимо, то говорят, что А является Достаточным условием для В , а В— НеОбсоДИМЫМ условием для А . Например, в утверждении: “ Если произведение двух натуральных чисел делится на простое число, то на него делится один из сомножителей“ , высказывание ” произведение двух натуральных чисел делится на простое число“ является достаточным условием для высказывания на простое число делится один из сомножителей“ , а второе высказывание — необходимым условием для первого.
Допустим теперь, что справедливы оба утверждения А 
В и В —» А . Тогда каждое из двух высказываний А и В является одновременно и необходимым и достаточным условием для другого, и эти высказывания равносильны. Поэтому утверждение (высказывание), что А является необходимым и достаточным условием для В , записывают в виде А В 
Читается: ” А необходимо и достаточно для В ” А имеет место тогда и только тогда, когда справедливо В ” . Например, высказывание ” Диагонали четырехугольника точкой их пересечения делятся пополам“ необходимо и достаточно для высказывания Четырехугольник является параллелограммом“ 
Построим из высказываний А и В с помощью отрицания И импликации следующие утверждения:
1. А — В (”если А, то В“).
2. В А (” если В , то А“).
З. -лА -лВ (” если не А, то не В ”).
4. —тВ —тА (Н если не В , то не А“).
Утверждения 1, 2, так же, как и утверждения З и 4, называются взаимно обратными.
Утверждения 1 и З ( значит, и утверждения 2 и 4) называются взаимно противоположными.
Простые примеры показывают, что истинность или ложность одного из двух взаимно обратных (или противоположных) утверждений не влечет за собой, вообще говоря, ни истинности, ни ложности другого высказывания. Например, если А— утверждение ” четырехугольник является ромбом“ , а В— утверждение ” диагонали четырехугольника взаимно перпендикулярны”, то утверждение А —У В истинно в то время; как утверждение В А— ложно, утверждение -лА— истинно, а утверждение -лА В — ложно.
Заметим, что по закону ”контрапозиции” высказывания 1 и 4, а также 2 и З равносильны между собой.
Ясно, что если утверждение А В есть теорема, то обратное утверждение В —5 А равносильно первому тогда и только тогда, когда В есть необходимое и достаточное условие для А . В этом случае все четыре утверждения равносильны, т.е. являются теоремами и носят следующие названия:
А В — прямая теорема;
В А— обратная теорема;
-лВ — теорема, противоположная прямой;
—тВ —» --А — теорема, противоположная обратной.
8. Предикаты
Рассмотрим предложение есть четное число“. Его нельзя назвать высказыванием, поскольку невозможно решить вопрос, является ли это предложение истинным или ложным. Но оно становится высказыванием, как только переменная с принимает какое-нибудь конкретное значение.
Таким образом, данное предложение определяет некоторую функцию, заданную на множестве Z целых чисел со значениями во множестве {И, Л} 
В более общей ситуации будем говорить, что на множестве Х задан преДикат, от переменныс 21 , . или п -местный преДитсат R(21, . если тсажДому набору значений этис переменныс поставлено в соответствие вполне опреДеленное значение истинности: И или Л.
1. На множестве N натуральных чисел задан предикат 
с есть простое число“. Тогда, например, запись Р(З) —И будет означать, что предикат при с = 3 превращается в истинное высказывание, т.е. ” З — простое число”, а Р(б) —Л означает, что число б не является простым.
2. На множестве рассмотрим предикат Q(c, у) с является Делителем у ”. Очевидно, что Q(2, 6) —И, а Q(3, 10) —Л.
Если на множестве Х задан п- местный предикат
P(Z1, то множество
, сп) Р(21, 
всех наборов (Cl , ) , при которых предикат превращается в истинное высказывание, называется областью истинности данного предиката.
Очевидно, что для задания предиката на множестве Х достаточно указать его область истинности.
Логические операции над предикатами. К предикатам применимы все операции логики высказываний. Это обстоятельство дает возможность образовывать из некоторых фиксированных предикатов новые, более сложные.
Например, пусть на множестве Х заданы два предиката Р(с) и Q(c) . Тогда Дизъюнкцией ис называется преДикат Р(с) Q(c) , который превращается в ложное высказывание при тес и только тес значенияс переменного с ? Х , при которыс тсажДьи) из преДикатов Р(с), Q(z) превращается в ложное высказывание.
Аналогично определяются операции: отрицание, конъюнкция, импликация и эквиваленция.
Эти определения естественным образом распространяются на случай многоместных предикатов.
Пусть предикат P(z) задан на множестве А . Тогда Р(с) называется тожДественно истинным, если его область истинности совпадает с областью определения А , т.е. Р(а) — И при любом значении а ? А 
Предикат называется тожДественно ложным, если его область истинности пуста, т.е. Р(а) — Л для любого элемента
Кванторы. Всякому одноместному преДикату Р(с) на множестве А поставим в соответствие высказывание ЗсР(с) 
которое считается истинным тогда и только тогда, когда область истинности предиката Р(с) не пуста. Другими словами, высказыв ание 3zP(c) ложно тогДа и только тогДа, когДа Р (с) — тожДественно ложный преДикат на множестве А. Высказывание ЗсР(с) читается так: ”Существует с ? А такое, что Р(с) ”. Логический знак З называется квантором существования.
Из предиката Р(с) можно построить другое высказывание VcP(c) , читается: ” Для всех с справедливо Р (с) ” или, более кратко: ”Для всес с Р(с) 
Высказывание УТР (с) считается по опреДелению истинньии тогДа и только тогда, когДа Р(с) — тожДественно истинный преДитсат на множестве А 
Знак называется квантором общности. Пусть, например, предикат Р (с) z 2 — 22 + 4 0 определен на множестве целых чисел Z. Тогда высказывание ЗсР(с) — истинно, а VzP(z) — ложно. Приписывание к предикату одного из знаков З, 'p' называется операцией навешивания квантора или связывания квантором.
Применение этой операции тс оДноместному преДшсату по опреДелению превращает этот преДикат в высказывание.
Навешивание квантора на многоместный преДитсат понижает местность этого преДикатпа на еДиницу.
Например, если на множестве А задан двухместный предикат Р (с, у) , то предложение VcP(c, у) является одноместным предикатом от переменной у . Переменная с в этом предикате уже не играет роли переменной, поскольку истинность преДложения УТР(г, у) зависит только от значения у 
По этой причине переменную, которая связывается квантором, называют связанной, а переменную, не связанную квантором, — свобоДноб.
Кванторы и З широко используются в математике для сокращенной записи математических предложений.
Например, пусть f(c) — функция действительного переменного. Тогда истинность высказывания
означает, что Т — периоД ФУНКЦИИ f(c) .
Если высказывание
036 > 0 Ус 74 (с — zol 
— Щ < Е) истинно, то Ь является преДелом функции f(c) в точке с. 
Законы логики предикатов, Пусть Р(с) и Q(z) — предикаты, определенные на множестве А. Будем говорить, что предикат Р(с) равносилен предикату Q(c), и записывать Р(с) Q(c), если они принимают оДинатсовые значения истинности при любом значении переменного ? А.
Аналогично определяется отношение равносильности для многоместных предикатов. Очевидно, что преДикаты Р (с) -е Q(c) равносильны тогДа и только тогДа, тсогДа ис эквиваленчия Р(с) е» Q(c) является тожДественно истинным предикатом.
Равносильности предикатов играют такую же роль в логических рассуждениях, как и равносильности формул логики высказываний. Поэтому их также называют законами логи 
ки. Приведем наиболее употребительные из них.
1. VzVyP(c, у) Е VyVcP(c, у), 
ЗуЗсР(с, у) (перестановочность одноименных кванторов).
2. Ус (Р(с) Л Q(c)) Е Ус Р(г) Л Ус Q(c) (дистрибутивность квантора общности относительно конъюнкции) 
З. (Р(с) Q(z)) Зс Р (с) V3c Q(c) (дистрибутивность квантора существования относительно дизъюнкции) 
(закон отрицания квантора общности 
Ус —тР(с) (закон отрицания квантора существования 
Равносильности 4 и 5 по традиции называются законами де Моргана логики предикатов.
Доказательство каждой из вышеприведенных равносильностей легко следует из определений.
В качестве примера убедимся в справедливости закона отрицания квантора существования 5.
Пусть, например, высказывание -Бс Р(с) истинно. Тогда высказывание Вс Р(с) ложно. Это означает, что Р (с) — тожДественно ложный предикат, а значит, О (2) — тожДественно истинный предикат. Следовательно, высказывание Ус —Р(т) истинно.
Обратно, пусть 
— истинное высказывание. Проделав предыдущие рассуждения в обратном порядке, получим, что высказывание —Бс Р(с) также истинно.
Таким образом, -Бс Р (с) Е 
У п р а ж н е н и я:
1. Докажите справедливость утверждения: формулы Ф и 
логики высказываний равносильны тогда и только тогда, когда их конъюнкция Ф 4-+ является тавтологией.
2. Докажите равносильности I--XV, указанные на с. 21.
З. Докажите справедливость утверждений для любых формул логики высказываний:
(а) если Ф, , фа Н Ф, ТО 91, . . ,pnb— Ф;
(Ь) если Ф Ё- А, . . . 
то Ф Е Л • Лфп.
4. Ф Е- № тогда и только тогда, когда Ф и Ф.
5. Если и Ф не, то ФЕЭ.
6. Обосновать следующие правила вывода для любых формул А, В логики высказываний:
(Ь) А, В Е Ал В;
(с)
7. Найти области истинности предикатов, заданных на множестве А = {1, З, 4, 6, 7, 9, 12} • 
с — нечетное число“ 
(Ь) Q(c, у) . с — делитель у ;
(с) S(c, y,z) : ”разность (с — у) делится на 2” 
8. На множестве Х заданы предикаты Р(с) и Q(c) .
(а) Сформулировать определение каждой из операций
V, Л , над предикатами Р (с) и Q(c) 
(Ь) Пусть Л и Ј2 — области истинности, соответственно, предикатов Р(с) и Q(c) . Найти область истинности предикатов —Р(с), Р(с) VQ(c), 
Р(с) Q(c), Р(с) Q(c) .
9. Пусть А = {ат, ч, , ап} конечное множество и Р(с) — одноместный предикат, заданный на множестве А . Докажите:
(а) Р(с) Е- Р(щ) V Р(а2) . . . V Р (ч); ф) Ус Р(с) Р(а1) Л Л . . . Л Р(ап).
Докажите основные равносильности 1 — 4, приведенные на с. 33.
11. Пусть Р(с, у, 2) — предикат, определенный на множестве
(а) Какие из следующих предикатов являются одноместными предикатами и от какой переменной: 3cVy Р(с, у, 2), 3yVz3c Р(с, у, z), 3cVz Р(с, у, z), Vc3yVz Р(с, у, z), Vz Р(с, у, z), Ус Р(с, у, z) ?
(Ь) Какие из предложений, указанных в предыдущем пункте, являются высказываниями?
12. Докажите, что следующие высказывания являются истинными:
(а) 3cVy Р (г, у) Vy3c Р (с, у);
(Ь) Ус Р (с) М Ус Q(c) Ус (Р(г) V Q(c)) ;
13. Привести пример предиката Р (с, у) , для которого высказывания Vc3y Р(с, у) и 3yVc Р (с, у) не равносильны.
14. Построить отрицания к следующим предложениям:
(а) ЗТ )> ОУС ? R (f(z + Т) = f(c)) , где f(c) — функция действительного переменного;
(Ь) УЕ > 035 > ОУС со (с — гы lf(c) — < Е) ,
(с) Ус1,с2 R (21 f(C1) f(C2)) ;
Г л ав а П
Дата: 2019-02-02, просмотров: 210.
