3.5. Построение логических схем на основе таблиц истинности

Нормальная форма логической функции — это ......................................................................... ................................................................................................................................................................ ................................................................................................................................................................ ................................................................................................................................................................

Элементарная конъюнкция — конъюнкция конечного множества логических переменных и их инверсий.

Элементарная дизъюнкция – дизъюнкция конечного множества логических переменных и их инверсий.

Ранг элементарной конъюнкции или дизъюнкции – число аргументов ее образующих.
Примеры:
Элементарная конъюнкция третьего порядка	Элементарная дизъюнкция второго порядка
Конъюнктивная нормальная форма (КНФ) содержит элементарные ...................... .............., связанные между собой операциями ...........................................	Дизъюнктивная нормальная форма (ДНФ) содержит элементарные ..................................., связанные между собой операциями ...............................................
Примеры:
Совершенная конъюнктивная нормальная форма (СКНФ): нет двух элементарных дизъюнкций; ни одна элементарная дизъюнкция не содержит двух одинаковых переменных; ни одна элементарная дизъюнкция не содержит переменную вместе с ее инверсией; все дизъюнкции имеют один и тот же ранг.	Совершенная дизъюнктивная нормальная форма (СДНФ): нет двух одинаковых элементарных конъюнкций; ни одна элементарная конъюнкция не содержит двух одинаковых переменных; ни одна элементарная конъюнкция не содержит переменную вместе с ее инверсией; все конъюнкция имеют один и тот же ранг.
Алгоритм образования СКНФ и СДНФ по таблице истинности
1. Выделить в таблице истинности все строки, в которых функция принимает значения .....	1. Выделить в таблице истинности все строки, в которых функция принимает значения ......
2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные: а) если значение переменной равно ....., то записывается ................................................; б) если значение переменной равно ....., то записывается ................................................. .............................................................	2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные: а) если значение переменной равно ....., то записывается ................................................; б) если значение переменной равно ....., то записывается ................................................. .............................................................
3. Соединить элементарные дизъюнкции знаком конъюнкции.	3. Соединить элементарные конъюнкции знаком дизъюнкции.

Пример: Образовать СКНФ согласно таблице истинности. Построить логическую схему.

Исходная таблица:

Этап 1:

Этап 2:

Логическая схема:

X	Y	Z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

X	Y	Z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Этап 3:

.

Задание 11. Составить СКНФ согласно таблице истинности. Построить логические схемы согласно полученным выражениям.

а.

^A	^B	^X
^0	^0	^0
^0	^1	^1
^1	^0	^0
^1	^1	^1

б.

^A	^B	^X
^0	^0	^0
^0	^1	^1
^1	^0	^1
^1	^1	^0

..................................................................... .....................................................................

в.

^A	^B	^C	^X
^0	^0	^0	^1
^0	^0	^1	^1
^0	^1	^0	^1
^0	^1	^1	^1
^1	^0	^0	^0
^1	^0	^1	^0
^1	^1	^0	^0
^1	^1	^1	^1

г.

^A	^B	^C	^X
^0	^0	^0	0
^0	^0	^1	1
^0	^1	^0	1
^0	^1	^1	1
^1	^0	^0	0
^1	^0	^1	1
^1	^1	^0	0
^1	^1	^1	1

..................................................................... .....................................................................

Задание 12. Составить СДНФ согласно таблице истинности. Построить логические схемы согласно полученным выражениям.

а.

^A	^B	^X
^0	^0	^1
^0	^1	^0
^1	^0	^0
^1	^1	^1

^б.

^A	^B	^X
^0	^0	^1
^0	^1	^1
^1	^0	^0
^1	^1	^0

..................................................................... .....................................................................

в.

^A	^B	^C	^X
^0	^0	^0	^1
^0	^0	^1	^0
^0	^1	^0	^0
^0	^1	^1	^1
^1	^0	^0	^0
^1	^0	^1	^0
^1	^1	^0	^0
^1	^1	^1	^1

г.

^A	^B	^C	^X
^0	^0	^0	0
^0	^0	^1	0
^0	^1	^0	0
^0	^1	^1	0
^1	^0	^0	0
^1	^0	^1	1
^1	^1	^0	1
^1	^1	^1	1

..................................................................... .....................................................................