Типовой расчёт. вар 63. Московский государственный институт радиотехники, электроники и автоматики

• Название: Московский государственный институт радиотехники, электроники и автоматики
• Анкор: Типовой расчёт. вар 63.doc
• Дата: 05.11.2017
• Размер: 428.5 Kb.
• Имя файла: Типовой расчёт. вар 63.doc
• Тип: Задача; #10144
• Категория: Математика

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Типовой расчёт

по предмету

« Основы дискретной математики »

студента группы ВСС 1-97

Рахмукова Владимира

Москва, 2000 г.

Вариант 63
Задача 1

Проверить полноту системы функций ={ f_i ; g_j }, найти D_min для функций f_i , g_j. Представить формулами над  и функциональными схемами над  функции 0,1,,&,,h_k.
63 = (2100)₃

1. 
   Проверяем полноту системы функций .
   

	T0	T1	S	M	L			x1	x2	x3	f0	g1
f0	+	-	-	-	+			0	0	0	0	1
g1	-	-	+	-	-			0	0	1	1	1
								0	1	0	0	1
								0	1	1	1	0
								1	0	0	1	1
								1	0	1	0	0
								1	1	0	1	0
								1	1	1	0	0

Определение линейности функции.
Найдём многочлен Жегалкина для функций и :

1. 
   
   

В многочлене Жегалкина конъюнкций переменных нет, следовательно, функция линейная.

2. 
   
   

В многочлене Жегалкина есть конъюнкции переменных, поэтому функция нелинейная.

Система функций целиком не входит ни в один из 5 замкнутых классов , таким образом, критерий полноты системы функций (Теорема Поста) выполняется (необходимость).

2. 
   Достаточность.
   

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

1. 
   Берём функцию, не принадлежащую классу , т.е. функцию и получаем:
   

– отрицание
Воспользуемся Леммой 1, и из функции , используя , получим одну из констант. Найдём взаимно противоположные пары наборов, на которых значение функции одно и тоже. Например, наборы . Выбираем любой из них.

, получаем константу 1.

Взяв её отрицание, получим константу 0:

Константу 0 можно также получить и следующим образом:
Берём, так как , следовательно

2. 
   По Лемме 3 из функции можно получить конъюнкцию или дизъюнкцию.
   

Чтобы сохранить конъюнкцию , подставим вместо константу 1.



теперь вместо . получаем конъюнкцию xy =

Дизъюнкцию xy получим по закону двойственности


Формула над для функции .

x1	x2	h0
0	0	0
0	1	1
1	0	0
1	1	0

Функциональные схемы над функций .



Определение D_мин для функций f₀, g₁ .

x1	x2	x3	f0	g1
0	0	0	0	1
0	0	1	1	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	0
1	1	1	0	0

1. 
   Для функции .
   

• 
  Интервалов ранга 1 нет.
  
• 
  Интервалы ранга 2:
  

• 
  Интервалов ранга 3 нет.
  
• 
  
  
• 
  , , ранг
  

2. 
   Для функции .
   

• 
  Интервалов ранга 1 нет.
  
• 
  Интервалы ранга 2:
  

• 
  Интервалов ранга 3 нет.
  
• 
  
  
• 
  , , ранг
  

Задача 2

Найти D_сокр, D_я, все D_min для f ( x₁, x₂, x₃, x₄ ) методом Карно и Квайна.




63= ( 0011 1111 )₂



Метод Карно

	00	01	11	10
00		1	1
01	1	1
11	1
10		1	1	1

	00	01	11	10
00		1	1
01	1	1
11	1
10		1	1	1

	00	01	11	10
00		1	1
01	1	1
11	1
10		1	1	1

D_min=D_1туп=D_2туп

Метод Квайна.

x3x4 x1x2	00	01	11	10
00		1	1
01	1	1
11	1
10		1	1	1

k1	0001	*	00-1	*	-0-1	1
k2	0100	*	0-01	5	-0-1
k3	0011	*	-001	*
k4	0101	*	010-	4
k5	1100	*	-100	3
k6	1001	*	-011	*
k7	1010	*	10-1	*
k8	1011	*	101-	2

	k1	k2	k3	k4	k5	k6	k7	k8
1	X		X			X		X
2							X	X
3		X			X
4		X		X
5	X			X

	k4
4	X
5	X

D_min=D₁=D₂

Задача 3

Построить минимальную функциональную схему для функции f из задачи 2 на элементах {,&,}.






Задача 4

Построить минимальную контактную схему для той же функции.





Задача 5

Решить задачу об оптимальном назначении с матрицей эффективности В.

ai\bi	0	0	0	0
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4

ai\bi	0	0	0	0
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4

ai\bi	0	0	0	0
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4

ai\bi	0	0	0	0
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4
4	1	2	3	4

Задача 6

Найти максимальный поток в транспортной сети. Пропускная способность рёбер определяется элементами матрицы В из задачи 5.


1 (1)

1 (1)

3 (1)

2 (0)

4 (0)

2 (0)

3 (0)

2 (2)

4 (2)

1 (0)

2 (0)

3 (3)

4 (3)

1 (0)

1 (0)

b

a

G


|
4 (3)
