Метод Квайна-МакКласки. Выпишем наборы, на которых функция принимает единичное значение. - презентация

1 Метод Квайна-МакКласки

2 Выпишем наборы, на которых функция принимает единичное значение

3 Отсортируем наборы по количеству единиц

4 Начинаем склеивание *1 ( ) 00*11 ( ) 1*011 ( ) 01*00 ( ) 0*011 ( ) 110*1 ( ) *1000 ( ) *0011 ( ) 1101* ( ) 0110* ( ) 1001* ( ) 1*010 ( ) 1100* ( ) 110*0 ( )

5 Второй этап склеивания *1000*00111*011 01*000*011110*1 000*11* * 00*11 110*0 1100* 0110* 1001* 000*1* *00**011 (0*011+1*011) *10001*01* (1*010+1*011) 00*11 110** (110*0+110*1) 110** (1100*+1101*) 0110* 1*01* (1001*+1101*)

6 Дальше склеивание невозможно, строим импликантную матрицу * *00 ++ * * ** *01* * ** * ++

7 Выделим существенные импликанты Импликанта *0011 окзалась избыточной, а из двух оставшихся импликант выбираем любую и записываем минимальную ДНФ *00+ *1000+ *0011

8 Результат

9 Бинарные отношения

10 Определение Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А. (однородное отношение) Если (x, y) R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

11 Примеры Отношение a= {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел. Из школьного курса На множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты"; на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают"; на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".

12 Пример Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение R 1 = { (x, y) | x 2 + y 2 1 } определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение R 2 = { (x, y) | x y } полуплоскость, а отношение R 3 = { (x, y) | |x-y| 1 } полосу.

13 Способы задания Перечисление всех пар из базового множества А и базового множества В A={a1,a2} B={b1,b2,b3}, ={(a1, b1), (a1,b3), (a2, b1)} Отношения могут задаваться формулами: формулы y = x 2 +5x - 6 или x + y < 5 задают бинарные отношения на множестве действительных чисел; формула x + y = любовь, задает бинарное отношение на множестве людей.

14 Графический метод задания a= {(a, d), (a, c), (b, b), (c, a), (e,d), (e, a)}

15 Графовое представление Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x i, а наличие дуги, соединяющей вершины x i и x j, означает, что (x i,x j ) R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. А={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}

16 Матричная форма задания Пусть на некотором конечном множестве X задано отношение a. Упорядочим каким-либо образом элементы множества X = {x 1, x 2,..., x n } и определим матрицу отношения A = [a ij ] следующим образом:

17 Определения Диагональ множества A A, т.е. множество ={(x,x) | x A}, называется единичным бинарным отношением или отношением равенства в A. Областью определения бинарного отношения R называется множество R={ x A | y B, (x, y) R }. Областью значений бинарного отношения R называется множество R={ y B | x A, (x, y) R }. Образом множества X относительно отношения R называется множество R(X) = { y B | x X, (x, y) R }; прообразом X относительно R называется R -1(X).

18 Операции над бинарными отношениями Пересечение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 }. = > Объединение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 или (x, y) R 2 }. Разностью отношений a и b, заданных на множестве X, называется отношение a\b, такое, что: R 1 \R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 } Дополнение к отношению R={ (x, y) | (x, y) (A A)\R}.

19 Обратное отношение R –1 = { (x, y) | (y, x) R}.

20

21 Композиция отношений Композиция (суперпозиция) отношений R=R 1 oR 2 содержит пару (x, y) тогда и только тогда, когда существует такое z A, что (x, z) R 1 и (z, y) R 2.

22 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность xM (xRx) Антирефлексивность xM ¬(xRx)

23 Рефлексивность отношений Обозначим через Ix отношение на множестве X, состоящее из пар вида (a, a), где a X: Ix = {(a, a)| a X}. Отношение Ix обычно называют диагональю множества X или отношением тождества на X. Очевидно, что отношение a на множестве X рефлексивно, если диагональ Ix является подмножеством множества a: Ix a. Отношение антирефлексивно, если диагональ Ix и отношение a не имеют ни одного общего элемента: Ix a = Ø.

24 Свойства отношений Симметричность xRy yRx или R=R -1

25 Свойства отношений Антисимметричность Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным. Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y) R означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x) R - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y. Отношение " " также антисимметрично: если x y и y x, то x=y. Асимметричность Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

26 Свойства отношений Для любого отношения R вводятся понятия симметричной части отношения R s = R R -1 и асимметричной части отношения R a = R \ R s. Если отношение R симметрично, то R= R s, если отношение R асимметрично, то R= R a. Примеры. Если R - " ", то R -1 - " ". Транзитивность отношений