Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 36
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
к лабораторным работам
«ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ»
Часть 1
Донецк-2010
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
к лабораторным работам
по курсу “Основы дискретной математики“,
часть I
Рассмотрено на заседании кафедры прикладной математики и информатики протокол № 13 от 30.08.2010
Лабораторная работа № 1
Способы задания множеств. Операции над множествами.
Основные соотношения алгебры множеств
Цель работы: изучение способов задания множеств, приобретение практических навыков в выполнении операций над множествами и проверке основных соотношений алгебры множеств.
Теоретическая справка
Множество – объединение в одно целое различимых между собой элементов.
Конечное множество – множество, состоящее из конечного числа элементов.
Бесконечное множество – множество, состоящее из бесконечного числа элементов.
Способы задания множеств
1) Перечисление элементов.
Например:
А = {1,3,5,6,889,-10}
2) Задание определяющего свойства.
Например:
X = { x | 1 > х > 5, x є Z };
А = {a2 | a - четное число}.
Пустое множество – множество, не содержащее ни одного элемента. Пустое множество обозначается Æ или .
Универсальное – множество, содержащее все возможные элементы. Универсальное множество обозначается U.
Утверждение "а является элементом множества А" записывается в виде аА (а принадлежит множеству А).
Утверждение "а не является элементом множества А" записывается в виде аА (а не принадлежит множеству А).
Множества А и В называются равными (обозначается А = В), если они состоят из одних и тех же элементов.
Если каждый элемент множества А является также элементом множества В, то говорят, что А содержится или включается в В.
В этом случае пишут А В.
Множество A называется подмножеством множества B, если .
В тех случаях, когда одновременно имеют место соотношения и AB, говорят, что A строго включается в B, и используют запись A B.
Операции над множествами
Объединением множеств A и B (обозначается A B) называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, т.е
A B = x x A или x B.
Пересечением множеств A и B (обозначается A Ç B) называется множество, состоящее из всех элементов, принадлежащих каждому из этих множеств, т.е.
А Ç B = x x А и x B.
Разностью множеств А и B (обозначается А \ B) называется множество, состоящее из всех элементов множества A , не принадлежащих множеству B, т.е.
А \ B =x x А и x B.
Дополнением множества А в универсальном множестве U (обозначается , А) называется множество, состоящее из всех элементов универсального множества U, не принадлежащих множеству А, т.е.
А = U \ A.
Симметрической разностью множеств A и B (обозначается AB или AB) называется множество, состоящее из всех элементов, принадлежащих в точности одному из этих множеств, т.е.
A B x либо x A и x B, либо x A и x B
A B = (A \ B) (B \ A) = (A B) \ (A B)
Операции над множествами можно проиллюстрировать графически с помощью кругов Эйлера. В этом случае исходные множества изображают в виде точек плоскости, ограниченных кругом или любой другой замкнутой линией, а множество-результат выделяется штриховкой. Штриховки может иметь разный цвет, наклон и плотность. Универсальное множество изображается множеством точек плоскости, ограниченных прямоугольником.
Например.
Пусть множества и заданы на универсальном множестве
, .
Тогда, ,, , , , ,.
Основные законы алгебры множеств
1) Коммутативные законы
А В = В А
А В = В А
А В = В А
2) Ассоциативные законы
А (В С) = (А В) С
А (В С) = (А В) С
3)Дистрибутивные законы
А (В С) = (А В) (А С)
А (В С) = (А В) (А С)
4) Законы с и U
А = А А U = А А = U
А = А U = U А =
= = U
6) Законы идемпотентности
А А = А А А = А = А
7) Законы поглощения
А (А В) = А
А ( В) = А В
А (А В) = А
А ( В) = А В
8) Законы де Моргана
=
=
9) Законы склеивания
(А В) ( В) = В
(А В) ( В) = В
Справедливость законов алгебры множеств доказывается на основе определения равенства: Х = Y, если
1) Х Y: x X x Y;
2) Y Х: y Y y X.
Сформулированный принцип называют интуитивным принципом объемности.
Задание к лабораторной работе.
Заданы множества X, Y, Z, U.
Правило образования множеств X, Y, Z и U:
X - множество букв имени студента;
Y - множество букв отчества студента;
Z - множество букв фамилии студента;
U - универсальное множество = X Y Z {ъ,ё, гласные, отсутствующие в множествах X, Y, Z}.
1. Вычислить:
- X Y , X Z, Y Z, X Y Z;
- Y Z , X Y Z;
- X \ Z, Z \ X;
- X ;
- X Z ;
- X , X (Y Z);
- (X \ Z) (Y \ Z).
2. Нарисовать диаграммы Эйлера для:
- X Y Z;
- (X Y) ;
- ();
- (X \ Z) (Y \ Z).
3. Проверить экспериментально на множествах X, Y, Z справедливость следующих утверждений:
4. Записать булеан для произвольного подмножества множества Z мощности 4. Выписать все возможные разбиения и привести примеры 3 покрытий этого подмножества.
Контрольные вопросы.
Лабораторная работа № 2
Отношения на множествах
Цель работы: изучение способов задания отношений, приобретение практических навыков в проверке основных свойств отношений, классификация отношений.
Прямое (декартово) произведение множеств Х и Y – множество упорядоченных пар, таких что:
.
При X = Y множество называется декартовой степенью множества X и обозначается X2.
Бинарное отношение на множествах X и Y – произвольное подмножество прямого произведения двух множеств .
Если Х2, то отношение задано на множестве Х.
Если (x,y), то (x,y) находятся в отношении или связаны отношением : х y или y = (х) .
Область определения D бинарного отношения - множество первых элементов каждой упорядоченной пары D = {x | (x,y) }.
Область значений J бинарного отношения - множество вторых элементов каждой упорядоченной пары
J = {y | (x, y) }.
Способы задания отношений
= {(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
= {(n,m)| n = 2*m}
={(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
={(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
2 |
0 |
0 |
0 |
1 |
0 |
0 |
|
3 |
0 |
0 |
0 |
0 |
0 |
1 |
|
4 |
0 |
0 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 |
0 |
1 |
0 |
0 |
0 |
0 |
Свойства бинарных отношений
Пусть задано на множестве X, Х2
Рефлексивность: х Х х х .
Антирефлексивность: х Х х х.
Нерефлексивность: х Х (x, x) .
Симметричность: х, y Х х y => y х.
Антисимметричность: х, y Х х y, y х x = y.
Транзитивность: х, y, z Х х y, y z => x z.
Отношение порядка – антисимметрично, транзитивно.
Отношение нестрого порядка () - рефлексивно,
антисимметрично,
транзитивно.
Отношение строгого порядка () - антирефлексивно,
антисимметрично,
транзитивно.
В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой.
Отношение эквивалентности ( ) - рефлексивно,
симметрично,
транзитивно.
Класс эквивалентности для х : [ x ] = { y Х | x y }.
Обратное отношение получается путём перестановки значений в парах исходного отношения.
Композиция отношений и - отношение, состоящее из пар
○ = {(x, z)| х у, y z }
Например:
Отношения и заданы на множестве Х = {1, 2, 3, 4, 5, 6,}.
= {(1,4), (2,5), (3,6), (4,1), (6,3)},
= {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.
Область определения D = {1, 2, 3, 4, 6}.
Область значений J = {1, 3, 4, 5, 6}.
Обратное отношение -1 = {(4,1), (5,2), (6,3), (1,4), (3,6)}.
Отношение - антирефлексивно, не симметрично, не транзитивно.
Область определения D = {1, 2, 3, 4, 5, 6}.
Область значений J = {1, 3, 4, 5, 6}.
Отношение - не рефлексивно, антисимметрично, не транзитивно.
Композиция ○ = {(1,5), (2,6), (3,6), (4,1), (6,4)}.
Например:
Отношение = { (x, y) | сравнение по модулю m, x,y N }.
Отношение сравнения по модулю m на множестве натуральных чисел: x = y mod m, что означает x и y имеют одинаковый остаток при делении на m (классы вычетов по модулю m).
Отрезок натурального ряда N4={1,2,3,4}.
Отношение сравнения по модулю 2 на N4 :
= { (1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2) ,(4,4)}.
Область определения D = {1, 2, 3, 4}.
Область значений J = {1, 2, 3, 4}.
Отношение - рефлексивно, симметрично, транзитивно.
Отношение - отношение эквивалентности.
Классы эквивалентности: [ 1 ]={ 1,3 }=[ 3 ]
[ 2 ]={ 2,4 }=[ 4 ].
Например:
Отношения и заданы на множестве N4 .
={ (1,2), (2,3), (1,3), (3,4), (2,4), (1,4) }
={ (1,1),(2,2),(3,3),(4,4) }.
Область определения D = { 1, 2, 3 }.
Область значений J = { 2, 3, 4 }.
Отношение - антирефлексивно, антисимметрично, транзитивно.
Отношение - отношение строгого порядка.
Область определения D = { 1, 2, 3 ,4 }.
Область значений J = { 1, 2, 3, 4 }.
Отношение - рефлексивно, симметрично, антисимметрично, транзитивно.
Отношение - отношение нестрогого частичного порядка.
Отношение - отношение эквивалентности.
Классы эквивалентности: [ 1 ]={ 1}
[ 2 ]={ 2 }
[ 3 ]={ 3 }
[ 4 ]={ 4 }.
Функциональные отношения
Пусть Х х Y.
Функциональное отношение – бинарное отношение , для которого
х D y Y: х y .
Всюду определённое отношение – бинарное отношение , для которого D =Х ("нет одиноких х").
Сюръективное отношение – бинарное отношение , для которого J = Y ("нет одиноких y").
Инъективное отношение – бинарное отношение, в котором разным х соответствуют разные у.
Биекция – функциональное, всюду определённое, инъективное, сюръективное отношение, задаёт взаимно однозначное соответствие множеств.
Например:
Пусть = { (x, y) R2 | y2 + x2 = 1, y > 0 }.
Отношение - функционально,
не всюду определено ("есть одинокие х "),
не инъективно (есть разные х, которым соответствуют одинаковые у),
не сюръективно ("есть одинокие у "),
не биекция.
Например:
Пусть = {(x,y) R2 | y = x+1}
Отношение - функционально,
Отношение - всюду определено ("нет одиноких х "),
Отношение - инъективно (нет разных х, которым соответствуют одинаковые у),
Отношение - сюръективно ("нет одиноких у "),
Отношение - биективно, взаимно-однородное соответствие.
Например:
Пусть ={(1,2), (2,3), (1,3), (3,4), (2,4), (1,4)} задано на множестве N4.
Отношение - не функционально, x=1 соответствует три y: (1,2), (1,3), (1,4)
Отношение - не всюду определенно D={1,2,3} N4
Отношение - не сюръективно I={1,2,3} N4
Отношение - не инъективно, разным x соответствуют одинаковые y, например (2,3) и (1,3).
Задание к лабораторной работе
(N1 х N2) (N2 х N1);
(N1 х N2) (N2 х N1);
(N1 N2) x (N1 N2);
(N1 N2) x (N1 N2),
где N1 = {цифры номера зачетной книжки, три последние};
N2 = {цифры даты и номера месяца рождения}.
2. Отношения и заданы на множестве N6={1,2,3,4,5,6}.
Описать отношения , , -1, ○ , -1 ○ списком пар.
Найти матрицы отношений и .
Для каждого отношения определить область определения и область значений.
Определить свойства отношений.
Выделить отношения эквивалентности и построить классы эквивалентности.
Выделить отношения порядка и классифицировать их.
= { (m, n) | сравнение по модулю 2}
= { (m, n) | m делитель n }
= { (m, n) | сравнение по модулю 3}
= { (m, n) | m2=n }
= { (m, n) | m = n }
= { (m, n) | m n }
= { (m, n) | сравнение по модулю 4}
= { (m, n) | m n }
= { (m, n) | m делится на n }
= { (m, n) | m делитель n }
= { (m, n) | (m + n) 5 }
= { (m, n) | (m - n) 2 }
= { (m, n) | 2 (m - n) 4 }
= { (m, n) | m n }
= { (m, n) | m 2 n }
= { (m, n) | m < n +2 }
= { (m, n) | m n }
= { (m, n) | m n , m- четно}
= { (m, n) | 1 (m - n) 3 }
= { (m, n) | m n }
= { (m, n) | m n , n-четно }
= { (m, n) | (m - n) 1 }
= { (m, n) | сравнение по модулю 2 }
= { (m, n) | 1 (m - n) 3 }
= { (m, n) | m не делится нацело на n }
= { (m, n) | m делится нацело на n }
= { (m, n) | m делитель n }
= { (m, n) | m делится нацело на n }
= { (m, n) | m / n - нечетно}
= {(m, n) | m и n имеют общий делитель, отличный от 1}
Выполнить это же задание для отношений и из пункта 3 лабораторной работы.
30) f={ (x, y) R2 | x = y3, y - 2 }.
Контрольные вопросы
1.Декартово или прямое произведение множеств.
2.Определение бинарного отношения.
3.Способы описания бинарных отношений.
4.Область определения и область значений.
5.Свойства бинарных отношений.
6.Отношение эквивалентности и классы эквивалентности.
7.Отношения порядка: строгого и нестрого, полного и частичного.
8.Классы вычетов по модулю m.
9.Функциональные отношения.
10. Инъекция, сюръекция, биекция.
Лабораторная работа № 3
Булевы функции. Законы алгебры логики. Аналитические способы описания. Полные системы функций
Цель работы: изучение способов описания булевых функций, практическое применение законов алгебры логики, представление функций в различных базисах.
Определение функции алгебры логики
Пусть множество Х состоит из двух элементов 0 и 1, Х={0,1}; множество Y=Xn = {(x1, …,xn) | i = , xi X}.
Двоичный набор – совокупность координат некоторого фиксированного вектора (х1, …, хn) Хn.
Каждому двоичному набору можно поставить в соответствие некоторый номер, равный двоичному числу соответствующему данному набору.
Пусть (х1, х2, …, хn) – логический набор, тогда х1*2n-1+х2*2n-2+…+xn*20 – номер набора.
Например:
(0,1,1) = 022 + 121+120 = 3
(0,0,1,1) = 023+022 +121+120 = 3
Замечание. Чтобы восстановить набор по номеру – нужно знать количество аргументов.
Логическая переменная – это переменная, которая может принимать только два значения: истина или ложь (TRUE/FALSE, 1/0).
Функция алгебры логики (булева функция, ФАЛ) – f(x1,x2, …,xn) – это функция, у которой все аргументы есть логические переменные, и сама функция принимает только логические значения.
Например:
Построим всевозможные двоичные наборы длиной n = 3.
По теореме, приведенной выше, их количество равно 2n = 23 = 8.
|
Номер двоичного набора |
Двоичный набор |
||
|
х1 |
х2 |
х3 |
|
|
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
|
2 |
0 |
1 |
0 |
|
3 |
0 |
1 |
1 |
|
4 |
1 |
0 |
0 |
|
5 |
1 |
0 |
1 |
|
6 |
1 |
1 |
0 |
|
7 |
1 |
1 |
1 |
Существуют следующие способы описания ФАЛ
Табличный способ представления ФАЛ
Любую булеву функцию можно представить таблицей, имеющей 2n строк. Такая таблица называется таблицей истинности.
В левой части таблицы перечисляются всевозможные двоичные наборы значений аргументов, а в правой части – значения некоторой булевой функции.
|
№ |
x1 |
х2 |
… |
хn |
f (х1, х2,…,хn) |
|
0 |
0 |
0 |
… |
0 |
1 |
|
1 |
0 |
0 |
… |
1 |
2 |
|
… |
… |
… |
… |
… |
… |
|
2n-1 |
1 |
1 |
… |
1 |
2n |
Графическое представление ФАЛ
ФАЛ можно представить в виде n-мерного единичного куба: если наборам значений аргументов сопоставить точки n-мерного пространства, то множество 2n наборов определяет множество вершин n-мерного куба.
Одномерный куб (n = 1)
Функция принимает значения либо 0, либо 1.
F=0 – пустой кружёчек,
F=1 – закрашенный кружёчек.
Двумерный куб (n = 2)
Трехмерный куб (n = 3)
Таким же способом можно задать функцию от четырех переменных, в виде четырехмерного куба.
Четырехмерный куб (n = 4)
Количество функций от одного аргумента равно = 4.
Функции алгебры логики одного аргумента
|
х |
f0(x) |
f1(x) |
f2(x) |
f3(x) |
|
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
f0(х) 0 – константа 0 («ложь»)
f1(х) 1 – константа 1 («истина»)
f2(х) = х – переменная х
f3(х) = - отрицание х (инверсия х)
Количество различных ФАЛ от двух аргументов равно = 16.
Элементарные функции алгебры логики
|
х1х2 |
00 |
01 |
10 |
11 |
Обозначение ФАЛ |
|
f0 |
0 |
0 |
0 |
0 |
тождественный 0, const 0. |
|
f1 |
0 |
0 |
0 |
1 |
х1 и х2, х1х2, х1&х2, х1х2 – конъюнкция, логическое «и» |
|
f2 |
0 |
0 |
1 |
0 |
- запрет х2; х1, но не х2 |
|
f3 |
0 |
0 |
1 |
1 |
х1 повторение первого аргумента |
|
f4 |
0 |
1 |
0 |
0 |
- запрет х1; не х1, но х2 |
|
f5 |
0 |
1 |
0 |
1 |
х2 повторение второго аргумента |
|
f6 |
0 |
1 |
1 |
0 |
, - сложение по модулю 2, неравнозначность |
|
f7 |
0 |
1 |
1 |
1 |
х1х2 – дизъюнкция, сумма, логическое «или» |
|
f8 |
1 |
0 |
0 |
0 |
x1х2 – стрелка Пирса, функция Вебба, ; логическое “или-не” |
|
f9 |
1 |
0 |
0 |
1 |
x1х2 – эквивалентность, равнозначность, тождество |
|
f10 |
1 |
0 |
1 |
0 |
- отрицание, инверсия второго аргумента |
|
f11 |
1 |
0 |
1 |
1 |
x2х1 – обратная импликация |
|
f12 |
1 |
1 |
0 |
0 |
- отрицание первого аргумента |
|
f13 |
1 |
1 |
0 |
1 |
x1х2 – импликация |
|
f14 |
1 |
1 |
1 |
0 |
x1 | х2 – штрих Шеффера, логическое «и-не », |
|
f15 |
1 |
1 |
1 |
1 |
тождественная 1, константа 1 |
Условные приоритеты булевых функций
Каждая булева функция имеет свой приоритет при выполнении элементарных функций.
|
1. ( ) |
|
2. отрицание () |
|
3. & |
|
4. ≡ |
Замечание. В пределах одного приоритета операции в выражении выполняются слева направо.
Например:
Дана функция .
Составить таблицу истинности функции 3-х переменных: F (x, y, z).
Изобразить функцию графически.
Решение:
Расставим порядок выполнения действий, соблюдая приоритеты.
2
5 3 6 4 1
Выполним операции согласно порядку от 1 до 6.
Таблица истинности функции F(x, y, z)
|
x |
y |
z |
1 |
2 |
3 |
4 |
5 |
F(x,y,z) |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Изобразим функцию на кубе:
.
|
Законы булевой алгебры |
|
|
Коммутативность Ассоциативность Дистрибутивность Идемпотентность Закон отрицания отрицания Закон исключающего третьего Закон противоречия |
Свойства констант Законы де Моргана Законы поглощения Правила склеивания Обобщенное склеивание Правило вычеркивания |
|
Свойства , , |
|
|
Свойства импликации
Свойства |
Свойства функций Шеффера и стрелки Пирса
Функции и связаны соотношениями аналогичными формулам де Моргана |
Выражение одних элементарных функций через другие
Аналитическая запись ФАЛ
Рассмотрим методы перехода от табличного способа задания функций к аналитическому методу (в виде формул).
Дизъюнктивная нормальная форма (ДНФ)
Элементарная конъюнкция – конъюнкция, в которой каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций.
Например:
Используя законы алгебры логики преобразовать по шагам функцию F(x,y,z) в ДНФ. Для полученного результата составить таблицу истинности.
Решение:
Выполним преобразования по шагам:
Составим таблицу истинности для полученного результата:
|
x |
y |
z |
|||||||
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Последний столбец этой таблицы совпадает со столбцом задания функции F(x,y,z), следовательно, перевод в ДНФ верен.
Дизъюнктивная совершенная нормальная форма (ДСНФ)
Любая таблично заданная ФАЛ f(x1, x2, …, xn) (кроме тождественного нуля) может быть представлена в следующем аналитическом виде:
Представление ФАЛ в таком виде называется дизъюнктивной совершенной нормальной формой этой функции (ДСНФ).
Алгоритм перехода от табличного задания функции к ДСНФ
Конъюнктивная совершенная нормальная форма
Любая таблично заданная ФАЛ f(x1, x2, …, xn) (кроме тождественной единицы) может быть представлена в следующем аналитическом виде:
Представление ФАЛ в таком виде называется конъюнктивной совершенной нормальной формой этой функции (КСНФ).
Алгоритм построения конъюнктивной
совершенной нормальной формы
3. Полученные дизъюнкции соединить операцией конъюнкция.
Например:
Построить ДСНФ и КСНФ для функции F(x,y,z).
Решение:
Для нахождения ДСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в единицу. Это вторая, третья и пятая строки. Выпишем конъюнкции, соответствующие выбранным строкам:
.
Соединяя эти конъюнкции знаками дизъюнкции, получаем:
.
Для нахождения КСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в ноль. Выпишем соответствующие дизъюнкции и соединим их знаками конъюнкции.
Получим: .
Полные системы ФАЛ
Система ФАЛ {f1, f2,…, fn} называется полной в некотором классе функций, если любая функция из этого класса может быть представлена суперпозицией этих функций.
Система ФАЛ, являющаяся полной в некотором классе функций, называется базисом.
Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций fi, которые его образуют, превращает эту систему функций в неполную.
Любая функция может быть представлена с помощью элементарных функций {¬, &, }. Эта система ФАЛ образует универсальный базис.
Наиболее популярными в алгебре логики являются базисы{,¬},{&,¬}, {},{|}, которые являются минимальными.
Например:
Представить функцию в базисах
{, }, {|}. Для проверки результата составить таблицу истинности.
Решение:
Для перевода в базис {, } применим закон де Моргана к ДСНФ функции: .
Для перевода функции в базис {|} применим следующие соотношения к ДСНФ функции:
Обозначим
Выполним перевод в базис {|} по действиям.
Проверим преобразования с использованием таблицы истинности:
2 1 3 5 4 6
Таблица истинности для выражения :
|
№ |
x |
y |
z |
y | y |
x | (y | y) |
3 |
z | z |
5 |
6 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
2 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
3 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
4 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
5 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
6 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
7 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
Аналогично, проверяем и .
Для проверки, построим таблицу истинности для полученной формы функции F(x, y, z).
Таблица истинности для F(x,y,z)
|
№ |
x |
y |
z |
A |
B |
C |
A | B |
|||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
2 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
4 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
5 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
6 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
7 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
Cтолбцы, соответствующие функции F(x, y, z) в таблицах истинности равны, следовательно, преобразования выполнены правильно.
Задание к лабораторной работе
|
|
|
Контрольные вопросы
1. Определение двоичного набора.
2. Определение булевой функции или функции алгебры логики (ФАЛ).
3. Область определения и область значений ФАЛ.
4. ФАЛ от одной переменной.
5. Элементарные ФАЛ от двух переменных.
6. Основные законы алгебры логики.
7. Полные системы функций, минимальный базис.
8. Аналитическое описание ФАЛ: дизъюнктивная и конъюнктивная нормальные формы.
Лабораторная работа № 4
Методы минимизации функций алгебры логики.
Цель работы: получение практических навыков минимизации функций алгебры логики в классе ДНФ, изучение особенностей минимизации не полностью определенных функций.
Теоретическая справка
Основные определения
Буква - переменная или ее отрицание.
Элементарная конъюнкция – конъюнкция, в которой каждая буква встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций.
Ранг элементарной конъюнкции – количество переменных, которые ее образуют.
Дизъюнктивная совершенная нормальная форма (ДСНФ) – ДНФ, состоящая из конъюнкций ранга n, где n – количество переменных.
Длина ДНФ ( L ) – число конъюнкций, которые ее составляют.
Кратчайшая ДНФ – ДНФ, имеющая наименьшую длину L по сравнению с другими ДНФ, эквивалентными данной функции.
Суммарный ранг ДНФ(R) – сумма рангов конъюнкций ДНФ.
Минимальная ДНФ – ДНФ, имеющая наименьший суммарный ранг R по сравнению с другими ДНФ, эквивалентными данной функции.
Минимизация ФАЛ на кубе
Рассмотрим проблему минимизации для геометрического способа задания ФАЛ на кубе.
Сопоставим различным геометрическим элементам куба (вершинам, ребрам, граням и кубу) конъюнкции различных рангов. Сумма размерности геометри-ческого эквивалента и ранга конъюнкции, ему соответствующей равна числу аргументов ФАЛ.
Каждый геометрический элемент меньшей размерности покрывается геометрическими элементами большей размерности.
Каждая конъюнкция большего ранга покрывается всеми конъюнкциями меньшего ранга.
Геометрические эквиваленты называют интервалами.
Интервал L-го ранга – подмножество вершин куба, соответствующих конъюнкции ранга L.
Например:
Конъюнкции x соответствует 4 вершины: 100, 101, 110, 111.
На кубе отмечают вершины, где ФАЛ равна 1. Эти вершины образуют подмножество Т1. Для того, чтобы задать ДНФ на кубе, необходимо задать покрытие всех вершин.
Максимальный интервал J – интервал, для которого не существует никакого другого интервала J’ с рангом меньше, чем у J, и такого, что выполняется следующее соотношение .
Например:
Пусть есть функция, которая равна 1 в отмеченных точках.
Сокращенная ДНФ (СДНФ) – ДНФ, которая соответствует покрытию множества Т1 всеми максимальными интервалами.
Минимальная ДНФ получается из СДНФ путем выбрасывания из покрытия множества Т1 максимальными интервалами некоторых “лишних” интервалов.
Метод Квайна минимизации булевых функций
Предположим, что функция задана в ДСНФ.
Элементарные конъюнкции ранга n будем называть минитермами ранга n.
Шаг 1. Нахождение первичных импликант.
Все минитермы данной ФАЛ сравниваются между собой попарно.
Если минитермы mi и mj таковы, что их можно попарно представить в виде , то выписывается конъюнкция, которая является минитермом ранга n-1: .
Минитермы n-го ранга, для которых произошло склеивание отмечаются (*).
После построения всех минитермов (n-1)-го ранга вновь сравнивают их попарно, выписывают минитермы (n-2)-го ранга и отмечают склеивающиеся минитермы и т.д.
Этап заканчивается, когда вновь полученные минитермы l-го ранга уже не склеиваются между собой.
Все неотмеченные минитермы называются первичными или простыми импликантами.
Шаг 2. Расстановка меток.
Для данной функции
, где - первичные импликанты. (1)
Соотношение (1) определяет СДНФ для данной функции.
Для нахождения минимального покрытия интервалами максимального ранга необходимо произвести выбрасывание некоторого количества первичных импликант.
На этапе расстановки меток составляется таблица, число строк в которой равно числу первичных импликант, число столбцов равно числу минитермов ДСНФ.
Если в минитерм ДСНФ входит какой-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставим метку.
Шаг 3. Нахождение существенных импликант.
Если в столбце стоит всего одна метка, то соответствующая импликанта – существенная.
Существенная импликанта не может быть исключена из правой части (1), т.к. без нее не будет получено покрытие всего множества данной функции. Поэтому из таблицы меток исключаем строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых ими.
Шаг 4. Вычеркивание лишних столбцов.
Если в таблице есть два столбца с метками в одинаковых строках, то один из них вычеркивается (так как покрытие одного обеспечивает и покрытие другого).
Шаг 5. Вычеркивание лишних первичных импликант.
Если после этапа 4 в таблице есть строки без единой метки, то они вычеркиваются.
Шаг 6. Выбор минимального покрытия максимальными интервалами.
Исследуется полученная таблица: выбирается такая совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере по 1 в каждом столбце).
При нескольких вариантах отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах.
Метод Мак-Класки минимизации булевых функций
Метод Мак-Класки - модификация первого этапа метода Квайна.
Шаг 1. Всем минитермам ставим в соответствие их двоичный эквивалент.
Шаг 2. Все номера-минитермы разбиваем на группы по числу единиц в этих номерах.
Шаг 3. Все минитермы сравниваются между собой попарно.
Попарное сравнение можно производить только между соседними группами, т.к. только эти группы отличаются для входящих в них минитермов в одном разряде.
Шаг 4. Преобразование новых минитермов:
В разрядах, соответствующих исключенным переменным, ставим черточку. Такая модификация удобна еще и отсутствием громоздкой записи.
Шаг 5. Строим таблицу и расставляем метки, как и в методе Квайна (п.2).
Шаг 6. Далее минимизация проводится по таблице как и в методе Квайна (п.3-6).
Например:
Задана функция f(x1,x2,x3,x4,), которая равна единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15.
Минимизировать ее методом Квайна - Мак-Класки.
Решение:
|
№ набора |
Наборы |
f (x 1,x 2,x 3,x4) |
|
0 |
0000 |
1 |
|
1 |
0001 |
1 |
|
2 |
0010 |
1 |
|
3 |
0011 |
1 |
|
4 |
0100 |
1 |
|
5 |
0101 |
0 |
|
6 |
0110 |
1 |
|
7 |
0111 |
1 |
|
8 |
1000 |
1 |
|
9 |
1001 |
1 |
|
10 |
1010 |
0 |
|
11 |
1011 |
1 |
|
12 |
1100 |
0 |
|
13 |
1101 |
0 |
|
14 |
1110 |
0 |
|
15 |
1111 |
1 |
0000* ------------------------------ – нулевая группа
0001*, 0010*, 0100*, 1000* --- – первая группа
0011*, 0110*, 1001* ------------ – вторая группа
0111*, 1011* --------------------- – третья группа
1111* ------------------------------ – четвертая группа
000_*, 00_0*, 0_00*, _000* ----------------- – нулевая группа
00_1*, _001*, 001_*, 0_10*, 01_0*, 100_* – первая группа
0_11*, _011*, 011*_, 10_1* ----------------- – вторая группа
_111*, 1_11* ----------------------------------- – третья группа
00_ _, _00_, 0__0 ---------------- – нулевая группа
_0_1, 0_1_ ------------------------ – первая группа
_ _11 ------------------------------- – вторая группа
|
0000 |
0001 |
0010 |
0011 |
0100 |
0110 |
0111 |
1000 |
1001 |
1011 |
1111 |
|
|
00_ _ |
|
|
|
|
|||||||
|
_00_ |
|
|
|
|
|||||||
|
0_ _0 |
|
|
|
|
|||||||
|
_0_1 |
|
|
|
|
|||||||
|
0_1_ |
|
|
|
|
|||||||
|
_ _11 |
|
|
|
|
Вычеркиваем столбцы, соответствующие существенным импликантам и отметим (●) столбцы минитермов, покрываемых ими.
|
1 |
2 |
3 |
|||||||||
|
●1 |
●2 |
●1 |
●3 |
●1 |
●1 |
●3 |
●2 |
●2 |
●3 |
●3 |
|
|
0000 |
0001 |
0010 |
0011 |
0100 |
0110 |
0111 |
1000 |
1001 |
1011 |
1111 |
|
|
00__ |
|
|
|
|
|||||||
|
_00_ |
|
|
|
|
|||||||
|
0__0 |
|
|
|
|
|||||||
|
_0_1 |
|
|
|
|
|||||||
|
0_1_ |
|
|
|
|
|||||||
|
__11 |
|
|
|
|
В результате получаем
Графический метод минимизации: карты Карно и диаграммы Вейча
Карты Карно – графический метод отображения булевых функций.
Это специальные таблицы, задающие ФАЛ. Они сформированы так, чтобы облегчить процесс склеивания. Карты Карно используются при n=2,3,4,5,6, при n>6 они практически непригодны.
Диаграммы Вейча принципиально не отличаются от карт Карно. Различие состоит лишь в порядке следования наборов значений и в обозначениях (Карно – {0,1}; Вейча – {}).
Основные принципы построения карт Карно
Например:
карты Карно диаграммы Вейча
Для построения используют две карты Карно четырех переменных.
Например:
Минимизировать на картах Карно функцию f(x1,x2,x3,x4), которая равна единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15 (предыдущий пример).
Построим двоичные наборы, на которых задана функция.
|
№ набора |
Наборы |
f (x 1, x 2, x 3, x4) |
|
0 |
0000 |
1 |
|
1 |
0001 |
1 |
|
2 |
0010 |
1 |
|
3 |
0011 |
1 |
|
4 |
0100 |
1 |
|
6 |
0110 |
1 |
|
7 |
0111 |
1 |
|
8 |
1000 |
1 |
|
9 |
1001 |
1 |
|
11 |
1011 |
1 |
|
15 |
1111 |
1 |
Построим Карты Карно для заданной функции.
|
00 |
01 |
11 |
10 |
|
|
00 |
1 |
1 |
1 |
1 |
|
01 |
1 |
1 |
1 |
|
|
11 |
1 |
|||
|
10 |
1 |
1 |
1 |
Таким образом,
Задание к лабораторной работе
Алгоритм генерации варианта
Контрольные вопросы
1.Определение логической переменной и буквы.
2.Определение элементарной конъюнкции.
3.Нормальная и совершенная дизъюнктивные формы.
4.Ранг конъюнкции. Длина ДНФ.
5.Кратчайшая и минимальная ДНФ.
6.Сокращенная ДНФ.
7.Максимальные интервалы.
8.Карты Карно и диаграммы Вейча.
9.Метод Квайна: минитермы, импликанты(простые и существенные).
ЛИТЕРАТУРА
Кук Д., Бейз Г. Компьютерная математика . – М.: Наука, 1990.
Столл Р. Множества.Логика.Аксиоматические теории. – М.: Просвещение, 1968.
Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: Энергия,1974. – 268с.
Шоломов Л.А. Основы теории дискретных логических вычислительных устройств. – М.: Наука,1980.
Андерсон Дж. Дискретная математика и комбинаторика.– М.: Мир, 2001. – 960с.
Міхайленко В.М., Федоренко Н.Д., Демченко В.В. Дискретна математика: Підручник. – Київ: Вид-во Європ. ун-ту, 2003. – 318с.
СОДЕРЖАНИЕ
Лабораторная работа № 1
Способы задания множеств. Операции над множествами.
Основные соотношения алгебры множеств………………………..................2
Лабораторная работа № 2
Отношения на множествах………… …………………………………….…..8
Лабораторная работа № 3
Булевы функции. Законы алгебры логики. Аналитические способы описания. Полные системы функций………………………………………..17
Лабораторная работа № 4
Методы минимизации функций алгебры логики …………………………...32