Дискретная математика

1. Построить диаграмму Венна.
2. Найдите минимальные ДНФ и КНФ булевых функций, зависящих от аргументов А, В, С, D
3.Найдите минимальные ДНФ булевых функций, зависящих от аргументов
4. Найдите СДНФ и минимальные ДНФ и КНФ
5.Найти производную по переменной D
6. Построить преобразователь четырехзначного двоичного весового кода Р в пятизначный весовой код Q
7. Построить автомат на JK-триггерах, реализующих две последовательности
8. 9-значное двоичное число разделили на две части a и b так, что в каждой части не менее четырех знаков. Сколько всего существует 9-значных чисел, для которых выполняется условие a=b
9. Найдите все простые цепи, соединяющие вершины 1 и 6 графа ...

-

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Функция принимает 0 на трёх наборах: 0011, 1001 и 1100, а 1 – на остальных тринадцати, поэтому для удобства вычислений запишем КНФ нашей функции:
f = (A v B v v )( v B v C v )( v v C v D)
По определению:
= (A v B v v 1)( v B v C v 1)( v v C v 0) = 11( v v C) = v v C
= (A v B v v 0)( v B v C v 0)( v v C v 1) = (A v B v )( v B v C) 1 = (A v B v )( v B v C)
Тогда:
( v v C) (A v B v )( v B v C)
A
B
C
v v C
A v B v
v B v C
(A v B v )( v B v C)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
= (01001010) или =(1, 4, 6)
7) Построить преобразователь четырехзначного двоичного весового кода Р в пятизначный весовой код Q:
P=2412, Q=21411
Решение:
а) По условию, у нас 4х-значный двоичный код, т.е. возможны 24=16 состояний. Запишем их вместе с их записью в соответствующих кодах в таблице истинности:
Число в 10 системе счисления
P = 2412
Q = 21411
A B C D
f1 f2 f3 f4 f5
0 0 0 0
0 0 0 0 0
1
1
0 0 1 0
0 0 0 0 1
2
1
0 0 0 1
1 0 0 0 0
3
1
1
0 0 1 1
1 0 0 0 1
4
1
0 1 0 0
0 0 1 0 0
5
1
1
0 1 1 0
0 0 1 0 1
6
1
1
0 1 0 1
1 0 1 0 0
7
1
1
1
0 1 1 1
1 0 1 0 1
8
1
1 1 0 1
1 0 1 1 1
9
1
1
1 1 1 1
1 1 1 1 1
10
1
1
x
x
11
1
1
1
x
x
12
1
1
x
x
13
1
1
1
x
x
14
1
1
1
x
x
15
1
1
1
1
x
x
Далее, при желании, с помощью карт Карно можно получить для каждого Qi, i = 0;4 его выражение в виде функции от Pj, j=0;3.
б) Представим каждую булеву функцию в СДНФ.
f1:
f2:
f3:
f4:
f5:
в) Запишем минимальные ДНФ и КНФ для всех булевых функций;
Изобразим карты Вейча для прямых и инверсных форм каждой из пяти функций – всего 10 карт.
f1=
х
1
х
х
х
1
х
х
1
1
1
1
Минимальная ДНФ согласно этой карте имеет вид:
Минимальная КНФ согласно этой карте имеет вид:
f2=
х
х
х
х
1
х
х
Минимальная ДНФ согласно этой карте имеет вид:
Минимальная КНФ согласно этой карте имеет вид:
f3=
х
1
х
х
х
1
х
х
1
1
1
1
Минимальная ДНФ согласно этой карте имеет вид:
Минимальная КНФ согласно этой карте имеет вид:
f4=
х
1
х
х
х
1
х
х
Минимальная ДНФ согласно этой карте имеет вид:
Минимальная КНФ согласно этой карте имеет вид:
f5=
х
1
х
х
х
1
х
х
1
1
1
1
Минимальная ДНФ согласно этой карте имеет вид:
Минимальная КНФ согласно этой карте имеет вид:
г) Запишем список пяти булевых функций, выбранных для построения логической схемы преобразователя и содержащих наименьшее число вхождений переменных.
д) Логическая схема преобразователя:
8) Построить автомат на JK-триггерах, реализующих две последовательности:
Если А = 0, то 2, 4, 6, 0, 1, 7, 5, 3.
Если А = 1, то 4, 0, 6, 7, 2, 1, 5, 3.
Решение:
Очевидно, что для построения схемы необходимо четыре триггера: один триггер, обозначенный в условии буквой А, используется для переключения направления счета, а для реализации самого счета требуется еще три триггера. Обозначим их буквами B, C, D и составим таблицу переходов, в которой отразим все случаи перехода автомата из одного состояния в другое.
В левой части таблицы, где приведены колонки А, В, С, D, записаны состояния автомата: когда А = 0 выполняется последовательность (2,4,6,0,1,7,5,3), когда же А = 1, то (4,0,6,7,2,1,5,3) В левой колонке, обозначенной «Дес.сс», указаны десятичные эквиваленты трёхзначных двоичных чисел, записанных в строках таблицы (ВСD).
Правая часть табл. состоит из колонок: JB, KB, Jс, Kс, Jd, Kd. Это выходы комбинационной схемы, управляющей триггерами В, С, D.
Т. к. триггер А устанавливается в единичное или нулевое состояние извне, поэтому в правой части табл. колонки JА и KА отсутствуют.
Изобразим таблицу переходов:
Дес.с/с
A
B
C
D
JB
KB
Jс
Kс
Jd
Kd
2
1
1
х
x
1
x
4
1
x
1
x
x
6
1
1
x
1
x
1
x
x
x
1
x
1
1
1
x
1
x
x
7
1
1
1
x
x
1
x
5
1
1
x
1
1
x
x
3
1
1
x
x
x
1
12
1
1
x
1
x
x
8
1
1
x
1
x
x
14
1
1
1
x
x
1
x
15
1
1
1
1
x
1
x
x
1
10
1
1
x
x
1
1
x
9
1
1
1