Файл: Diskretnaya_matematika.doc

2. Отношение Rна множествеXназываетсясимметричным, если из усло­вия (х, у)Rследует (у, х)R. ОтношениеRна множествеXназываетсянесимметричным, если для любых х, уXиз условия (х,y)Rследует (у, х)R.

3. Отношение Rна множествеXназываетсятранзитивным, если для лю­бых х, у,zRиз одновременного выполнения условий (x,y)Rи (у,z)Rследует (х,z)R.

Пример. Рассмотрим следующие отношения на множестве X = {1,2,3,4,5,6,7}:

G = {(x, y) | х, у  Х; х > у};

L = {(х, у) | х, у  Х; х  у};

M = {(x, y) | х, у  X; (х - у) делится на 3};

К = {(х, y) | х, у  Х; х² + у²  20}.

Исследуем, какими свойствами они обладают.

Среди приведенных в примере отношений рефлексивными являются отношениеL(т. к. хх справедливо при всех хX) и отношение М (т. к. х - х = 0 делится на 3, поэтому пара (х, х) принадлежит отношению М при всех х X).

Симметричными являются отношения М (если х - у делится на 3, то и у - х делится на 3) и К (если х² + у²  20, то и у² + х²  20).

Транзитивными являются отношения G, L, М.

1.5.4. Отношения эквивалентности

Бинарные отношения делятся на типы в зависимости от свойств, которыми они обладают.

Отношение Rна множествеXназываетсяотношением эквивалентности, если оно обладает свойствами рефлексивности, симметрич­ности и транзитивности.

Важной особенностью отношений эквивалентности является то, то они разбивают все множество Х на не­пересе­кающиеся подмножества – классы эквива­лент­ности.

Классом эквивалентности, порожденным элементом хX, называется подмножество [х] множестваX, для элементов которого выполняется условие (х, у)R,yX.

Таким образом, класс эквивалентно­сти:

[х] = {у | y  X; (x, y)  R}.

Классы эквивалентности образуют систему непустых непересекающихся подмножеств множества X, в объединении дающую все множество X – т. е. образуют разбиение множества Р(Х).

Обозначим отношение эквивалентности символом , тогда класс эквивалентности записывается в виде:

[х] = {у | y  X; х  у}.

Из рассмотренных в примере отношений только отно­ше­ние М является отношением эквивалент­ности.

Отношение М разбивает множество X = {1,2,3,4,5,6,7} на три клас­са эквивалентности:

[1] = {1,4,7}, [2] = {2,5}, [3] = {3,6}. Классы, порожденные элементами 4, 5, 6 и 7 совпадают с этими классами:

[4] = [1], [5] = [2], [6] = [3], [7] = [1]. 1.6. Отображения множеств

Пусть XиY– два непустых множества. ЗаконG, согласно ко­торому любому элементу хXставится в соответствие элемент уY, называетсяоднозначным отображением XвY. Отображение является обобщением понятия функци­и, определенной наXи принимающей значения наY.

Используются следующие эквивалентные записи:

G:XY

или

у = G(x); где х  X , у  Y.

В случае однозначного отображения элемент у называ­ется образом элемента х, а х – прообразом у.

Возможна ситуация, когда каждому х  X отображение G ста­вит в соответствие некоторое подмножество G(x)  Y. Тогда обра­зом элемента х будет подмножество G(x). Отображение G в этом случае будет являться многозначным отображением.

Отображение является, таким образом, всюду определенным отношением и определяется тройкой множеств (X,Y,G).

Интересным является случай, когда множества XиYсовпада­ют:X=Y. ОтображениеG:XXпредставляет собой отображе­ние множестваXсамого в себя и определяется парой множеств (X,G), гдеGXX. Подробным изучением таких отображений занимается теория графов. Рассмотрим здесь лишь нескольких операций над ними.

Пусть G и Н – отображения множества X в X. Композицией этих отображений назовем отображение GH, которое определяется следующим образом:

GH(x) =G(H(x)).

В частном случае при Н = Gполучим отображения:

G²(x) =G(G(x)),G³(x) =G(G²(x)) и т. д.

Для произвольного S2 имеем:G^S(x) =G(G^{S -1}(x)).

Введем для общности соотношение: G⁰(x) = х. То­гда можно записать:

G⁰(x) =G(G^-1(x)) =GG^-1(x) = х.

Это означает, что G^-1(x) представляет собой обратное отобра­жение. ТогдаG^-2(x) =G^-1(G^-1(x)) и т. д.

Пример. Пусть X – множество людей. Для каждого человека х  X обозначим через G(x) множество его детей. Тогда:

G²(x) – множество внуков х,

G³(x) – множество правнуков х,

G^-1(х) – множе­ство родителей х и т. д.

Изображая людей точками и рисуя стрелки, идущие из х в G(x), получим родословное, или генеалогическое де­рево, представленное на рис. 1.10.

Рис. 1.10. Генеалогическое дерево

1.7. Контрольные вопросы и упражнения

1. Вставьте обозначения числовых множеств:

• множество натуральных чисел;

• множество целых чисел;

• множество рациональных чисел;

• множество действительных чисел.

2. Вставьте пропущенный знак  или : 117 ___ N; 22,4 ___ Z; 4/3___Q;

___ Q; ___R;  ___ Z.

3. Принадлежит ли множеству корней уравнения

x² - 5х + 6 = 0 число х = -3?

3. Какими способами можно задать множество?

