10303

Импликацией двух высказываний А и В называется высказывание, обозначаемое A → B (читается: "из A следует В" или "если A , то В''),которое будет ложным, если А истинно, а В ложно, и исти нным в остальных случаях (см. табл. 4):

Большинство тео рем в математике может быть представлено в виде импликации A → B , где высказывание А является услов ием теоремы (что дано), а высказывание В является заключением теоремы (оно вытекает из условий, содержащихся в высказывании А). При этом вы сказывание В на-

зывается необходимы м условием высказывания А, а в ысказывание А называется достаточным условием для существования факта, о котором говорится в высказы вании В.

Например, утверждение: «Если сумма цифр в десятичной записи целого положительного числа делится на 9, то и само число делится на 9» можно записать в виде импликации A → B , где А есть высказывание: «сумма цифр в десятичной записи целого положительного числа делится

Истинностные з начения этой формулы в зависимости от истинностных значений входящ их в нее пропозициональных переменных А, В,C приведены в следующ ей таблице:

Например, формула A A является тождественно истинной, а ее отри-

цание A& A является тождественно ложной. Очевидно, что, если формула

правильно (или дождь сегодня будет, или дождя сегодня не будет). А рассуждать по схеме

(A→ B)→(B → A) («если из A следует В, то из В следует A»)

в общем случае неправильно. Например, из того, что, если запись целого числа окачивается двумя нулями, то число делится на 4, не следует, что, если число делится на 4, то его запись окачивается двумя нулями.

63.3 Понятие предиката. Язык логики высказываний не вполне подходит для выражения понятий и логических рассуждений, используемых в пределах математики и, тем более, в обиходе. Более выразительным является язык логики предикатов. Предикаты определяют свойства, которыми могут обладать (или не обладать) элементы некоторого множества или наборы элементов некоторого множества. И потому, оперируя в языке предикатами, можно выяснять взаимозависимость различных свойств элементов или наборов элементов некоторого множества.

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

P(a) =1, если a обладает свойством P; P(a) =0, если a не обладает свойством P.

При этом, если для элемента a M имеет местоP(a) =1 то говорят, что предикатP(x) истинен на этом элементе, если же P(a) =0, то говорят, что предикатP(x) ложен на этом элементе.

Например, если N есть множество натуральных чисел, а P есть свойство натурального числа быть простым числом, то предикат

P(x) = « x есть простое число»

будет истинным на простых числах и ложным на составных числах. Аналогично, если P есть некоторое свойство, которым могут обладать наборы(ai1 , ai 2 ,..., ain ) элементов множества M, то n-местным предикатом,

соответствующим этому свойству, называется функция P(x1, x2 ,..., xn ) ,

переменные которой принимают значения на элементах множества M и такая, что

184

P(ai1, ai2 ,...,ain ) = 1, если набор(ai1 , ai 2 ,..., ain ) обладает свойством P; P(ai1, ai2 ,...,ain ) = 0, если набор(ai1 , ai 2 ,..., ain ) не обладает свойством P При этом, если P(ai1, ai2 ,...,ain ) =1 ( P(ai1,ai2 ,...,ain ) = 0), то говорят, что на наборе (ai1 , ai 2 ,..., ain ) предикатP(x1 , x2 ,..., xn ) истинен (ложен).

Пусть, например, R есть множество действительных чисел и пусть на некоторой плоскости введена декартова система координат. Тогда двуместный предикат P(x, y) =" x + y = 1" соответствует свойству точки с координатами (х,у) лежать на прямой x + y = 1. На этих точках данный предикат будет истинным, а на остальных точках плоскости он будет ложным.

Точно так же двуместный предикат O(x, y) =" x2 + y2 = 1" истинен на точках плоскости, которые лежат на окружности радиуса 1 с центром в начале координат.

Предикат P(x1 , x2 ,..., xn )

1)тождественно истинным на множестве М, если он истинен на любом наборе значений его аргументов;

2)выполнимым на множестве М, если он истинен на некотором наборе значений его аргументов;

3)тождественно ложным на множестве М, если на всех наборах его аргументов он ложный.

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

Так, например, предикат P(x) =« x -простое число» является тожде-

ственно истинным на множестве М={2,5,7,11}, выполнимым на множе-

стве всех целых чисел и тождественно ложным на множестве всех целых четных чисел, больших чем 2.

Пусть P(x1 , x2 ,..., xn ) есть n-местный предикат на множестве М. Тогда с точки зрения алгебры высказываний выражение P(ai1, ai 2 ,...,ain ) можно рас-

