Типовой расчет (1023549)
Текст из файла
Рахмуков Владимир ВСС 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 ) методом Карно и Квайна.
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 | ||
|
| 1 | 1 | ||
| 11 | 1 | |||
| 10 | 1 | 1 | 1 |
|
| 00 | 01 | 11 | 10 |
| 00 | 1 | 1 | ||
|
| 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 |
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