4. Запишите множество действительных корней уравне­ния 3х + 4 = 0. Как записать ответ, если требуется найти множество целых корней этого уравнения?

5. Что такое подмножество данного множества? Какой символ используется для записи «множество А является подмножеством множества В»? Запишите его: А ____ В.

6. Вставьте пропущенный символ  или  :

1 ___ {1,2,3}; {1} ____ {1,2,3};

 ___ {1,2,3}; {2,3} ____ {1,2,3}.

3. Вставьте пропущенные знаки операций на множествах:

{а,b,с} ____ {d,b,e} = {b};

{a,b,с} ____ {с, d} = {а,b,с,d};

{а,b,с} ____ {a,d} = {b,c}.

3. Что такое булеан множества X?

4. Является ли булеаном множества {а,b,с} система под­множеств {а}, {b}, {с} ?

5. Является ли разбиением множества {а,b,с} система подмножеств {a,b},{b,с},{а,с} ?

6. Нарисуйте диаграммы Эйлера для левой и правой час­тей за­кона де Моргана. Сравните их.

7. Запишите законы алгебры множеств. Запомните их названия.

8. Вставьте пропущенный знак = или : {3,5} _____ {5,3}; (3,5) _____ (5,3).

9. Нарисуйте график декартова произведения X  Y, где X = {1,5}, Y = {2,3}. Совпадает ли он с графиком У  X?

10. Дайте определение бинарного отношения на множестве.

11. Обведите кружком номер правильного ответа. Обла­стью определения бинарного отношения R называется множество

а) {(х, у)| (х, у)  R};

б) {х| (х, у)  R};

в) {у| (х, у)  R}.

3. Какими способами можно задать бинарное отношение?

4. Какое отношение является рефлексивным?

5. Какой особенностью обладает матрица рефлек­сив­ного отношения? А матрица симметричного отноше­ния?

6. Закончите фразу: Отношение, облада­ю­щее свойствами рефлек­сивно­сти, симметрич­ности, тран­зи­тив­нос­ти, называется отношением

_________________________________________.

3. Запись [х] используется для обозначения __________________________________________.

2. Математическая логика

2.1.Алгебра логики

2.1.1. Логические высказывания

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

Примеры:

1. Волга впадает в Каспийское море.

2. Два больше трёх.

3. Я лгу.

Примеры 1, 2 являются высказываниями (1 – истинно, 2 –ложно). Пример 3 – не высказывание (если предположить, что оно истинно, то в силу его смысла оно одновременно ложно и, наоборот, из лож­ности этого предложения вытекает его истинность).

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

Высказывания будем обозначать буквами А, В, С, а их зна­чения («истина» или «ложь») – соответственно цифрами 1 или 0. Эти цифры будем рассматривать как символы, не имеющие арифметического смысла.

В обычной речи сложные предложения образуются из простых предложений с помощью связок: «и», «или», «если..., то…» и т. д.

Примеры:

1. Светит солнце, и идёт дождь.

2. Шесть делится на два или шесть делится на три.

3. Если контакт замкнут, то лампа горит.

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

2.1.2. Основные логические операции

1. Выражение А  В(«А и В») означает высказыва­ние, истинное только в том случае, когда А и В истинны.

Такое вы­сказывание называют конъюнкцией выска­зы­ва­нийА и В. Символобозначает операцию конъюнкции. Эта операция соответствует союзу«и»в обычной речи. В алгебре логики знак операции «» можно опускать или заменять на «•».

В обычной речи не принято соединять союзом «и» два высказывания, далекие по со­держанию. В алгебре высказываний операция конъюнкции мо­жет быть применена к любым двум высказываниям. Например, для высказываний: «пять больше трех» и «трава зеленая» их конъюнкция является истинным вы­сказыванием.

2. Выражение А  В(«А или В») означает высказы­вание, истинное, если хотя бы одно из высказываний А или В явля­ется истинным.

Такое высказывание называют дизъюнкцией вы­ска­зыва­нийА и В. Символобозначает операцию дизъюнкции. Эта операция соответствует союзу «или» в обычной речи, применяе­мому в неисключающем смысле.

Дело в том, что в обычной речи союз «или» может иметь два смысловых значения: неисключающее и исключающее. В пер­вом случае подразумевается, что из двух высказываний, по крайней мере, одно истинно, а может быть и оба истинны. Пример такого высказывания: «В жаркую погоду пьют воду или едят мороже­ное». Во втором случае полагают, что из двух высказываний истин­ным является только одно. Пример такого высказывания: «Сегодня мы поедем на экскурсию или пойдем на пляж». Конъюнкция высказываний соответствует перво­му случаю.

3. Выражение A  B(«если А, то В» или «А влечет В») означает высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно.

Такое высказывание называют импли­кацией высказыванийА и В. Высказывание А называетсяусловием(посылкой), высказывание В –заключением(следствием) импликации. Символобозначает опера­цию импликации.

В обычной речи операции импликации соответствует связка «если ..., то…». Отличие состоит в том, что связка предполагает смысловую за­висимость соединяемых высказываний, а для операциисмысло­вая связь несущест­венна.

Например, высказывания: «если 2 * 2 = 5, то трава синяя» и «если два больше трех, то восемь делится на четыре» являются истинными, так как у первого из них ложная посылка, а у второго – истинное следствие. Импликация: «если 2 * 2 = 4, то 5 < 2» ложна, поскольку ее условие истинно, а заключение ложно.