WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 |

Операции над множествами с целью получения новых множеств мож A U но представлять характеристическими предикатами и иллюстрировать с помощью диаграмм Эйлера-Венна, которые используют геометричесB А\ В кие фигуры. Универсальное множество изображают прямоугольником, его подмножества – в виде кругов или другой простой области внутри прямоугольника, а результат операции – заштрихованной областью.

A U Пример. Пусть универсальное множество U = {a, e, i, o, u} – гласные буквы английского алфавита; множества A = {a, i, u}, B = {e, i}.

Объединение множеств:

А В = {x | x A или x B}, А В = {a, i, u} {e, i} = {a, e, i, u}.

A U Пересечение множеств:

А—В B A B = {x | x A и x B}, A B = {a, i, u} {e, i} = {i}.

Дополнение (разность) множеств:

A \ В = {x | x A и x B}, A \ В = {a, i, u}\ {e, i} = {a, u}.

Абсолютное дополнение множества ( А ) – это элементы универсума без элементов множества А:

А = U \ A = {x | x A}, Операции над множествами Таблица A B A B A B A \ B A B x A x x A B x A B x x A \ B x A B 011010 10 10 0 1 А = {a, e, i, o, u}\ {a, i, u} = {e, o}.

Симметрическая разность множеств:

А — В = { | (x A и x B) или (x В и x А)}, А — В = (A \ В) (В \ А), А— В = {a, i, u} — {e, i} = {a, e, u}.

Очевидны следующие отношения включения результатов операций с множествами: A B А А В и A B В А В. Аналогично можно показать соотношения результатов других операций.

Определение множества в виде характеристического предиката (логического высказывания) А = {x | P(x)}, где х A, если P(x) – истинное высказывание, можно использовать для более компактного представления операций над множествами. Если закодировать предикат х A как 1, а x A как 0, то можно представить операции над множествами в виде табл. 3, в которой для множеств, указанных в заголовке, приведены значения соответствующих предикатов.

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

Варианты множеств X и Y Таблица № варианта XY 0{a, 1, a2, 9, 2, 19, c} {r, 1, t, 8, 9, d, 0} 1{b, 4, 3, c, 8, d, r2} {7, 9, r, 1, p, 2, 23} 2 {5, a, 6, 7, p, t, 1} {t, 1, 5, p, 4, 0, 17, 16} 3{b, c, 2, 5, t, 0, 4} {3, p, 4, 1, 9, s, t} 4{b1, 6, 3, c, d, 1, 2} {c, 2, 0, 1, p, r, 6} 5 {8, b2, a1, 7, 3, p, 1} {2, c, 7, t2, 0, 6, 21} 6 {1, d, 3, 6, c, 2, s} {5, p, r, 1, 14, 0, 11} 7 {2, p, 13, 4, t, 6, 21} {3, 13, r, p, 1, 5, 17} 8 {4, 9, p2, 31, 2, 3} {{2, t1, 3, 8, 26, 5, s} 9 {12, a1, 5, t, 2, 8, 4} {7, t, 4, 31, 1, 3, p, r} Основные понятия теории множеств Пусть множество цифр U = {0, 1, …,9} – это универсальное множество в данной работе. Используя множества U, а также X и Y, соответствующие варианту задания в табл. 4, требуется описать необходимые понятия теории множеств (словами и формулами) и получить новые множества согласно пунктам задания:

1. C1 = {x | xX и xU }; C2 = {x | x X и xU }.

2. D = {9 – x | x Y и x U }.

3. Семейство множеств (булеан) B(D) и его мощность |B(D)|.

4. С1 D.

5. С1 D.

6.

D.

7. C1 \ D.

vv1 v2 v3 v4 vVuv1 0 1 0 0 uuuuv1 v3 S55 = v2 1 0 2 0 v3 0 0 1 1 u7 uv4 1 0 0 0 v4 u8 v5 0 0 0 1 v5 uРис. 2. Орграф и его матрица смежности 8. C1 D.

9. Показать отношение включения между множествами: C1, D, С1 D, С1 D, C1 \ D, C1 D.

Для пояснения пунктов 4–8 использовать диаграммы Эйлера-Венна.

Обработка ориентированного графа Общие методические указания по обработке орграфа приведены (разд. 5). Пусть орграф G = (V, U) состоит из множества вершин V = ={v1, v2, v3, v4, v5} и множества дуг U = {u1 = (v1, v2), u2 = (v2, v1), u3 = =(v2, v3), u4 = (v2, v3), u5 = (v3, v3), u6 = (v3, v4), u7 = (v4, v1), u8 = (v5, v4), u9 = (v5, v5)}. Множество дуг можно для краткости задать также в виде множества пар номеров начала и конца дуг: U = {(1, 2), (2, 1), (2, 3), (2, 3), (3, 3), (3, 4), (4, 1), (5, 4), (5, 5)}. Количество вершин графа n = |V| = 5, а количество дуг |U| = 9.

Геометрическое и матричное представление заданного графа приведено на рис. 2. Орграф можно описать квадратной матрицей смежности Snґn, где n – количество вершин графа, а элемент sij равен количеству дуг (vi, vj), т. е. стрелок, идущих от вершины vi к vj.

Дуга может быть инцидентна не только вершинам, представляющим ее начало и конец, но и множеству вершин. На рис.1 выделена область, включающая подмножество вершин V1 = {v2, v3} (V1 М V). Говорят, что дуга u = (vi, vj) заходит в V1, если конец дуги vj находится в V1, и дуга u исходит из V1, если начало дуги vi находится в V1. В обоих случаях дугу u называют инцидентной подмножеству V1, причем она должна а) б) в) г) vvvvvvvvvvvvvРис. 3. Разделение орграфа на подчасти:

