Выполнение логических функций на логических элементах.

Практическое занятие

Тема: Выполнение логических функций на логических элементах.

Цель. Научиться определять значения логических функций и составлять таблицы истинности сложных функций.

Теоретический материал

ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ ФУНКЦИИ К ЛОГИЧЕСКОЙ СХЕМЕ.

Для построения логической схемы необходимо логические элементы, предназначенные

для выполнения логических операций, располагать, начиная от входа, в порядке, указанном

в булевом выражении.

Построим структуру логического устройства (комбинационную схему), реализующего

логическую функцию трех переменных

y =(a + b + c)(a + b + c)(a + b + c)(a + b + c).

Слева располагаем входы а, b и c с ответвлениями на три инвертора, затем четыре

элемента ИЛИ и, наконец, элемент И на выходе (рис. 1).

Итак, любую логическую функцию можно реализовать непосредственно по

выражениям, представленным в виде СДНФ или СКНФ. Однако, полученная таким

образом схема, как правило, не оптимальна с точки зрения её практической реализации: она

громоздка, содержит много логических элементов и возникают трудности в обеспечении

её высокой надёжности.

Алгебра логики позволяет преобразовать формулы, описывающие сложные

высказывания с целью их упрощения. Это помогает в конечном итоге определить

оптимальную структуру того или иного логического устройства, реализующего любую

сложную функцию. Под оптимальной структурой принято понимать такое построение

логического устройства, при котором число входящих в его состав элементов минимально.

Алгоритм построения логических схем.

1. Определить число логических переменных.

2. Определить количество логических операций и их порядок.

3. Изобразить для каждой логической операции соответствующий ей логический элемент.

4. Соединить логические элементы в порядке выполнения логических операций.

Пример. По заданной логической функции   построить логическую схему.

Решение.

Число логических переменных = 2 (A и B).

Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.

Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор.

Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов).

Логические законы и правила преобразования логических выражений

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений.

1. Закон двойного отрицания:  ;

2. Переместительный (коммутативный) закон:

для логического сложения:   ;

для логического умножения:  ;

3. Сочетательный (ассоциативный) закон:

для логического сложения:   ;

для логического умножения:    ;

4. Распределительный (дистрибутивный) закон:

для логического сложения:   ;

для логического умножения:   ;

5. Законы де Моргана:

для логического сложения:   ;

для логического умножения:   ;

6. Закон идемпотентности:

для логического сложения:   ;

для логического умножения:   ;

7. Законы исключения констант:

для логического сложения:  ;

для логического умножения:  ;

8. Закон противоречия: ;

9. Закон исключения третьего:   ;

10. Закон поглощения:

для логического сложения:  ;

для логического умножения:  ;

11. Правило исключения импликации:  ;

12. Правило исключения эквиваленции:  .

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

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

Пример. Упростить логическое выражение  .

Решение:

Согласно закону де Моргана:

.

Согласно сочетательному закону:

.

Согласно закону противоречия и закону идемпотентности:

.

Согласно закону исключения 0:

Окончательно получаем
/

Контрольные вопросы

1. Что такое высказывание (приведите пример)? 

2. Что такое составное высказывание (приведите пример)? 

3. Как называются и как обозначаются (в языке математики) следующие операции: ИЛИ, НЕ, И, ЕСЛИ … ТО, ТОГДА И ТОЛЬКО ТОГДА, ЛИБО …ЛИБО?

4. Укажите приоритеты выполнения логических операций.

5. Составьте таблицу истинности для следующих операций: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

6. Изобразите функциональные элементы: конъюнктор, дизъюнктор, инвертор.

7. Какие логические выражения называются равносильными?

8. Записать основные законы алгебры логики.