Задание 10
Построить логическую схему на четыре
входа
и один выход y в
базисе НЕ – ИЛИ, причем выход y
равен 0 тогда и только тогда, когда два
или менее из ее входов равны 0.
Теоретическая часть:
Были использованы законы алгебры логики для простых и составных высказываний:
- логические утверждения, тогда:
; - идемпотентность
;
;
- закон противоречия
- закон исключения третьего
- закон двойного отрицания
; - законы де Моргана
; - коммутативность
; - ассоциативность
; - дистрибутивность
ДНФ (КНФ) – дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.
Практическая часть:
Построим таблицу истинности согласно заданию.
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Составим по таблице СДНФ и минимизируем её с помощью карт Карно:
-
1
1
1
1
1
Из карт Карно получаем минимизированную СДНФ:
Переведем эту формулу в базис НЕ – ИЛИ с помощью законов де Моргана:
Построим логическую схему для данной функции:
Задание 11
Для функции
,
представленной таблицей истинности,
найти минимальную ДНФ, используя методы
карт Карно и Квайна – Мак’Класки.
Теоретическая часть:
Были использованы законы алгебры логики для простых и составных высказываний:
- логические утверждения, тогда:
; - идемпотентность
;
;
- закон противоречия
- закон исключения третьего
- закон двойного отрицания
; - законы де Моргана
; - коммутативность
; - ассоциативность
; - дистрибутивность
ДНФ (КНФ) – дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.
Практическая часть:
1) Метод карт Карно:
Рисуем табличку согласно нашей функции
(в строках
,
,
в столбцах
,
):
-
1
1
1
1
1
1
1
1
Склеиваем единицы:
-
1
1
1
1
1
1
1
1
Получаем минитермы:
,
,
,
Больше не осталось единиц для склеивания, следовательно можно записать окончательный результат:
2) Метод Квайна – Мак’Класки:
Нарисуем таблицу.
В столбцах - минитермы исходной функции и соответствующие им двоичные наборы:
|
|
|
|
|
|
|
|
0111 |
0101 |
0001 |
1110 |
0110 |
1000 |
1001 |
1010 |
Разобьем минитермы на классы по числу входящих в них единиц:
0 – «-»
1 – 0001, 1000
2 – 0101, 0110, 1001, 1010
3 – 0111, 1110
4 – «-»
Попарно склеим минитермы, отметим минитермы участвующие в склеивании.
Получим минитермы ранга 3: 0_01, _001, 100_, 10_0, 01_1, 011_, _110, 1_10.
Аналогично разобьем эти минитермы на классы по числу входящих в них единиц:
0 – «-»
1 – 0_01, _001, 100_, 10_0
2 – 01_1, 011_, _110, 1_10
3 – «-»
4 – «-»
Очевидно, что данные минитермы более
склеить нельзя. Т. о. полученные первичные
импликанты можно записать, как:
,
,
,
,
,
,
,
.
Построим таблицу и расставим метки:
|
|
|
|
|
|
|
|
|
0111 |
0101 |
0001 |
1110 |
0110 |
1000 |
1001 |
1010 |
|
|
|
+ |
+ |
|
|
|
|
|
|
|
|
+ |
|
|
|
+ |
|
|
|
|
|
|
|
+ |
+ |
|
|
|
|
|
|
|
+ |
|
+ |
|
+ |
+ |
|
|
|
|
|
|
|
+ |
|
|
|
+ |
|
|
|
|
|
|
|
+ |
+ |
|
|
|
|
|
|
|
+ |
|
|
|
+ |
Очевидно, что существенных импликант среди полученных первичных нет, т. к. во всех столбцах стоит больше чем по одной метке.
Т. о. можно записать окончательный результат:
Как видно полученная функция совпадает с результатом применения метода карт Карно.