9402

63.2. Высказывания. Алгебра высказываний. В математической логике основными неопределяемыми являются следующие понятия: высказывание, истина, ложь. Под высказыванием понимается любое повествовательное предложение, относительно которого можно сказать истинно оно или ложно. Например, высказывание «Студент, сдавший экзаменационную сессию на «отлично», получает повышенную стипендию» есть истинное высказывание; а высказывание «Число 6 делится на 4» есть ложное высказывание.

Пропозициональными переменными, обозначаемыми заглавными латинскими буквами А,В,С,… , будем называть переменные, значениями которых являются произвольные высказывания (истинные или ложные). К высказываниям можно применять те или иные операции. В результате появляются новые высказывания, истинностные значения которых зависят от истинностных значений высказываний, к которым операция применена. Приведем определения наиболее употребительных операций над высказываниями.

Отрицанием высказывания А называется высказывание, записываемое в виде A (читается: "не А "), которое истинно, если А ложно, и ложно, если А истинно. Это отражено в таблице истинности 1:

таб.1

Конъюнкцией двух высказываний А и В называется высказывание, обозначаемое A & B (читается: " А и В ''),которое истинно, если истинны оба высказывания A и В, и ложно в остальных случаях (см. таб. 2).

таб. 2

Дизъюнкцией двух высказываний А и В называется высказывание, обозначаемое A B (читается: " А или В ''), которое ложно, когда оба высказывания А и В ложны, и истинно, в остальных случаях (см. таб. 3):

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

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

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

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

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

принимают соответственно истинностные значения л, и, л. В этом случае

182

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

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

Тождественно истинные формулы фактически соответствуют

правильным схемам рассуждений. Например, рассуждать по схеме

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

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

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

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

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

определенная на множестве M такая, что

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

свойство натурального числа быть простым числом, то предикат P(x) = « x есть простое число»

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

P(x1 , x2 ,..., xn ) , переменные которой принимают значения на элементах множества M и такая, что

P(ai1, ai2 ,...,ain ) = 1, если набор (ai1 , ai 2 ,..., ain ) обладает свойством P;

184

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, ai2 ,...,ain ) можно

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

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

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

185

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)будет ложным.

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

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

( 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) = «десятичная запись целого числа окачивается двумя нулями»,

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

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

высказывание ( x)(Q(x) & P(x)) .

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

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

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

186

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

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

R(x) = (y)P(x, y) будет истинен при x ³ 5, а при x < 5 он будет ложным.

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

P(x) =« x – простое число » и =« x меньше чем y ». Тогда формула ( x)(P(x) & Q(x, y)) будет соответствовать одноместному

предикату с переменной y, который истинен для всех натуральных чисел, кроме 1 и 2 . А формула

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

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

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

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

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 является простым, т.е. эта формула выделяет среди натуральных чисел простые числа.

187

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

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

свойство симметрии: S = (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,а снабжено стрелкой, означающей направленность перехода между вершинами. Такого типа соединения

отсутствуют. Это означает, что переходы между вершинами возможны в

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

189

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

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

Рис. 64.2

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

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

задался вопросом: не льзя ли, начав прогулку с какого-то места, обойти все мосты ровно по одному разу и вернуться в исходно е место? Данным вопросом заинтересовался гениальный математик Леонард Эйлер (швейцарец по происхождению, большую часть жизни проработавший в

виде графа, изображенного на рис. 64.3,б. (Обратим вним ание на тот факт,

190