Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ.

Этот факт является теоремой алгебры логики. Из него следует, что любая формула (кроме констант 0 и 1) может быть преобразован к виду как СДНФ, так и СКНФ. Константа 0 может быть представлена только СКНФ (), а константа 1 – только СДНФ (). Из вышесказанного следует, что если надо построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции.

 

Алгоритм получения СДНФ по таблице истинности:

1. Отметить те строчки таблицы истинности, в последнем столбце которых стоят 1:

 

X	Y	F(X,Y)
0	0	0
0	1	1*
1	0	1*
1	1	0

 

1. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание:

 – для 2-й строки;

 – для 3-й строки.

1. Все полученные конъюнкции связать в дизъюнкцию: .

 

Алгоритм получения СКНФ по таблице истинности:

1. Отметить те строки таблицы истинности, в последнем столбце которых стоит 0:

 

X	Y	F(X,Y)
0	0	0*
0	1	1
1	0	1
1	1	0*

 

1. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание:

 – для 1-й строки;

 – для 4-й строки.

1. Все полученные дизъюнкции связать в конъюнкцию: .

 

Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики: .

Примечание: для нахождения формулы по таблице истинности рекомендуется использовать тот из двух алгоритмов, в котором в таблице помечается меньше строк.

 

ТИПОВЫЕ ЛОГИЧЕСКИЕ УСТРОЙСТВА ЭВМ.

К типовым логическим устройствам ЭВМ относятся сумматоры, полусумматоры, триггеры, счетчики, регистры, шифраторы, дешифраторы.

 

СУММАТОРЫ.

 

Сумматор является основным узлом арифметико-логического устройства ЭВМ и служит для суммирования чисел посредством поразрядного сложения.

Сумматор выполняет сложение многозначных двоичных чисел. Он представляет собой последовательное соединение одноразрядных двоичных сумматоров, каждый из которых осуществляет сложение в одном разряде. При этом если сумма двух цифр в данном разряде больше или равна основанию используемой системы счисления, то возникает перенос старшего разряда в соседний сумматор.

Одноразрядный сумматор должен иметь два выхода: для суммы и для переносимого значения. У него может быть два или три (для складываемых значений и значения переноса) входа.

 

Одноразрядный двоичный сумматор на два входа и два выхода называется одноразрядным полусумматором.

Одноразрядный двоичный сумматор на три входа и два выхода называется одноразрядным сумматором на три входа.

ОДНОРАЗРЯДНЫЙ ПОЛУСУММАТОР.

Условное обозначение:

В двоичной системе счисления операция сложения двух двоичных чисел в одном разряде осуществляется по правилу:

 

X	Y	P (перенос)	S(сумма)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

 

Из таблицы видно, что P (X, Y) = X & Y. Формула для S можно получить двумя способами: либо по алгоритмам получения СДНФ или СКНФ, либо по сводной таблице логических функций двух переменных

Предпоследняя формула – это СКНФ, последняя – СДНФ.

Для построения функциональной схемы воспользуемся структурной формулой , так как в ней наименьшее количество операций. Получим структурные формулы и функциональную схему одноразрядного полусумматора:

 

 

СВОДНАЯ ТАБЛИЦА ЛОГИЧЕСКИХ ФУНКЦИЙ ДВУХ ПЕРЕМЕННЫХ