Учебное пособие 1920

Первый элемент из множества X может быть сопоставлен с любым из n элементов множества Y, а для каждого такого сопоставления второй элемент множества X может быть сопоставлен с любым из оставшихся n-1 элементов множества Y и т. д. Общее число взаимно однозначных соответствий для n-элементных множеств будет равно n(n-1) ... 1=n!

1.5. Счетные и несчетные множества

Множества будут бесконечными, если при установлении между ними взаимно однозначного соответствия требуется оперировать с бесконечно большим числом элементов множества. Для сопоставления бесконечных множеств будем брать натуральный ряд чисел N: 1, 2, .... n... и если бесконечное множество сопоставить во взаимно однозначное соответствие с натуральным рядом чисел, то множество называют счетным. В противном случае его называют несчетным.

Пример 1 .Рассмотрим множество равносторонних треугольников, в которых вершинами каждого треугольника являются середины сторон построенного треугольника (рис. 1.2). Бесконечное множество равносторонних треугольников приводится во взаимно однозначное соответствие с натуральным рядом чисел. Бесконечное множество таких равносторонних треугольников является счетным.

Рис. 1.2. Пример счётного множества

180

Пример 2. Множество квадратов целых чисел 1, 4, 9,

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

Пример 3. Счетным будет множество Z целых чисел.

2.ЭЛЕМЕНТЫ ТЕОРИИ ОТНОШЕНИЙ

2.1.Бинарные отношения. Свойства отношений

Решение многих задач требует рассматривать элементы, между которыми имеется зависимость.

Множество X имеет n-арное отношение – подмножество Rn-й декартовой степени X n Χ Χ ... X данного множест-

ва. Носителем отношения будет R Xn,Χ.

Упорядоченные элементы x1,x2,...,xn X имеются в от-

ношении R, если x1,x2,...,xn R.

Одноместное отношение будет унарным и соответствует подмножеству X.

Пусть R={(x,y)| х≤у; (х,у) R}, определено на множестве. Тогда xRy означает, что х≤у, и в качестве обозначения этого

1, (xi ,xj ) R; rij 0, (xi,xj ) R.

Эта матрица дает полную информацию о связях между элементами и вводится как информация на компьютер.

Она состоит из нулей и единиц.

Пример. Пусть = { , , }, а таблица описывает бинарное отношение (табл.2.1).

181

ным, если x, у, z ((х,у) R и (у, z) R (x,z) R).

Следующие отношения для множества (R) имеют свойства рефлексивности, симметричности и транзитивности:

R={(x,y)| x,y R и x = y}; R={(x,y)| x,y R и x2 = y2}.

Отношение R={(x,y)| x, y R и x y} будет рефлексивным, транзитивным и несимметричным.

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

Если на множестве Х определено отношение V X Χ, то совокупности G=(X,V) называют графом, здесь Х – множество вершин графа, а V – множество линий, соединяющих все или часть этих вершин.

Если в паре (х,у) играет роль порядок следования элементов, то эту линию будем называть дугой (или направленным отрезком прямой), а граф G - ориентированным графом или орграфом. Граф G в противном случае называется неориенти-

рованным графом или неорграфом.

Две противоположно направленные дуги между двумя

182

вершинами в графе обычно заменяют ребром.

Граф задается с помощью матрицы смежности А={aij}n n

(n=|X|), где

1, (xi,xj ) V; aij 0, (xi,xj ) V.

Матрица смежности графа совпадает с матрицей бинарного отношения.

Пример. Пусть матрица бинарного отношения R, заданного на универсальном множестве U={a,b,c,d}, имеет вид

(табл. 2.2).

Таблица 2.2 Пример бинарного отношения для построения графа

Граф имеет вид (рис. 2.1).

e

с d

Рис. 2.1. Пример графа с бинарными отношениями R

Если отношение V рефлексивно, то в каждой вершине графа G имеется петля; если V симметрично, то любые две вершины графа G соединены парой дуг; если V антисимметрично, то в G любые две вершины х и у (х,у) V соединены дугой. Граф G имеет транзитивное отношение V, тогда для вся-

183

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

Отношение будет множеством упорядоченных пар, тогда для негоT можно ввести операции такие же, что и для множеств (операции объединения, пересечения, разности и дополнения). Также для отношений определена операция инверсии отношения R (или обратное к отношению R): ={(x,y)| (y,x) R}.

Матрица обратного отношения R 1- это транспонированная матрица отношения, т. е. RT.

Если , - отношения на множестве X, тогда композицией отношений R1 и R2 называется отношение:

3)(PoQ)oR=Po(QoR) (ассоциативность композиции).

2.2.Отношение эквивалентности и разбиения

Рассмотрим специальные типы отношений. Рефлексивное, симметричное, транзитивное отношение

будем называть отношением эквивалентности.

Классом эквивалентности K(x) элемента х называется множество элементов у Х, каждый из которых находится с этим элементом в отношении эквивалентности

