Задачи по дискретной математике, математической логике и теории алгоритмов (стр. 2 )

ОТНОШЕНИЕ КАК ГРАФ

Существует геометрический способ задания (изображения) бинарных отношений на конечных множествах. Изобразим элементы такого множества точками на плоскости. Если выполнено соотношение, x1 R x2 , то проведем стрелку от x1 к x2 . Если x R x, то у точки x нарисуем петлю, выходящую из x и входящую в ту же точку. Такая фигура наз-ся ориентированным графом, или просто графом, а сами точки - вершинами графа. Пустому отношению соответствует граф без стрелок и петель. E соответствует граф, в котором присутствуют только петли. Полное отношение изображается полным графом, где все вершины соединены со всеми. Граф есть геометрическое изображение отношения аналогично тому, как график есть геометрическое изображение функции. Существует другой смысл понятия “граф”, который рассматривается ниже по тексту.

Свойства отношений

Определение. Отношение R на X наз-ся рефлексивным, если "xÎX xRx.

Содержательные примеры рефлексивных отношений: "быть похожим на"; "иметь общий признак с"; "быть не старше"; "£"; "³". Всегда E Í R. Отношения "быть родственником"; "быть старше"; "<"; ">" заведомо не рефлексивны. cii = 1.

Определение 2.11. Отношение R на X наз-ся антирефлексивным, если ("xÎX ) (x;x)Ï R, т. е. R ÇE =Æ . (" x, yÎC)(xRy Þ x ¹ y).

Выше приведенные примеры нерефлексивных отношений явл-ся антирефлексивными

Матрица, представляющая антирефлексивное отношение, имеет на главной диагонали нули, т. е. сij = 0.

Определение 2.12. Отношение R на X называется симметричным, если (" x, y)(x R y Þ y R x), или (" x, y)((x;y) Î R Þ (y;x)Î R). R Í R-1 .

Теорема. Отношение R симметрично Û R = R-1 .

Содержательные примеры таких отношений: "быть похожим на"; "быть одинаковым с"; "быть родственником"; "a ½½b"; "a ^ b". В соответствующем графе вместе с каждой стрелкой, идущей из вершины xi в вершину xj , существует и противоположно направленная стрелка. Поэтому иногда стрелки не указывают. bij = bji.

