Типовой расчет (Типовой расчёт. вар 63)
Описание файла
Файл "Типовой расчет" внутри архива находится в папке "Типовой расчёт. вар 63". Документ из архива "Типовой расчёт. вар 63", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Типовой расчет"
Текст из документа "Типовой расчет"
Рахмуков Владимир ВСС 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, и из функции , используя , получим одну из констант. Найдём взаимно противоположные пары наборов, на которых значение функции одно и тоже. Например, наборы . Выбираем любой из них.
Взяв её отрицание, получим константу 0:
Константу 0 можно также получить и следующим образом:
Берём , так как , следовательно
Чтобы сохранить конъюнкцию , подставим вместо константу 1.
теперь вместо . получаем конъюнкцию xy =
Дизъюнкцию xy получим по закону двойственности
x1 | x2 | h0 |
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:
-
Интервалов ранга 1 нет.
-
Интервалы ранга 2:
Задача 2
Найти Dсокр, Dя, все Dmin для f ( x1, x2, x3, x4 ) методом Карно и Квайна.
6 3= ( 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 | -0-1 | |
k3 | 0011 | * | -001 | * | ||
k4 | 0101 | * | 010- | 4 | ||
k5 | 1100 | * | -100 | 3 | ||
k6 | 1001 | * | -011 | * | ||
k7 | 1010 | * | 10-1 | * | ||
k8 | 1011 | * | 101- | 2 |