Дискретка(исходные данные типового расчета 2семестр)
.pdfДИСКРЕТНАЯ МАТЕМАТИКА
(2-й курс, 4-й семестр) (2012/2013 учебный год)
ТИПОВОЙ РАСЧЕТ
ЗАДАЧА 1. Функциональная полнота системы булевых функций. Булевы функции f 2 3F , g 2 3F , h 2 2F заданы своими векторами значений:
f = (1001 1001); g = (1110 1000); h = (0100):
1)С помощью метода Карно найти Dсов(f), Dсокр(f), Dядр(f), Dб(f) и Dmin(f). Указать ранг каждой ДНФ.
2)С помощью метода Карно найти Dсов(g), Dсокр(g), Dядр(g), Dб(g) и Dmin(g). Указать ранг каждой ДНФ.
3)Составить критериальную таблицу Поста системы булевых функций Q = ff; gg.
4)Доказать, что система Q является функционально полной системой (ФПС). Определить, относится ли система Q к типу А или к типу Б.
5)Реализовать в виде формул и в виде схем из функциональных элементов (СФЭ) над системой Q следующие булевы функции: 0, 1, 6, ^, _, h (каждую функцию достаточно реализовать одним каким-либо способом). Для каждой формулы указать трудность t( ), сложность l( ) и глубину d( ). Для каждой схемы S указать сложность l(S) и глубину d(S).
ЗАДАЧА 2. Минимизация булевой функции в классе дизъюнктивных нормальных форм (ДНФ). Булева функция f 2 4F задана своим вектором значений:
f= (0011 0001 1010 1110):
1)С помощью метода Квайна Мак-Класки найти Dсокр(f), Dядр(f), Dб(f) и Dmin(f). Указать ранг каждой ДНФ.
2)С помощью метода Карно найти Dсокр(f), Dядр(f), Dб(f) и Dmin(f). Указать ранг каждой ДНФ. Сравнить полученный результат с результатом п. 1).
ЗАДАЧА 3. Реализация булевой функции в виде схемы из функциональ-
ных элементов (СФЭ). Булева функция f 2 4F задана своим вектором значений:
f= (0011 0001 1010 1110):
1)Реализовать функцию f в виде СФЭ S1 над булевой системой QB = f6, ^, _g. Указать сложность l(S1) и глубину d(S1) схемы S1.
2)Реализовать функцию f в виде СФЭ S2 над системой Жегалкина QZ = f1, ^, g. Указать сложность l(S2) и глубину d(S2) схемы S2.
ЗАДАЧА 4. Реализация булевой функции в виде контактной схемы (КС).
Булева функция f 2 4F задана своим вектором значений: f = (0011 0001 1010 1110):
Реализовать функцию f в виде КС K. Указать сложность l(K) схемы K.
ИСХОДНЫЕ ЧИСЛОВЫЕ ДАННЫЕ
Вариант 1 |
Задача 1 |
f = (0101 1010), |
g = (1110 1000), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0100 1011 1100 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 2 |
Задача 1 |
f = (0101 1010), |
g = (1110 1000), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 1011 1100 0100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 3 |
Задача 1 |
f = (0101 1010), |
g = (1011 0010), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 0100 1010 1011) |
|
||
|
|
|||
|
|
|
|
|
Вариант 4 |
Задача 1 |
f = (0101 1010), |
g = (1011 0010), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1011 0100 1010 1100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 5 |
Задача 1 |
f = (0101 1010), |
g = (1011 0010), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0100 1100 1011 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 6 |
Задача 1 |
f = (0101 1010), |
g = (1101 0100), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 1010 0100 1011) |
|
||
|
|
|||
|
|
|
|
|
Вариант 7 |
Задача 1 |
f = (0101 1010), |
g = (1101 0100), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 1100 1011 0100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 8 |
Задача 1 |
f = (0101 1010), |
g = (1101 0100), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1101 1100 0010 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 9 |
Задача 1 |
f = (0110 0110), |
g = (1110 1000), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0010 1101 1010 1100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 10 |
Задача 1 |
f = (0110 0110), |
g = (1110 1000), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 1101 1010 0010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 11 |
Задача 1 |
f = (0110 0110), |
g = (1110 1000), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 0010 1100 1101) |
|
||
|
|
|||
|
|
|
|
|
Вариант 12 |
Задача 1 |
f = (0110 0110), |
g = (1011 0010), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1101 0010 1100 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 13 |
Задача 1 |
f = (0110 0110), |
g = (1011 0010), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0010 1010 1101 1100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 14 |
Задача 1 |
f = (0110 0110), |
g = (1011 0010), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 1100 0010 1101) |
|
||
|
|
|||
|
|
|
|
|
Вариант 15 |
Задача 1 |
f = (0110 0110), |
g = (1101 0100), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 1010 1101 0010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 16 |
Задача 1 |
f = (0110 0110), |
g = (1101 0100), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1110 1010 0001 0011) |
|
||
|
|
|||
|
|
|
|
|
Вариант 17 |
Задача 1 |
f = (0110 0110), |
g = (1101 0100), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0001 1110 0011 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 18 |
Задача 1 |
f = (1001 1001), |
g = (1110 1000), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 1110 0011 0001) |
|
||
|
|
|||
|
|
|
|
|
Вариант 19 |
Задача 1 |
f = (1001 1001), |
g = (1110 1000), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0011 0001 1010 1110) |
|
||
|
|
|||
|
|
|
|
|
Вариант 20 |
Задача 1 |
f = (1001 1001), |
g = (1110 1000), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1110 0001 1010 0011) |
|
||
|
|
|||
|
|
|
|
|
Вариант 21 |
Задача 1 |
f = (1001 1001), |
g = (1011 0010), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0001 0011 1110 1010) |
|
||
|
|
|||
|
|
|
|
|
Вариант 22 |
Задача 1 |
f = (1001 1001), |
g = (1011 0010), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0011 1010 0001 1110) |
|
||
|
|
|||
|
|
|
|
|
Вариант 23 |
Задача 1 |
f = (1001 1001), |
g = (1011 0010), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1010 0011 1110 0001) |
|
||
|
|
|||
|
|
|
|
|
Вариант 24 |
Задача 1 |
f = (1001 1001), |
g = (1101 0100), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0111 0101 1000 1100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 25 |
Задача 1 |
f = (1001 1001), |
g = (1101 0100), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1000 0111 1100 0101) |
|
||
|
|
|||
|
|
|
|
|
Вариант 26 |
Задача 1 |
f = (1001 1001), |
g = (1101 0100), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0101 0111 1100 1000) |
|
||
|
|
|||
|
|
|
|
|
Вариант 27 |
Задача 1 |
f = (0101 1010), |
g = (1110 1000), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 1000 0101 0111) |
|
||
|
|
|||
|
|
|
|
|
Вариант 28 |
Задача 1 |
f = (0101 1010), |
g = (1110 1000), |
h = (0100) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (0111 1000 0101 1100) |
|
||
|
|
|||
|
|
|
|
|
Вариант 29 |
Задача 1 |
f = (0101 1010), |
g = (1110 1000), |
h = (0010) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1000 1100 0111 0101) |
|
||
|
|
|||
|
|
|
|
|
Вариант 30 |
Задача 1 |
f = (0101 1010), |
g = (1011 0010), |
h = (1000) |
|
|
|
|
|
Задачи 2, 3, 4 |
f = (1100 0101 1000 0111) |
|
||
|
|
|||
|
|
|
|
|
Замечание. Вариант 19 является демонстрационным вариантом.