Определение 2.13. Отношение R называется асимметричным, если ("x, y)((x;y)ÎR Þ (y;x)Ï R). R ÇR-1 = Æ .

Из двух соотношений x R y и y R x по крайней мере одно не выполнено. Для матричных элементов это приводит к равенству bij bji = 0. В соответствующем графе не может быть стрелок, соединяющих две вершины в противоположных направлениях, т. е. направление стрелок всегда существенно.

Теорема 2.1. Если отношение R асимметрично, то оно антирефлексивно.

Определение 2.14. Отношение R называется антисимметричным, если (" x;y)((x R y & y R x) Þ (x = y)), R Ç R-1 Í E.

Для матричных элементов это приводит к утверждению: bij bji = 0, если i ¹ j.

Определение 2.15. Отношение R наз-ся транзитивным, если (" x, y, z)(x R z & z R y Þ x R y), R2 Í R.

Отношения <, £, >, ³, на множестве чисел; отношения конгруэнтности и подобия на множестве фигур; отношения параллельности на множестве прямых или плоскостей обладают свойством транзитивности.

Определение 2.16. Отношение R наз-ся антитранзитивным, если (" x, y, z)(xRz & zRy Þ ù xRy). (" x, y,z)((x, z)Î R & (z, y)Î R Þ (x, y) ÏR).

Отношение ^ на множестве прямых плоскости антитранзитивно, но в пространстве это неверно, так как $ три попарно ^ прямые. Таким образом, отношение ^ прямых пространства не является ни транзитивным, ни антитранзитивным.

Определение 2.17. Отношение R называется отношением эквивалентности, обозначаемое символом ~ (эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Широкое применение отношений эквивалентности в современной математике связано с тем, что отношение эквивалентности осуществляет разбиение множества, в котором оно определено, на классы, обычно принимаемые за новые математические объекты, т. е. с помощью отношений эквивалентности порождаются новые математические объекты, понятия. Если R - эквивалентность на множестве X и a Î X, то подмножество R(a) = { x | xÎX & (a;x)Î R } называется классом эквивалентности R .

Определение 2.18. Множество классов эквивалентности R на множестве X или, что то же самое, множество подмножеств, образующих соответствующее разбиение, называется фактормножеством множества X по эквивалентности R и обозначается через X/ R.

Пример 2.4. X - множество зерен, насыпанных в мешки. Для зерен x и y положим (x;y) Î R, если они лежат в одном мешке. Тогда классом эквивалентности служит множество зерен, лежащих в одном мешке, а фактормножеством X/ R - множество мешков.

Пример 2.5. X - множество фруктов (яблок, груш, персиков). Рассмотрим на X отношение R: "x является фруктом одного вида с фруктом y", которое разбивает X на 3 класса, причем X = Xя U Xг U Xп & Xя Ç Xг =Æ , Xя Ç Xп = Æ , Xг Ç Xп = Æ . Тогда фактормножеством X по отношению R является множество {Xя, Xг, Xп }, т. е. X/R = {Xя, Xг, Xп }

Пример. Z - множество целых чисел, Z0 и Z1 состоят из четных и нечетных чисел соответственно. Тогда {Z0 , Z1 } оказывается разбиением Z, и если R - соответствующая эквивалентность - бинарное отношение «иметь один остаток при делении на 2», то Z/R = { Z0 , Z1 }.

Пример 2.7. Отношением эквивалентности явл-ся отношение равенства на некотором числовом множестве и вообще диагональное отношение E на " непустом множестве X.

Отношение эквивалентности на множестве X связано с разбиением этого множества на попарно-непересекающиеся подмножества (классы). Обоснованием является следующая теорема 2.2 : Если отношение R на множестве X является эквивалентностью, то разбиение {X1 ,X2 ,...} множества X такое, что соотношение xRy выполняется в тех и только тех случаях, когда x и y принадлежат одному классу разбиения. Обратно: если задано разбиение {X1 ,X2 ,...} множества X и бинарное отношение R определено как "принадлежать одному классу разбиения", то R - эквивалентность.

Отношения порядка

Одним из основных способов познания - сравнение. Познание немыслимо без сравнения. В познавательном процессе сравнение может выступать и как элементарный познавательный акт, и как отправной пункт рассуждения, и как цель его. Сравнениями наполнена и наша повседневная практика: один источник света ярче, чем другой; одно тело более нагрето, чем другое; один маршрут от дома до работы требует меньше времени, но дороже; ... .

Отношения такие, как <, > между величинами или числами, - предшествует между точками прямой, Ì - строго включается между множествами, обладают свойствами антирефлексивности, асимметричности и транзитивности.

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

Определение 2.19. " антирефлексивное, асимметричное и транзитивное отношение R на множестве X (R Í X2 ) называется отношением строгого порядка. Для обозначения отношения используется символ < или символ > (имеются и другие), т. е. соотношения x < y и y > x равносильны и читаются соответственно: x предшествует (меньше, подчинен, ...) y и y следует за (больше, превосходит...) x.

Часто встречаются такие отношения, как ³ (неменьше), £ (небольше) между числами или величинами; | (делит), (делится на) между числами; Í (включается) между множествами, которые являются рефлексивными, антисимметричными и транзитивными. Такие и подобные им отношения являются примерами отношений порядка (в широком смысле, включающем равенство).

Определение 2.20. " рефлексивное, антисимметричное и транзитивное отношение R на множестве X (R Í X2 ) называется отношением (частичного) порядка. Для обозначения отношения используется символ £ или символ ³ (имеются и другие), т. е. соотношения x £ y и y ³ x равносильны и читаются соответственно: x не превосходит (небольше, ...) y и y не предшествует (неменьше, ...) x.

Отношение порядка, как, впрочем, и другие отношения, не может рассматриваться в отрыве от множества, между элементами которого оно установлено. Упорядоченную пару - множество и заданный в нем порядок, например (X, £), называют (частично) упорядоченным множеством.

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

Определение 2.21. Множество X называется линейно упорядоченным некоторым отношением порядка R (R Í X2 ), если для (" x, yÎX) и x ¹ y выполняется обязательно (x; y)ÎR или (y; x) ÎR, т. е. (X,R).

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

Например, Z упорядочивается £ , так как (" x, y)(x£y Ú y£x);

< , так как (" x, y)(x ¹ y Þ (x<y Ú y<x)).

Другими простейшими примерами бесконечных упорядоченных множеств (числовых) являются : N, Q, R, (0; 1), [0; 1] и др.

Одно множество можно упорядочивать разными способами, получая различные упорядоченные множества. N можно упорядочить естественным способом, но можно упорядочить по возрастанию отдельно все нечетные числа и отдельно все четные числа и считать каждое нечетное число предшествующим каждому четному, т. е. получая 1, 3, 5, ..., 2, 4, 6, предшествует 2 ).

Если для подмножеств данного множества X определить отношение включения : M £ M1 , если M Ì M1 Í X, то множество подмножеств X = {1; 2}, т. е. 2X = { Æ ; {1}; {2}; {1; 2}} не упорядочивается отношением Í (включается) или отношением Ì (строго включается) в указанном выше смысле. Множество 2X лишь частично упорядочивается, так как {1} ¹ {2} & ({1}; {2}) ÏR & ({2}; {1}) ÏR.

Примером частично, но не линейно упорядоченного множества является множество X всех пар натуральных чисел со следующим порядком: [ (m, n) < (m¢, n¢) ] Û [ (m < m¢) & ( n < n¢) ].

Множество N частично упорядочено, если m < n означает « n делится без остатка на m ».

Пусть М - множество всех непрерывных функций на отрезке [a, b]. Установив f £ g в том и только том случае, когда f (t) £ g(t) для " t, a £ t £ b, мы получим частичную упорядоченность.

Пусть X - упорядоченное множество. Элемент aÎX называется наименьшим (минимальным, первым), если "xÎX a £ x. Элемент bÎX называется наибольшим (максимальным, последним), если "xÎX x £ b. Во всяком линейно упорядоченном множестве имеется не более одного наименьшего и не более одного наибольшего элемента, причем, если таковой элемент $ , то он единственный. Так, для

N $ наименьший элемент, равный 1, и не $ наибольшего элемента,

Z, Q, R, (0; 1) не $ наименьшего и наибольшего элементов,

[0; 1] наименьший элемент равен 0 и наибольший элемент равен 1 . В множестве всех неположительных чисел максимальный элемент равен 0.

В частично, но не линейно упорядоченном множестве может быть много наименьших и наибольших элементов. Так, в приведенном выше частично упорядоченном множестве пар натуральных чисел все пары вида (1, n) и (m, 1) являются наименьшими элементами.

Понятие n - местного (n - арного) отношения является естественным обобщением понятия двуместного (или бинарного) отношения. n - местное отношение - отношение между n объектами.

Примеры: (" a, b,c ÎR) a = b + c

(" a, b,c, d ÎR) a:b = c:d

Определение 2.22. n - местным отношением между элементами множеств (на множествах) X1 ,... Xn наз подмножество их декартого произведения X1 ´...´ Xn .

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 2.1

по теме : автоматизированное исследование свойств отношений

Постановка задачи: отношение на множестве задается указанием упорядоченных пар или матричным способом. Определить, является ли оно: полным, диагональным, антидиагональным, пустым?

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 2.2

по теме : автоматизированное исследование свойств отношений (6 часа).

Постановка задачи: отношение на множестве задается указанием упорядоченных пар или матричным способом. Определить, каким из следующих свойств оно обладает (по вариантам): рефлексивности, антирефлексивности, симметричности, асимметричности, антисимметричности, транзитивности, антитранзитивности.

Вариант	Свойства отношения
1	Рефлексивность, симметричность, антитранзитивность
2	Антирефлексивность, асимметричность, транзитивность
3	Рефлексивность, антисимметричность, транзитивность
4	Антирефлексивность, симметричность, транзитивность
5	Рефлексивность, асимметричность, антитранзитивность
6	Антирефлексивность, антисимметричность, транзитивность
7	Рефлексивность, симметричность, антитранзитивность
8	Антирефлексивность, асимметричность, транзитивность
9	Рефлексивность, антисимметричность, транзитивность
10	Антирефлексивность, симметричность, транзитивность
11	Рефлексивность, асимметричность, транзитивность
12	Антирефлексивность, антисимметричность, транзитивность
13	Рефлексивность, симметричность, антитранзитивность

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 2.3.

по теме : автоматизированное определение отношений эквивалентности

и порядка (2 часа).

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

4. БУЛЕВЫ ФУНКЦИИ

ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИЙ В ДИЗЪЮНКТИВНОЙ (КОНЪЮНКТИВНОЙ) НОРМАЛЬНОЙ ФОРМЕ ДНФ (КНФ).

Цель работ:

- накопление опыта в составлении математической модели и разработке алгоритмов;

- изучение алгоритмов преобразования булевых выражений, заданных в дизъюнктивной (конъюнктивной) нормальной форме;

- практика в использовании ПЭВМ для решения задач дискретной математики;

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

Пример.

Постановка задачи. Булево выражение, заданное в конъюнктивной нормальной форме, преобразовать в сокращенную дизъюнктивную нормальную форму.

Для преобразования используется метод Нельсона, который заключается в последовательном применении к заданной КНФ выражения следующих операций:

- раскрытие скобок, т. е. преобразование вида

(a Ú b) & (c Ú d) = a & c Ú a & d Ú b & c Ú b & d;

- применение правила a & a = a;

- исключение тождественно нулевых конъюнкций, т. е. конъюнкций, содержащих вхождения вида a &`a = 0;

- исключение элементарных поглощений, т. е. выполнение преобразований вида a Ú a & c = a.

Получающаяся в результате этих операций ДНФ является сокращенной.

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 3.1.

по теме : автоматизированное получение СДНФ (СКНФ) булевой функции,

заданной таблично (4 часа).

Постановка задачи: для булевой функции, заданной таблично, получить СДНФ (СКНФ). Варианты заданий указываются в таблице.

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 3.2.

по теме : вычисление булевых формул - ДНФ, КНФ, полинома Жегалкина и скобочных формул, задаваемых в различных базисах, т. е. получение соответствующей булевой функции, задаваемой табличным способом. (6 часов)

Постановка задачи: для заданной ДНФ (КНФ, полинома Жегалкина, скобочной формулы) получить табличное задание соответствующей булевой функции. Варианты заданий указываются в таблице.

1. a) b)

c) d)

2. a) b)

c) d)

3. a) b)

c) d)

4. a) b)

c) d)

5. a) b)

c) d)

6. a) b)

c) d)

7. a) b)

c) d)

8. a) b)

c) d)

9. a) b)

c) d)

10. a) b)

c) d)

11. a) b)

c) d)

12. a) b)

c) d)

13. a) b)

c) d)

14. a) b)

c) d)

15. a) b)

c) d)

16. a) b)

c) d)

17. a) b)

c) d)

18. a) b)

c) d)

19. a) b)

c) d)

20. a) b)

c) d)

21. a) b)

c) d)

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 3.3.

по теме : автоматизированное упрощение (минимизация) ДНФ (6 часов).

Постановка задачи: для заданной ДНФ получить минимальное (по числу букв) выражение (ДНФ или суперпозиционную формулу):

1) на основе элементарных свойств логических операций;

2) на основе эквивалентностей, использующих правила: склеивания, поглощения, вычеркивание буквы;

3) на основе обобщенного склеивания.

Варианты заданий указываются в таблице.

5. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 4.1

по теме : моделирование процессов (2 часа).

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

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 4.2

по теме : моделирование (вычислительный эксперимент) (2 часа).

Постановка задачи: Две точки в момент времени t0 начинают двигаются из заданных положений по пересекающимся прямым с заданными законами движения. Определить: а)расстояние между ними в момент времени t ; б) минимальное расстояние между ними.

Л А Б О Р А Т О Р Н А Я Р А Б О Т А № 4.3.

Нечетный вариант:

В остроугольный DАВС, заданный координатами вершин на основе метода математического моделирования вписать DMNK (определить его вершины, принадлежащие сторонам исходного) , который имеет наименьший периметр среди всех возможных таких треугольников.

Четный вариант:

В плоскости Oxy даны три точки . Найти такую 4-ю точку плоскости на основе метода математического моделирования, для которой сумма длин была минимальной.

Дать геометрическую иллюстрацию.

Вариант	К о о р д и н а т ы т о ч е к A, B, C
	xA	yA	xB	yB	xC	yC
1	2	5	77	2	40	86
2	39	69	3	6	80	4
3	3	84	66	90	33	3
4	5	67	76	96	73	2
5	6	3	2	81	84	41
6	7	8	79	3	43	96
7	8	92	63	89	31	4
8	6	65	64	94	71	5
9	11	6	4	90	92	46
10	4	5	75	5	42	93
11	9	69	63	98	69	6
12	6	7	90	3	43	87
13	36	75	5	6	88	5
14	3	81	70	95	36	4
15	4	3	5	92	84	50
16	55	90	3	7	89	3
17	2	94	60	3	89	90
18	5	40	55	90	87	70
19	4	5	3	89	82	50
20	7	96	86	99	36	9
21	3	40	85	3	90	86
22	49	92	4	6	86	4
23	3	89	61	4	86	91
24	3	4	6	95	81	46
25	5	41	54	91	86	69
26	84	66	3	39	55	92
27	6	85	71	94	35	3
28	2	3	4	91	83	51
29	54	97	5	4	91	3
30	3	4	9	89	80	47

6. АЛГОРИТМЫ ОПТИМИЗАЦИИ НА ГРАФАХ