Лекции по дискретной математикеl

Лекции по дискретной математике.

1Формальный математический язык и элементы теории множеств. Функции и их свойства.

1.1Логические символы и формальный математический язык

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

связки

_ (дизъюнкция; содержательно, "или"),

^ (конъюнкция; содержательно, "и"),

: (отрицание; содержательно, "не"),

! (импликация; содержательно, "если ... то"),

$(равносильность; содержательно, "равносильно")

èкванторы

8 (квантор произвольности; содержательно, "для любого"),

9(квантор существования; содержательно, "существует").

Êлогическим символам обычно относят еще символ равенства "=".

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

8x9y (y > x)

è

(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1))

1

являются правильно построенными формулами. Первую можно прочитать так:

для любого x существует y, который больше, чем x

,

а вторую так:

z не равно единице, и для любых x и y, если z равно произведению x и y, то x равно z или x равно единице.

Напротив, последовательности символов

9x ^ x > y_

è

x + 8y = 0

не являются правильно построенными формулами.

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

8x9y (y > x)

все входящие в нее переменные x и y связанные, а в формуле

(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1))

переменные x и y связанные, а z свободная. Если некоторая переменная x является свободной переменной какой-нибудь формулы ', то, чтобы подчеркнуть это, часто пишут '(x). Формула, все переменные которой связанные, называется (замкнутым) предложением.

Формулы являются чисто синтаксическим (языковым) объектом. Чтобы придать формуле смысл, надо условиться, какое множество пробегают входящие в нее переменные и какие именно константы, функции и отношения обозначены входящими в нее символами. Если это уже проделано, то каждое предложение становится либо истинным, либо ложным. Так, если считать, что переменные x и y пробегают множе-

ство натуральных чисел, а символом ">" обозначено выражает обычное отношение "больше", то предложение

8x9y (y > x);

несомненно, истинно. Если же считать, что переменные x и y пробегают, например, только первый миллион натуральных чисел, то предложение становится ложным.

1На самом деле понятие свободной и связанной переменной определяется более сложным образом, см. например, [2], но мы не будем использовать формул, для которых данное нами определение будет вступать в противоречие с "правильным".

2

Если в формуле присутствуют свободные переменные, то истинными или ложными они могут становиться только после подстановки вместо свободных переменных каких-нибудь конкретных значений из рассматриваемой области. Например, если опять считать, что переменные x, y и z пробегают множество натуральных чисел, а

символ " " обозначает обычную операцию "умножение", то формула

(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1))

превращается в истинное утверждение только при подстановке вместо переменной z такого натурального числа, которое не равно единице и не имеет делителей,

