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 языка. Тогда можно простроить систему уравнений:

n(А∩В∩С) = x = 0;

n(А∩В) + n(А∩С) + n(В∩С) – 3n(А∩В∩С) = 5+4+3 – 3*0 = 12;

Ответ: 0;12.

2.5

Получить СДНФ, СКНФ, используя таблицу истинности. Построить ДНФ, КНФ, упростив выражение.

P	Q	S		PQ	Q  P		P  Q		)	X
0	0	0	1	1	0	0	0	0	0	0
0	0	1	0	1	0	1	0	0	0	0
0	1	0	1	0	1	0	1	0	0	0
0	1	1	0	0	1	1	1	0	1	1
1	0	0	1	0	1	1	1	0	1	1
1	0	1	0	0	1	0	1	0	0	0
1	1	0	1	1	0	1	0	0	0	0
1	1	1	0	1	0	0	0	0	0	0

СДНФ =

_{СКНФ =}

3.5

Упростить схему

Построим выражение по схеме:

_{Упростим:}

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

Построим СКНФ:

_{Результаты упрощений равны, что и требовалось доказать.}

_{Упрощённая схема:}

y

4.5

Выяснить, каким из пяти замкнутых классов принадлежит функция, заданная своим характеристическим множеством (или представленная в табличной форме). Построить полином Жегалкина.

Построим таблицу истинности:

x1 x2 x3	f
0 0 0	1
0 0 1	1
0 1 0	0
0 1 1	1
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	1

, т.к. на противоположных наборах аргументов функция даёт равные значения

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

Найти методом Квайна-МакКласски минимальную ДНФ функции, заданной своим характеристическим множеством М₁ ={0000, 0001, 1100, 1001, 1110, 1101, 1111}

x1	x1		x1		x1		M
0	0		0		0		1
0	0		0		1		0
0	0		1		0		0
0	0		1		1		0
0	1		0		0		0
0	1		0		1		1
0	1		1		0		0
0	1		1		1		0
1	0	0		0		1
1	0	0		1		1
1	0	1		0		0
1	0	1		1		1
1	1	0		0		0
1	1	0		1		1
1	1	1		0		1
1	1	1		1		1

0	0000	*000
1	1000	-001
2	1010 1001	11-0* 110-* 1-01	1**1
3	1011 1101 1110	111-* 11-1*
4	1111

Наборы не участвующие в склейке: *000, 100*, *101, 1**1, 111*

		0000	1001	1000	0101	1101	1011	1111	1110
p1	*000	1		1
p2	100*		1	1
р3	*101				1	1
р4	1**1		1			1	1	1
Р5	111*							1	1
vpi		p1	p2v p4	P1 v p2	p3	p3 v p4	p4	p4 v p5		p5

ДНФ_min = p₁ v p₃ v p₄ v p₅

ДНФ_min =

6.5

Найти инварианты неориентированного графа, заданного матрицей смежности

	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

Решение:

Согласно отношениям смежности, изобразим граф G:

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)

Мощность наименьшего вершинного покрытия называется числом вершинного покрытия графа.

Построим матрицу инцидентности графа G:

	x1x2	x1x4	x1x5	x2x3	x2x5	x3x4	x3x5	x3x6	x4x5	x4x6	x5x6
x1	1	1	1	0	0	0	0	0	0	0	0
x2	1	0	0	1	1	0	0	0	0	0	0
x3	0	0	0	1	0	1	1	1	0	0	0
x4	0	1	0	0	0	1	0	0	1	1	0
x5	0	0	1	0	1	0	1	0	1	0	1
x6	0	0	0	0	0	0	0	1	0	1	1

Проход алгоритма №1

В искомое множество добавлена вершина x1

	x2x3	x2x5	x3x4	x3x5	x3x6	x4x5	x4x6	x5x6
x2	1	1	0	0	0	0	0	0
x3	1	0	1	1	1	0	0	0
x4	0	0	1	0	0	1	1	0
x5	0	1	0	1	0	1	0	1
x6	0	0	0	0	1	0	1	1

Проход алгоритма №2

В искомое множество добавлена вершина x3

	x2x5	x4x5	x4x6	x5x6
x2	1	0	0	0
x4	0	1	1	0
x5	1	1	0	1
x6	0	0	1	1

Проход алгоритма №3

В искомое множество добавлена вершина x5

	x4x6
x4	1
x6	1

Проход алгоритма №4

В искомое множество добавлена вершина x4

Искомое множество вершинного покрытия включает в себя вершины: x1, x3, x5, x4.

Отсюда число вершинного покрытия равно 4.