а – орграф; б – суграф; в – подграф; г – частичный граф пересекать границу выделенной области. Обозначим через U + (V1) и U - (V1) множества дуг, заходящих в V1 и исходящих из него. Например, для графа на рис. U + (V1) = {u1 = (v1, v2)}, U - (V1) = {u2 = (v2, v1), u6 = (v3, v4)}.

Разделение орграфа (рис. 3, а) заключается в удалении некоторых его частей. Суграф получается из исходного графа удалением некоторых его дуг, но с сохранением числа вершин. На рис. 3, б показан суграф без петель и параллельных дуг. Такой граф называется обыкновенным. Для а) б) в) vvvvv1 v3 v1 v v 11 v4 vvРис. 3. Разновидности орграфов:

а – симметрический; б – антисимметрический; в – полный него сохраняется связность исходного графа. Подграф образуется из исходного графа удалением некоторых вершин вместе с инцидентными им дугами (например, вершины v3 на рис. 3, в). Частичный подграф получится, если к исходному графу применены обе операции, описанные выше (рис. 3, г).



Некоторые специальные классы орграфов могут быть получены дополнительной трансформацией исходного графа.

Симметрическим называется граф G = (V, U), в котором (viV, vjV) (vi, vj) U (vj, vi) U (любые две смежные вершины vi и vj соединены двумя встречными, т. е. противоположно направленными дугами) (рис. 3, а).

Антисимметрическим называется граф G = (V, U), в котором (viV, vjV) (vi, vj)U (vj, vi) U (пара смежных вершин может быть соединена лишь в одном направлении, петли отсутствуют) (рис. 4, б).

Полным называется граф G = (V, U), в котором (viV, vjV) (vi, vj) U (vj, vi) U (i j) (любые две вершины соединены по крайней мере одной дугой, т. е. смежны) (рис. 4, в).

Рефлексивным называется граф, имеющий петлю в каждой вершине (vi, vi).

Транзитивным называется граф, в котором из наличия дуг u1 = (v, v’) и u2 = (v’, v”) следует существование дуги u3 = (v, v”).

