Типовой расчёт. вар 63
.docРахмуков Владимир ВСС 1-97 МИРЭА 2000г.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Типовой расчёт
по предмету
« Основы дискретной математики »
студента группы ВСС 1-97
Рахмукова Владимира
Москва, 2000 г.
Вариант 63
Задача 1
Проверить полноту системы функций ={ fi ; gj }, найти Dmin для функций fi , gj. Представить формулами над и функциональными схемами над функции 0,1,,&,,hk.
63 = (2100)3
-
Проверяем полноту системы функций .
|
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 |
Определение линейности функции.
Найдём многочлен Жегалкина для функций и :
В многочлене Жегалкина конъюнкций переменных нет, следовательно, функция линейная.
В многочлене Жегалкина есть конъюнкции переменных, поэтому функция нелинейная.
Система функций целиком не входит ни в один из 5 замкнутых классов , таким образом, критерий полноты системы функций (Теорема Поста) выполняется (необходимость).
-
Достаточность.
Доказательством достаточности является построение из функции системы основных элементарных булевых функций.
-
Берём функцию, не принадлежащую классу , т.е. функцию и получаем:
– отрицание
Воспользуемся Леммой 1, и из функции , используя , получим одну из констант. Найдём взаимно противоположные пары наборов, на которых значение функции одно и тоже. Например, наборы . Выбираем любой из них.
, получаем константу 1.
Взяв её отрицание, получим константу 0:
Константу 0 можно также получить и следующим образом:
Берём, так как , следовательно
-
По Лемме 3 из функции можно получить конъюнкцию или дизъюнкцию.
Чтобы сохранить конъюнкцию , подставим вместо константу 1.
теперь вместо . получаем конъюнкцию xy =
Дизъюнкцию xy получим по закону двойственности
Формула над для функции .
-
x1
x2
h0
0
0
0
0
1
1
1
0
0
1
1
0
Функциональные схемы над функций .
Определение Dмин для функций f0, g1 .
-
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 нет.
-
Интервалы ранга 2:
-
Интервалов ранга 3 нет.
-
, , ранг
-
Для функции .
-
Интервалов ранга 1 нет.
-
Интервалы ранга 2:
-
Интервалов ранга 3 нет.
-
, , ранг
Задача 2
Найти Dсокр, Dя, все Dmin для f ( x1, x2, x3, x4 ) методом Карно и Квайна.
63= ( 0011 1111 )2
Метод Карно
-
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
Dmin=D1туп=D2туп
Метод Квайна.
-
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 |
|
|
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 |
Dmin=D1=D2
Задача 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