сматривать как некоторое высказывание, которое истинно, если P(ai1, ai2 ,...,ain ) =1и ложно, если P(ai1, ai2 ,...,ain ) = 0. Таким образом, выражение P(x1 , x2 ,..., xn ) можно рассматривать как переменное высказы-

вание, истинность которого зависит от конкретного набора значений переменных (x1 , x2 ,..., xn ) . В связи с этим, к предикатам можно применять

те же операции, что и к высказываниям.

Например, предикат R(x) =« x >1» на множестве натуральных чисел истинен для всех чисел, больших 1. Предикат R(x) = "x > 1" является отрицанием предиката R(x) и он будет истинен только для x =1.

Пусть двуместные предикаты

185

Q(x, y) ="x ≤ y" и R(x, y) =" x + y > 5"

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

S(x, y) = Q(x, y) & R(x, y)

является их конъюнкцией, а двуместный предикат

T (x, y) = Q(x, y) R(x, y)

является их дизъюнкцией. Высказывания S (3,5) и T (8,3) будут истинными, а высказывание R(8,3) будет ложным.

Наряду с операциями алгебры высказываний, в логике предикатов существует еще две операции: навешивание квантора существования (обозначается( ) ) и навешивание квантора общности (обозначается( )).

Поясним применение и результаты применения этих операций.

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

В результате навешивания квантора общности по переменной x полу-

чается высказывание

( x)P(x) (читается: для всех x P(x) ),

истинное, когда предикат P(x) истинен на всех элементах множества М, и ложное в противном случае. Часто в формулах для обозначении квантора общности символ опускается и вместо( x) пишут просто (x) .

В результате навешивания квантора существования по перемен-

ной x получается высказывание

( x)P(x) (читается: существует x ,такой что P(x) ),

истинное тогда, когда существует элемент в М, на котором предикатP(x) истинен, и ложное в противном случае). Нетрудно понять, что для кванторов общности и существования справедливы соотношения

( x)P(x) ≡ ( x)P(x) ; ( x)P(x) ≡ ( x)P(x)

Рассмотрим несколько примеров. Если на множестве натуральных чисел N рассмотреть два предиката

P(x) = «сумма цифр в десятичной записи числа x делится на 9», Q(x)= «число x делится на 9»,

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

(x)(P(x) → Q(x)) и (x)(Q(x) → P(x))

являются истинными.

Если же на множестве натуральных чисел N рассмотреть предикаты

P(x) = «десятичная запись целого числа окачивается двумя нулями»,

186

Q(x)= «число делится на 4»,

то высказывание (x)(P(x) → Q(x)) является истинным, а высказывание (x)(Q(x) → P(x))является ложным, в силу того, что истинным является высказывание ( x)(Q(x) & P(x)) .

Допустим, что P(x, y,z) есть 3-местный предикат на множестве М. То-

гда в результате навешивания квантора общности по переменной y

получается двуместный предикат

P(x, z) = (y)P(x, y, z) (читается: для всех y P(x, y, z)),

1

который на паре элементов (ai ,a j ) из множества М будет истинным только в том случае, когда предикат P(x, y, z) истинен на всех наборах вида (ai , y, aj ) , где y любой элемент из множества М.

При навешивании квантора существования по переменной y по-

лучается двуместный предикат

P (x, z) = ( y)P(x, y,z) (читается: существует y такой что P(x, y, z)),

2

который на паре элементов (ai , a j ) из множества М будет истинным тогда,

когда для некоторого элемента b из множества М предикат P(x, y, z)исти-

нен на наборе (ai , b, a j )

Пусть, для примера, предикат P(x, y) ="x + y >5" определен на множестве положительных чисел. Тогда одноместный предикат R(x) = (y)P(x, y) будет истинен при x ³5, а при x <5 он будет ложным.

Рассмотрим на множестве натуральных чисел предикаты:

P(x) =« x – простое число » и Q(x, y) =« x меньше чем y ».

Тогда формула ( x)(P(x) & Q(x, y)) будет соответствовать одноместному предикату с переменной y, который истинен для всех натуральных чисел, кроме 1 и 2 . А формула

( y)( x)(P(x) & Q( y, x))

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

63.4. Определение математических понятий посредством формул логики предикатов. Как уже говорилось, язык логики предикатов является более выразительным по сравнению с алгеброй высказываний. Многие

187

математические объекты и свойства этих объектов могут быть записаны в виде формул логики предикатов.

Рассмотрим на множестве натуральных чисел предикат:

P(x, y, z) =" xy = z".

Тогда формула

E(x) = ( y)P(x, y, y)

на множестве натуральных чисел будет истинна только, если x = 1. Или можно сказать, что эта формула определяет единицу. Если к тому же рассмотреть предикатR(x, y) =" x = y"то формула