отличных от единицы и самого себя (т.е. является простым числом 2, 3, 5, 7, 11

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

Между формулами существует отношения логического следования и логической эквивалентности . Если две формулы ' и логически эквивалентны, то они одно-

временно истинны или ложны. Некоторые эквивалентности полезно запомнить. Пусть ' и произвольные формулы. Тогда:

::' эквивалентно ';

' ! эквивалентно :' _ ;

:(' ! ) эквивалентно ' ^ : ;

:' ! : эквивалентно ! ';

:(' _ ) эквивалентно :' ^ : ;

:(' ^ ) эквивалентно :' _ : ;

:8x'(x) эквивалентно 9x:'(x);

:9x'(x) эквивалентно 8x:'(x):

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

(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1));

т.е. формула

:[(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1))];

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

:[(:z = 1) ^ 8x8y (z = x y ! (x = z _ x = 1))] эквивалентно

(z = 1) _ :[8x8y(z = x y ! (x = z _ x = 1))] эквивалентно

(z = 1) _ 9x9y:[(z = x y ! (x = z _ x = 1))] эквивалентно

3

(z = 1) _ 9x9y(z = x y ^ :x = z ^ :x = 1):

Вместо :x = z часто пишут x 6= z; поэтому последнюю формулу можно переписать

òàê:

(z = 1) _ 9x9y(z = x y ^ x 6= z ^ x 6= 1):

Последняя формула имеет прозрачный смысл: z равно единице или может быть

представлено в виде произведения двух сомножителей, первый из которых отличен от самого z и от единицы.

Систематическое изложение содержания данного пункта является одним из предметов изучения математической логики . Его можно найти, например, в книге [2].

1.2Элементы теории множеств

1.2.1Основные обозначения и идеи аксиоматического подхода

Понятия "множество" и "принадлежности элемента множеству " являются наиболее

фундаментальными математическими понятиями. Содержательно множество означа- ет любую совокупность некоторых элементов (которые, вообще говоря, тоже являются множествами), а принадлежность элемента x множеству y означает, что элемент x

входит в совокупность y. Для обозначения отношения принадлежности используется символ "2":

x 2 y читается "x принадлежит y":

Âтеории множеств используются также следующие обозначения:

;пустое множество, т.е. множество, не содержащее ни одного элемента;

x y множество x есть подмножество множества y. Это обозначение есть сокращенная запись формулы 8z(z 2 x ! z 2 y) (каждый элемент множества x есть и элемент множества y);

fx: '(x)g множество всех элементов, удовлетворяющих свойству '(x) (здесь под "свойством" подразумевается формула со свободной переменной x);

fx 2 y : '(x)g множество всех элементов множества y, удовлетворяющих свойству '(x). Это сокращение для записи fx: (x 2 y) ^ '(x)g.

Кроме того вместо выражений :x 2 y, :x y часто пишут соответственно x 2= y, x * y, а для обозначения того факта, что множество x есть собственное подмножество множества y (т.е. (x y) ^ (x 6= y)) используют обозначение x y или x ( y.

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

Например, для любой формулы '(x) вместо 8x(x 2 y ! '(x)) записыва-

C точки зрения классической логики оказываются верными следующие предложения, содержащие символ " ":

4

8x(; x),

8x(x x),

8x8y8z((x y ^ y z) ! x z)).

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

любое множество однозначно определяется своими элементами .

Формально это выражается так:

8x8y ((8z(z 2 x $ z 2 y)) ! x = y)

(если у множеств x и y одни и те же элементы, то они равны) или, с использованием введенных обозначений

8x8y ((x y ^ y x) ! x = y):

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

совокупность всех элементов x, удовлетворяющих некоторому характеристическому свойству '(x), является множеством . Более строго, принцип свободы означает, что для каждой правильно построенной формулы '(x) со свободной переменной x существует множество fx: '(x)g. Без использования специальных обозначений это

Заметим, что принцип свободы это не аксиома, а бесконечный список аксиом (каждая для своей формулы '(x)). При этом предполагается, что формула '(x) может

иметь еще и другие свободные переменные x1, x2, ... xn (ни одна из которых не сов-

5

утверждает, что для каждого множества x1 существует множество y, содержащее множество x1 в качестве единственного элемента.

Поскольку из аксиомы объемности следует, что для каждой n-ки множеств x1, x2,

... xn множество fx: '(x; x1; x2; : : : ; xn)g (если оно существует) единственно, аксиома ( ) фактически определяет некоторую операцию на множествах, которая каждой n-ке множеств x1, x2, ... xn ставит в соответствие множество fx: '(x; x1; x2; : : : ; xn)g.

Приведем в качестве примера еще некоторые частные случаи "принципа свободы".

Существует множество fx: x 6= xg; формально,

9y8x(x 2 y $ x 6= x)

(существует множество y, состоящее из таких элементов, которые не равны самим

себе; таких элементов, конечно, не существует, поэтому это утверждение постулирует существование множества без элементов, т.е. пустого множества ;).

Существует множество fx: x 2 y _ x 2 zg, формально,

9u8x(x 2 u $ (x 2 y _ x 2 z))

(Для любых множеств y и z существует множество u, которое содержит в точности те элементы, которые принадлежат хотя бы одному из множеств y и z, иначе говоря, существует объединение множеств y и z),

è ò.ï.

Эти три (и многие другие) частные случаи, конечно, нельзя не признать справедливыми. Однако, как оказалось, в полном объеме принцип свободы ведет к противоречию. Это вытекает, например, из следующего парадокса Рассела. Рассмотрим

множество всех множеств, которые не являются своим собственным элементом , т.е. fx: x 2= xg. Обозначим его символом Rs. Если верить принципу свободы, такое

множество существует. Зададимся вопросом, принадлежит ли множество Rs самому себе или нет. Допустим, Rs 2 Rs. Тогда для него должно выполняться то характеристическое свойство '(x) = x 2= x, с помощью которого образовано множество Rs, следовательно, Rs 2= Rs. Пусть, напротив, Rs 2= Rs. Тогда для множества Rs характеристическое свойство '(x) выполнено и, следовательно, оно должно оказаться среди элементов множества Rs, т.е. Rs 2 Rs.

жества y можно выделить подмножество всех элементов, которые

2На самом деле это тоже не аксиома, а бесконечный список аксиом по всем формулам '(x).

6

удовлетворяют свойству '(x). Например, если уже определено множество натуральных чисел N (и операция умножения на нем), то корректно говорить и о множестве простых чисел fz 2 N: (z 6= 1) ^ 8x8y (z = x y ! (x = z _ x = 1))g.

Более подробно см. [3]. Обсуждение аксиом теории множеств и увлекательную историю становления аксиоматического подхода можно найти в [4].

1.2.2Операции над множествами

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

Во-первых, согласно аксиоме (неупорядоченной) пары для любых двух различных множеств x и y существует множество fx; yg, содержащее в качестве элементов в

точности множество x и множество y. Эта аксиома может быть распространена

на любой конечный набор множеств, т.е. для любого конечного набора x1, x2, ..., xn попарно различных множеств существует множество fx1; x2; : : : ; xng элементы которого суть в точности x1, x2, ..., xn. В частности для любого множества x существует множество fxg, содержащее x в качестве единственного элемента.

Аксиома объединения постулирует для любого множества x существование мно-

x = fz : 9y(y 2 x ^ z 2 x)g

всех элементов, которые принадлежат хотя бы одному элементу этого множества. Комбинируя эту аксиому с аксиомой пары легко получить утверждение о существовании объединения x [ y любых двух множеств x и y:

x [ y = fz : z 2 x _ z 2 yg:

Вместе с операцией объединения обычно рассматривают еще следующие элементарные операции:

x \ y = fz : z 2 x ^ z 2 yg пересечение ;

x n y = fz : z 2 x ^ z 2= yg относительное дополнение (или разность) и

x M y = (x n y) [ (y n x) симметрическая разность ;

корректность которых легко следует из предыдущих аксиом.

Часто используют также понятие "(абсолютное ) дополнение ". Для этого вначале надо задаться некоторым универсальным (непустым) множеством и условиться рассматривать только подмножества этого множества. В этом случае дополнение x множества x есть n x или, что то же самое, fz 2 : z 2= xg.

7

A\B = f1; 2g, AnB = f0g, B nA = f3; 4g, A M B = f0; 3; 4g, (AnB)n(A M B) = ; è ò.ï.

Для операций над множествами справдливы следующие тождества. Для всех подмножеств x; y; z некоторго универсального множества

1.(x [ y) [ z = x [ (y [ z), (x \ y) \ z = x \ (y \ z) (ассоциативность объединения и пересечения),

2.x [ y = y [ x, x \ y = y \ x (коммутативность объединения и пересечения),

3.x [ (y \ z) = (x [ y) \ (x [ z), x \ (y [ z) = (x \ y) [ (x \ z) (дистрибутивность

объединения относительно пересечения и пересечения относительно объединения),

4.x [ (x \ y) = x \ (x [ y) = x (законы поглощния),

5.x [ x = , x \ x = ; (законы дополнительности ),

6.x = x, x [ y = x \ y, x \ y = x [ y (законы двойственности ),

6. [ x = , \ x = x, ; [ x = x, ; \ x = ;; 3

кроме того, справедлива следующая цепочка равносильностей

x y $ y x $ x [ y = y $ x \ y = x $ x [ y = $ x \ y = ;:

Приведенные выше тождества и равносильности легко доказываются с помощью определений и аксиомы объемности.

Пример. Докажем, например, тождество x [ y = x \ y. Для этого, во-первых, докажем включение x [ y x \ y. Пусть z произвольный элемент множества x [ y. Тогда z 2= x[y. Если предположить, что z 2 x, то z 2 x[y. Поэтому z 2= x. Аналогично получим z 2= y. Тогда z 2 x и z 2 y. Следовательно, z 2 x \y. Включение x [ y x \y доказано.

3Можно доказать, что все верные теоретико-множественные тождества, которые записываются

ñпомощью символов объединения, пересечения и дополнения, можно вывести из этих тождеств,

причем на самом деле достаточно тождеств 1-5.

8

Пусть теперь z произвольный элемент множества x \ y. Тогда z 2 x и z 2 y, т.е. z 2= x и z 2= y. Если z 2 x [ y, то z 2 x или z 2 y, поэтому z 2= x [ y и, следовательно, z 2 x [ y. Доказано включение x \ y x [ y.

Теперь доказывемое тождество следует из аксиомы объемности.

Рассмотрим другие операции над множествами. Используя уже определенные операции для каждого множества x можно определить множество Sc(x) = x[fxg. Любое

множество y называется индуктивным, если оно содержит в качестве элемента пустое множество ;, и вместе с каждым своим элементом z содержит элемент Sc(z). Аксиома

бесконечности утверждает, что существует хотя бы одно индуктивное множество. С помощью этой аксиомы можно построить множество, обозначаемое символом ! (или

N), состоящее в точности из всех тех множеств, которые принадлежат каждому индуктивному множеству. Таким образом, элементы ! это множества

;; f;g; f;; f;gg; f;; f;g; f;; f;ggg è ò.ä.

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

0 = ;; 1 = 0 [ f0g = f;g; 2 = 1 [ f1g = f;; f;gg; 3 = 2 [ f2g = f;; f;g; f;; f;ggg è ò.ä.

Все операции над определенными таким образом натуральными числами (сложение, умножение и т.д.) могут быть определены через теоретико-множественные операции4, а аксиомы, которые принимают для натуральных чисел (например, схема индукции ), могут быть выведены из аксиом теории множеств. Кроме того, все расширения множества натуральных чисел (множества целых Z, рациональных

Q, действительных R и т.п. чисел) также вводятся с помощью теоретикомножественных конструкций, примененных к множеству N.

Аксиома степени постулирует существование множества P(x) всех подмножеств произвольного множества x, называемого иногда множеством-степенью или булеаном множества x:

P(x) = fy : y xg:

Например, P(;) = f;g, P(P(;)) = P(f;g) = f;; f;gg. Можно доказать, что если множество x конечно и содержит n элементов, то множество P(x) содержит 2n элементов.

Другой важной операцией над множествами является декартово (или прямое) произведение множеств. Для того, чтобы определить эту операцию, надо сначала ввести понятие упорядоченной пары. Содержательно, упорядоченная пара (u; v) мно-

жеств u и v это такая их совокупность, в которой за множествами u и v "закреплено соответствующее место ": множество u "первое", а множество v "второе". При

этом единственным свойством пары является способность полностью определяться своим первым и вторым членами:

(x; y) = (x0; y0) $ x = y ^ x0 = y0:

4например, отношение "меньше" это просто принадлежность: x < y $ x 2 y

9

Один из способов определить упорядоченную пару состоит в том, чтобы положить

(u; v) = fu; fu; vgg.

Если понятие упорядоченной пары уже определено, то декартовым произведением x y множеств x и y называется множество всех пар (u; v), первый элемент которых

берется из множества x, а второй из множества y:

x y = fz : 9u9v(z = (u; v) ^ u 2 x ^ v 2 y)g:

Например, f0; 1; 2g f0; 1g = f(0; 0); (0; 1); (1; 0); (1; 1); (2; 0); (2; 1)g, а декартово произведение отрезка [0; 1] действительных чисел на себя есть "единичный квадрат" f(u; v): u; v 2 R ^ 0 u; v 1g. Можно показать, что если конечные множества x и y содержат n и m элементов соответственно, то множество x y содержит nm элементов. В частности, x ; = ; y = ; для любого множества x.

Множества x (y z) и (x y) z, строго говоря, не равны между собой, но их обычно отождествляют и записывают просто x y z. Аналогично для любого числа "сомножителей".

Декартово произведение x x : : : x называют декартовой n-ой степенью мно-

| {z }

n ðàç

жества x и обозначают символом xn. Элементы этого множества называют последовательностями (или кортежами ) длины n из элементов множества x. Множество всех кортежей элементов множества x любой конечной длины часто обозначают символом

x<!:

[

x<! = xn:

n2!

Теория множеств содержит еще несколько аксиом, которые мы не будем обсуждать.

1.3Функции и их свойства

В классической математике функции отождествляются с из "графиками". Точнее, функция f из множества X в множество Y (обозначение f : X ! Y ) это любое подмножество множества X Y , которое удовлетворяет следующим условиям:

1.(8x 2 X)(9y 2 Y )(x; y) 2 f (у каждого элемента x из множества X есть хотя бы один "образ"),

2. (8x 2 X)(8y1; y2 2 Y )(x; y1) 2 f ^ (x; y2) 2 f ! y1 = y2 (у каждого элемента x из множества X единственный не более одного "образа").

Запись f(x) = y при этом считается просто другой формой записи (x; y) 2 f.

Пример. Если изображать подмножества f множества x y посредством множества стрелок, соединяющих первый элемент пары (x; y) 2 f со вторым, то на первых четырех картинках изображены функции, а на оставшихся двух не функции:

10