Задания: 1.5 Используя диаграммы Эйлера-Венна, решить задачу. 2.5 Получить СДНФ, СКНФ, используя таблицу истинности. Построить ДНФ, КНФ, упростив выражение. 3.5 Упростить схему 4.5 Выяснить, каким из пяти замкнутых классов принадлежит функция, заданная своим характеристическим множеством (или представленная в табличной форме). Построить полином Жегалкина. 5.5 Найти методом Квайна-МакКласски минимальную ДНФ функции, заданной своим характеристическим множеством М1 ={0000, 0001, 1100, 1001, 1110, 1101, 1111}
1.5 Используя диаграммы Эйлера-Венна, решить задачу.
На кафедре иностранных языков работают 20 преподавателей, из них 12 преподают английский язык, 11 – немецкий, 9-французский; 5 преподавателей преподают английский и немецкий языки, 4 - английский и французский, 3 –немецкий и французский. Сколько преподавателей преподают все три языка? Только два языка?
Решение:
В качестве универсального выберем множество всех преподавателей. Число его элементов равно 20. Пусть А - множество преподавателей английского языка, В - немецкого, С - французского. Число элементов множества А обозначим n(A). Оно равно 12, т.е. n(A)=12. Аналогично, n(В)=11, n(С)=9. По условию задачи n(А∩В)=5, n(А∩С)=4 и n(В∩С)=3. Обратимся к диаграмме (рис. 1).
Рис. 1. Диаграмма Эйлера-Венна
Область 1 есть множество преподавателей, которые преподают все 3 языка, т.е. множество А∩В∩С. Пусть область 5 – преподаватели, преподающие только английский язык, обозначим как a; область 6 – только немецкий язык, обозначим b; область 7 – только французский язык, обозначим c. Пусть x – преподаватели, преподающие все 3 языка. Тогда можно простроить систему уравнений:
x y z f 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1
Построим СКНФ:
Результаты упрощений равны, что и требовалось доказать. Упрощённая схема:
4.5 Выяснить, каким из пяти замкнутых классов принадлежит функция, заданная своим характеристическим множеством (или представленная в табличной форме). Построить полином Жегалкина.
, т.к. на противоположных наборах аргументов функция даёт равные значения f(0,0,0) = f(1,1,1) , т.к. f(0,0,0) 0 , т.к. f(1,1,1) 1 , т.к. f(1,0,1) > f(1,0,0)
Построим полином Жегалкина: Строим СДНФ
Заменяем все v на , все на
, т.к. полученный полином Жегалкина – не линейный.
5.5 Найти методом Квайна-МакКласски минимальную ДНФ функции, заданной своим характеристическим множеством М1 ={0000, 0001, 1100, 1001, 1110, 1101, 1111}
1. Количество вершин n = 6 2. Количество ребер r = 11 3. Количество граней f = 7 n-r+f = 2 f = 2-n+r = 2-6+11 = 7 4. Число связности k = 1 5. Толщина графа t(G) = 1 Толщина графа равна 1, т.к. граф планарный. 6. Плотность графа q(G) = 4 Плотность графа это количество вершин в максимальной клике. Задача о поиске клики заданного размера NP-полна. Т.к. наш граф небольшого размера - воспользуемся полным перебором для поиска максимальной клики. Найденная максимальная клика содержит вершины x6, x5, x4, x3.
7. Число независимости α0(G) Число независимости графа это число вершин в его наибольшем независимом множестве. Проход алгоритма №1 x1 x2 x3 x4 x5 x6 x1 0 1 0 1 1 0 x2 1 0 1 0 1 0 x3 0 1 0 1 1 1 x4 1 0 1 0 1 1 x5 1 1 1 1 0 1 x6 0 0 1 1 1 0 В искомое множество добавлена вершина: x1.
Проход алгоритма №2 x3 x6 x3 0 1 x6 1 0 В искомое множество добавлена вершина: x3. Наибольшее независимое множество содержит вершины: x1, x3. А значит число независимости α0(G) = 2. 8. Найдем число вершинного покрытия β0(G) Мощность наименьшего вершинного покрытия называется числом вершинного покрытия графа.
Проход алгоритма №3 В искомое множество добавлена вершина x5 x4x6 x4 1 x6 1
Проход алгоритма №4 В искомое множество добавлена вершина x4
Искомое множество вершинного покрытия включает в себя вершины: x1, x3, x5, x4. Отсюда число вершинного покрытия равно 4. 9. Найдем число наибольшего паросочетания α1(G) Мощность наибольшего паросочетания называется числом паросочетания графа. Искомое множество включает следующие ребра: x1x2, x3x4, x5x6. А значит число наибольшего паросочетания α1(G) = 3 10. Число реберного покрытия β1(G) = 3 Согласно Лемме 2: α1(G) + β1(G) = n; β1(G) = n – α1(G) = 6 - 3 = 3. 11. Число доминирования μ(G) Доминирующее множество вершин - такое множество вершин графа, что каждая вершина графа либо принадлежит доминирующему множеству вершин, либо инцидентна некоторой вершине из него. Мощность наименьшего доминирующего множества называется числом доминирования графа.