(x)( y)(P(x, y, z) → (E(x) & R( y, z) E( y) & R(x, z))

будет истинной только в том случае, когда число z является простым, т.е. эта формула выделяет среди натуральных чисел простые числа.

Ранее, в лекции по теории множеств, нами было введено понятие бинарного отношения В на некотором множестве M. Очевидно, задание бинарного отношения на множестве равносильно заданию некоторого двуместного предиката P на этом множестве. И тогда свойства бинарного отношения могут быть записаны формулами логики предикатов. Вот некоторые из них:

свойство рефлексивности: R= (x)(P(x, x)) ;

(x)( y)(P(x, y) → P( y, x)) ;

свойство транзитивности: T= (x)( y)(z)(P(x, y)&P( y, x) → P(x, z)) .

Как указывалось в лекции по теории множеств, бинарное отношение называется отношением эквивалентности, если оно обладает свойствами

рефлексивности, симметрии и транзитивности. А это означает, что со-

ответствующий этому отношению двуместный предикат P обращает в истину конъюнкцию указанных трех формул:

Q = R & S & T .

188

Л екция 64. Элементы теории графов

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

64.1.Определени е и основные типы графов. Что же такое граф? Можно сказать, что г раф – это есть совокупность точек на плоскости,

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

Рис. 64.1

На рис. 64.1 приведены примеры двух основных типов графов. Каждое соединение на рис. 64.1,а снабжено стрелкой, означа ющей направленность перехода межд у вершинами. Такого типа соедин ения называются дугами, а графы такого типа называются ориентированными. На рис. 64.1,б стрелки на соединениях графа отсутствуют. Это означает, что переходы между вершинами возможны в обоих направле ниях. Такого типа соединения называются ребрами, а графы с такими соединениями назы-

ваются неориентиро ванными.

Графы на рис. 6 4.2,а и рис. 64.2,б являются графам и с петлями, т.к. там присутствуют ребра и дуги, соединяющие некоторые вершины с самими собой. Графы на рис. 64.2,в и рис. 64.2,г называются взвешенными. Каждое ребро (дуга) в этих графах сопровождается некоторым числом. Эти числа могут озна чать или пропускную способность ребра (дуги), или расстояния между вер шинами, или стоимость перехода между вершинами.

189

Ориентированные графы служат хорошими моделям и при проектировании газотранспортн ых или электрических сетей или технологий строительства крупных объектов.

Рис. 64.2

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

На рис. 64.3,а изображены семь мостов, которые связывали два берега реки и два острова в городе Кенигсберге (современный Калининград). Немецкий философ Иммануил Кант, гуляя по городу, задался вопросом: нельзя ли, начав прогулку с какого-то места, обойти все мосты ровно по одному разу и вернуться в исходное место? Данным вопросом заинтересовался гениальный математик Леонард Эйлер (швейцарец по происхождению, большую часть жизни проработавший в России), и его исследования в поисках ответа оказались отправными в становлении теории графов как самостоятельной математической дисциплины. Приняв берега и острова за вершины, а мосты, их соединяющие, за ребра, Эйлер представил данный городской ландшафт в виде графа, изображенного на рис. 64.3,б. (Обратим внимание на то т факт, что в графе на рис. 64.3,б вершины v4иv1, а

190

также v4 иv2 соединены не одним, а двумя ребрами. Г рафы, в которых имеются вершины, соединенные между собой несколькими ребрами, называются мультиграфами.). И теперь вопрос Канта стал звучать так: можно ли из произвольной вершины графа обойти все ребра ровно по одному разу и вернуться в исходную вершину? Ответ, который получил Эйлер, будет сформулирован ниже.

Рис. 64.3

Алгебраически п роизвольный граф можно представить в виде совокупности G двух множеств V и E(записывается G={V, E}), где

V ={v1,v2,...,vn} есть множество вершин графа, а E есть множество дуг или

множество ребер в зависимости от того ориентированный, граф или неориентированный. В первом случае каждая дуга из множества E задается в виде упорядоченной пары (vi ,vj ), где vi есть нача льная вершина ду-

ги, а v j есть ее конечн ая вершина. Во втором случае каждое ребро из мно-

жества E задается в виде пары (vi ,vj ), в которой (i ≤ j). Для ориенти-

рованных (нериенти рованных) мультиграфов каждая дуга (ребро) из

Для взвешенных графов каждая дуга (ребро) из множества E зада-

ется в виде тройки (vi , v j , r ) ( (vi , v j , r) , (i ≤ j ), где число r означает пропускную способность дуги (ребра). Например, ребро, соединяющее вершиныv1 иv2 . в гра фе на рис. 62.2,г будет описано так: (v1 ,v2 ,48).

191