Сущность моделирования устанавливает отношение эквивалентности между двумя системами.

Модель называется изоморфной, если между моделью и реальной системой имеется полное поэлементное соответствие.

184

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

2.3. Отношения порядка. Диаграмма Хассе

Эквивалентность является обобщением отношения равенства. Эквивалентные элементы определены как «равные». Обобщение отношения будет называться отношением порядка.

Отношение R X2 называется предпорядком, при этом R рефлексивно и транзитивно. Например, отношение

R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(1,3)} на X={1,2,3} будет предпорядком. Отношение нестрогого порядка – это рефлексивное, антисимметричное, транзитивное отношение (обозначается ). Антирефлексивное, антисимметричное, транзитивное отношение будет отношением строгого порядка ( ).

При этом отношения строгого и нестрогого порядков называются отношениями упорядоченности. Отношение, которое обратно отношению упорядоченности, будет отношением упорядоченности, т. е. ( ) 1 = .

Пример. Пусть Y – некоторое множество. Отношение включения на множестве подмножеств P(Y) будет отношением нестрогого порядка.

Отношение «х старше у» на некотором множестве L людей является отношением строгого порядка. Если два элемента х и у множества Х находятся в отношении порядка, то Х назы-

вается множеством линейно упорядоченным или цепью. В про-

тивном случае множество Х называется частично упорядоченным. Можно в частично упорядоченном множестве выделить цепь. Цепь с повторяющимися элементами называется мультицепью. Пусть между элементами х и у имеется отношение порядка, тогда они называются сравнимыми, в противном слу-

чае – несравнимыми.

Антицепью называется подмножество частично упорядо-

185

ченного множества, где два элемента несравнимы. Специальным интервалом частично упорядоченного множества P={z X|x z у}. будет замкнутый интервал [x,y], а для множества P={z X|x z у} интервал (x,y) будет открытым.

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

Пусть имеем множество Х с отношением на множестве частичного порядка .

Элемент y покрывает элемент x, если х у и нет никако-

го элемента z X, такого что х z у. Т. е. у покрывает х тогда, когда х у и [х,у]={х,у}. Частично упорядоченное множество представляется в виде схемы.

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

Пример. Отношение включения на булеане Р(Х), Х={а,b,с}. Оно будет частично упорядоченным множеством.

Множество Р(Х) имеет восемь элементов: { ,{a},{b}, {c},{a,b},{a,c},{b,c},{a,b,c}}. Диаграмма Хассе этого отноше-

ния (рис. 2.2):

Рис. 2.2. Диаграмма Хассе для отношения включения

186

Из диаграммы Хассе следует, что х у, если можно пройти из точки х в точку у вдоль восходящих отрезков, соединяющих точки (cмена направления движения допускается в точках диаграммы).

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

Пусть имеется частично упорядоченное множество X. Верхней гранью Элементов х и у из множества Х называется элемент z Х, такой, что z x и z y, а их нижней гранью – любой элемент t X, такой, что t х и t у.

На диаграмме Хассе х у означает, что имеется путь из x в y; верхняя грань x и y – это вершина, в которой есть путь из x и y; нижняя грань x и y – это вершина, из которой есть путь и в x и в y.

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

3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

3.1. Составные высказывания

Основные понятия

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

Повествовательное предложение (если оно истинно

или ложно) называется высказыванием.

Будем обозначать высказывания буквами: A, B, C,…. Элементарные высказывания называются атомами. Употребляемые в обычной речи логические связки "и",

"или", "если..., то...", "эквивалентно" и т. д. помогают строить новые, "сложные" высказывания.

187

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

зывания.

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

Для высказывания можно определить его истинностное значение или ложность («И», если высказывание истинно или «Л», если высказывание ложно).

Составные высказывания

При помощи логических операций из атомов (элементарных высказываний) строятся сложные высказывания.

Порядок их выполнения определяется скобками. Характеристика высказывания в таблице истинности.

3.2. Основные логические операции. Формулы логики

Логические операции

Рассмотрим A, В – некоторые высказывания, для которых не известно их истинностное значение.

188

Отрицанием высказывания A называется высказывание A ( A), которое истинно, если A – ложно, и ложно, если A истинно. Связке "НЕ" соответствует логическая операция отрицания.

Таблица 3.2

Таблица истинности для отрицания

ЛИ

Конъюнкцией высказываний A и B называется высказывание A B ("A и B"), которое истинно тогда, когда A, B – истинно. Связке "И" соответствует операция конъюнкции, обозначается операция знаком (или ).

Таблица 3.3

Таблица истинности конъюнкции

Дизъюнкцией высказываний A и B называется высказывание A B ("A или B"), которое ложно тогда, когда A, B – ложны. Связке "ИЛИ" соответствует операция дизъюнкции, обозначение операции – знак .

Таблица 3.4

Таблица истинности дизъюнкции

189