Полным графом с петлями называется граф G = (V, Г), если (viV) Гvi = V (каждая пара вершин, различных или нет, соединяется дугой, т. е.

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

v2 Корень дерева v1 v3 1-й уровень v4 2-й уровень Рис. 5. Прадерево Элементарный контур в орграфе образует замкнутый путь с различными вершинами, кроме первой и последней. При поиске контуров следует исключить петли, которые не позволяют сдвинуться от начальной вершины. Контур можно задавать по вершинам и по дугам. Например, в графе рис. 2 можно выделить три элементарных контура: по вершинам: (v1, v2, v1), по дугам: (u1, u2); по вершинам: (v1, v2, v3, v4, v1), по дугам: (u1, u3, u6, u7); по вершинам: (v1, v2, v3, v4, v1), по дугам: (u1, u4, u6, u7).

Прадерево – это бесконтурный иерархический орграф. Его построение можно начинать от любой вершины исходного графа, принимая ее за корень дерева, если из нее исходит хотя бы одна дуга. На каждом следующем уровне располагаются смежные вершины, отстоящие от вершины предыдущего уровня на одну дугу, при этом вершины не повторяются. Вершины каждого уровня упорядочиваются по возрастанию их номеров слева направо. Построение следующего уровня начинается с вершины с меньшим номером. Например, для графа на рис. 2 построим дерево от вершины v2 как корня (рис. 5).

Путь от корня прадерева до других вершин – это элементарный путь минимальной длины (по количеству дуг).

Получение отображений Гv, Г n v, – есть процесс нахождения Гv множества вершин, в которые можно прийти от вершины v. Аналогич но, обратные отображения Г - v, Г - n v, представляют множества Г v вершин, из которых можно прийти в вершину v (дуги (стрелки) сходятся к вершине v).

Например, для графа на рис. 2 получим множества вершин, смежных с вершинами графа, в которые можно придти за одну дугу:

Гv1 = {v2}; Гv2 = {v1, v3}; Гv3 = {v3, v4}; Гv4 = {v1}; Гv5 = {v4, v5}.

Эти же множества можно получить по матрице смежности графа на рис. 2. Для каждой строки vi не нулевые значения в строке указывают смежные вершины (обозначения столбцов), в которые можно прийти из вершины vi за одну дугу.

Множества вершин, в которые можно прийти за две дуги от вершин v1, v2:

Г 2 v1 = Г{Гv1} = Г{v2} = {v1, v3};

Г 2 v2 = Г{Гv2} = Г{v1, v3} = Гv1 ИГv3 = {v2} И {v3, v4} = {v2, v3, v4}.

Множества вершин, в которые можно прийти за три дуги от вершин v1, v2:

Г 3 v1 = Г{Г 2 v1} = Г{v1, v3} = Гv1 Гv3 = {v2}{v3, v4} = {v2, v3, v4};

Г3v2 = Г{Г2 v2) = Г{v2, v3, v4} = Гv2 Гv3 Гv4 = {v1, v3} {v3, v4} {v1} = {v1, v3, v4}.

Транзитивные замыкания вершин v1, v2, т. е. множества вершин, в которые можно придти от этих вершин без повторения дуг:

= {v1} {v2} {v1, v3} {v2, v3, v4} = v1 = {v1}v1 2v1 … ={v1, v2, v3, v4};

= {v2} {v1, v3} {v2, v3, v4} {v1, v3, v2 = {v2}v2 2v2 … v4} = {v1, v2, v3, v4};

Из вершин v1, v2 в вершину v5 нельзя придти никаким путем.

Для графа на рис. 2 получим множества вершин, смежных с вершинами графа, из которых можно придти за одну дугу:

Г - v1 = {v2, v4}; Г - v2 = {v1}; Г - v3 = {v2, v3}; Г - v4 = {v3, v5}; Г - v= {v5}.

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

Множества вершин, из которых можно придти за две дуги к вершинам v1, v2:

Г -2 v1 = Г -{Г - v1} = Г - {v2, v4} = Г -{v2} Г – {v4} = {v1} {v3, v5} = {v1, v3, v5};

Г -2 v2 = Г -{Г - v2} = Г -{v1} = Г -{v2, v4} = Г – v2 Г – v4 = {v1} {v3, v5} = {v1, v3, v5}.

Множества вершин, из которых можно придти за три дуги к вершинам v1, v2: Г –3 v1 = Г –{Г –2 v1} = Г –{v1, v3, v5} = Г – v1 Г – v3 Г – v5= {v2, v4} {v2, v3} {v5} = {v2, v3, v4, v5};

Г –3 v2 = Г –{Г –2 v2}=Г –{v1, v3, v5} = Г – v1 И Г – v3 Г – v5 ={v2, v4} {v2, v3} {v5} = {v2, v3, v4, v5}.

Обратные транзитивные замыкания вершин v1, v2, т. е. множества вершин, из которых можно прийти к этим вершинам без повторения дуг:

= {v1} И {v2, v4} И {v1, v3, v5} = {v1, -v1 = {v1}-v1 -2v1 … v2, v3, v4, v5};

- = {v2} И {v1} И {v1, v3, v5} И {v2, v3, v2 = {v2} v2 -2v2 … v4, v5} = {v1, v2, v3, v4, v5};

Вершины v1, v2 доступны из любых вершин графа.

Обработка ориентированного графа Варианты множества дуг графа Таблица № Дуги графа { U } вар.





{ (0,1), (0,2), (0,5), (1,0), (1,0), (1,4), (1,5), (2,1), (2,3), (2,5), (3,0), (3,3), (3,4), (3,5), (4,1), (4,0), (4,4), (5,0), (5,1), (5,2), (5,4), (5,5) } { (0,0), (0,2), (0,4), (1,2), (1,3), (1,5), (2,2), (2,4), (2,5), (3,0), (3,2), (3,3), (3,5), (4,0), (4,1), (4,3), (4,5), (5,0), (5,2), (5,3), (5,4), (5,4) } { (0,0), (0,3), (0,5), (1,1), (1,3), (1,5), (2,2), (2,3), (2,3), (3,0), (3,1), (3,4), (3,5), (4,0), (4,2), (4,5), (5,0), (5,2), (5,3), (5,4), (5,4), (5,5) } { (0,2), (0,4), (0,5), (1,1), (1,2), (1,4), (1,5), (2,0), (2,3), (2,4), (2,5), (3,0), (3,0), (3,1), (3,3), (4,2), (4,4), (4,5), (5,0), (5,3), (5,4), (5,5) } { (0,3), (0,5), (1,1), (1,3), (1,5), (1,5), (2,0), (2,4), (2,5), (3,0), (3,1), (3,2), (3,4), (3,5), (3,5), (4,1), (4,2), (4,4), (4,5), (5,0), (5,2), (5,3) } Окончание таблицы № Дуги графа { U } вар.

{ (0,0), (0,2), (0,4), (0,5), (1,2), (1,4), (1,5), (2,0), (2,2), (2,5), (2,5), (3,0), (3,1), (3,3), (3,5), (3,5), (4,1), (4,3), (4,5), (5,0), (5,3), (5,5) } { (0,2), (0,4), (0,5), (1,1), (1,2), (1,4), (1,5), (2,0), (2,3), (2,5), (2,5), (3,0), (3,0), (3,1), (3,5), (4,2), (4,4), (4,5), (5,1), (5,3), (5,4), (5,5) } { (0,0), (0,1), (0,5), (1,3), (1,5), (1,5), (2,0), (2,4), (2,5), (3,0), (3,0), (3,2), (3,4), (3,5), (4,0), (4,2), (4,5), (4,5), (5,1), (5,2), (5,3), (5,5) } { (0,0), (0,2), (0,5), (1,0), (1,1), (1,4), (1,5), (2,1), (2,5), (2,5), (3,0), (3,3), (3,4), (3,5), (4,0), (4,1), (4,5), (5,0), (5,1), (5,3), (5,4), (5,5) } { (0,1), (0,4), (0,6), (1,1), (1,3), (1,4), (1,5), (2,0), (2,4), (2,5), (2,5), (3,0), (3,1), (3,3), (3,5), (4,2), (4,3), (4,5), (5,1), (5,3), (5,4), (5,4) } В соответствии с вариантом задания, приведенным в табл. 5, построить геометрическое и матричное представление графа и выполнить пункты задания по обработке графа G = (V, U), где V – множество вершин, U – множество дуг графа; количество вершин n = |V| = 6; вершины имеют нумерацию от 0 до 5. Пункты задания должны содержать формульные и словесные пояснения.

1. Определить входящие и исходящие дуги для множества вершин {1, 3, 5}.

2. Для множества вершин {0, 1, 2, 3} выделить подграф и из него получить симметрический, антисимметрический, полный и обыкновенный графы.

3. Выделить 4 элементарных контура графа.

4. От вершин i = 2, 5 как от корней построить прадеревья.

Определить Г i, Г - i, Г 2 i, Г – 2 i, для i = 0, 1, 2.

Гi Г i Работа с булевыми функциями Общие методические указания по обработке булевых функций приведены в п. 4.2 (раздел 6). Как было показано выше, для n-местной булевой функции f(x1, x2, …, xn) можно составить m=2n различных наборов аргументов из 1 и 0. Поскольку функция на любом наборе может принимать значение 0 или 1, то количество различных функций |P | = 2m. Например, n при n = 3 m =23 = 8, |P3| = 28 = 256.

Таблица x y z i Ni 0 0 0 1 1 0 1 1 7 0 0 1 1 1 1 0 1 6 0 1 0 0 1 1 0 1 5 0 1 1 0 1 0 1 1 4 1 0 0 1 1 0 1 1 3 1 0 1 1 1 1 0 1 2 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 Функции можно пронумеровать и задавать их десятичным номером (см. табл. 1 и 2). По таблице истинности функции f(x1, x2, …, xn) ее номер определяется столбцом значений функции на всех наборах аргументов следующим образом:

N( f ) = f0 20 + f121 +…+ fn-12n-1, где fi – значение функции f на наборе i, N i = 2i – множитель (“вес”) для набора i = 0, 1,…, n -1, причем нумерация значений функции в таблице идет снизу вверх. Таким образом, функцию можно задать, как fN (x1, x2, …, xn).

Пример. Построить таблицу истинности и определить номер функции f (x, y, z) = (x y) y z.

Для построения таблицы истинности заданной функции (табл. 6) следует использовать таблицы булевых функций одной и двух переменных (табл. 1 и 2), последовательно вычисляя компоненты формулы, представляющей функцию:

Вычислим десятичный номер функции:

N(f) = 120 + 021 + 122 +123 +124 + 125 + 126 + 127 = 1 + 4 + 8 + + 32 + 64 + 128 = 253, т. е. это функция f253 (x, y, z).

Для восстановления булевых значений функции по ее номеру необходимо разложить N(f) в двоичный код последовательным делением по модулю 2. Остатки от деления (0 или 1), начиная с младшего по номеру разряда, и последнее частное (1 – как старший разряд) определяют значения функции. Незаполненные вверху таблицы значения функции дополняются нулями.

Например, для функции f253 (x, y, z) определим последовательность ее булевых значений: 253/2 = 126 (остаток 1 – младший разряд); 126/2 = 63 (0); 63/2 = 31 (1); 31/2 = 15 (1); 15/2 = 7 (1); 7/2 = 3 (1); 3/2 = 1 (1).

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

На практике мы говорим о булевых функциях, а пишем формулы, хотя это не одно и то же. Количество n-местных булевых функций конечно, а количество представляющих их формул безгранично. Например, функции для двух переменных f8 (стрелка Пирса) и f14 (штрих Шеффера) можно представить двумя формулами (см. с. 15).

Тождественность соотношений A (x, y, z, …) = B (x, y, z, …) для формул, представляющих одну и ту же булеву функцию, можно доказать или опровергнуть построением таблиц истинности для формул А и В и проверкой совпадений или несовпадений значений этих представлений на всех наборах значений переменных x, y, z, …. Это общий алгоритм проверки любых тождественных соотношений в булевой алгебре, поскольку ввиду конечности числа наборов значений для любого конечного множества булевых переменных описанная процедура всегда заканчивается через конечное число шагов.

Pages:     | 1 |   ...   | 2 | 3 || 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.