Логические основы работы ЭВМ

Логические основы работы ЭВМ (Логические функции и законы алгебры логики)

Адрес

http://90.189.213.191:4422/temp/nkpsis/tema_wt_tc23/lek4/lek4.doc инд: 2-124-3-4

Совершенные формы записи логических функций по таблицам истинности.

Для описания логики функционирования аппаратных и программных средств ЭВМ используется алгебра логики (булева алгебра). Булева алгебра оперирует с логическими переменными, которые могут принимать только два значения: истина (1) или ложь (0). Совокупность значений логических переменных называется набором переменных.

Для k логических переменных существует 2k логических комбинаций из 0 и 1,

например при k=2 x1x2=00, 01, 10, 11.

Логической функцией от набора логических переменных (аргументов) называется функция, которая может принимать только два значения: истина (1) или ложь (0). Логическая функция также называется переключательной или булевой функцией.

Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы аргументов, а в правой соответствующие им значения функции (табл.1).

Основными логическими функциями являются:

дизъюнкция (синонимы - логическое сложение, операция ИЛИ), конъюнкция (логическое умножение, операция И) и логическое отрицание (инверсия, операция НЕ).

В булевой алгебре используются следующие обозначения данных операций:

конъюнкция: ;

дизъюнкция: ;

инверсия: .

Таблица истинности (соответствия) для логических функций

В электрических схемах логические операции сложения, умножения и инверсии выполняют логические элементы: дизъюнктор, конъюнктор, инвертор соответственно

а) б) в)

Аксиомы и законы булевой алгебры

Аксиомы и законы	Алгебраические выражения
Аксиомы
Законы
Переместительный (коммутативный)
Сочетательный (ассоциативный)
Распределительный (дистрибутивный)
Двойственности (де Моргана)
Двойного отрицания
Поглощения
Склеивания

Формы записи логических функций

Логические функции могут быть записаны либо в аналитическом, либо в табличном виде.

Табличная форма записи представляет собой таблицу истинности.

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

Пример:

Различают две нормальные формы записи логических функций:

Дизъюнктивная нормальная форма (ДНФ) - представляет собой логическую сумму элементарных конъюнкций (минтермов).

Пример: .

Конъюнктивная нормальная форма (КНФ) - представляет собой логическое произведение элементарных дизъюнкций (макстермов).

Пример: .

Минтерм (конституента единицы) – конъюнкция, которая связывает только отдельные переменные в прямом или инверсном виде.

Пример:

Макстерм (конституента нуля) – дизъюнкция, которая связывает отдельные переменные в прямом или инверсном виде.

Пример:

Число переменных, составляющих элементарную дизъюнкцию или конъюнкцию называется рангом.

Любая переключательная функция может иметь несколько ДНФ и КНФ. Однозначность представления выполняется при записи переключательной функции в совершенной нормальной форме.

Совершенная ДНФ (СДНФ) – форма записи логической функции в виде дизъюнкции элементарных конъюнкций, для которых значение функции равно единице.

При этом каждая конъюнкция включает в себя каждую переменную только один раз в прямом или инверсном виде.

Пример: .

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

Основные законы и тождества алгебры логики. Упрощение логических выражений. Понятие логического базиса. Базисы И, НЕ; ИЛИ, НЕ; И, ИЛИ, НЕ.

Основные законы представлены выше. Рассмотрим практические примеры Функций Алгебры Логики.

Физическая реализация функций алгебры логики осуществляется на дискретных элементах автоматики, к которым относятся реле, двухпозиционные переключатели и логические элементы (ЛЭ). Операция логического умножения выполняется путем последовательного соединения контактов реле или с помощью логического элемента И (дизъюнктора) (рис. 1.1). Логическое сложение выполняется при параллельном соединении контактов или на логическом элементе ИЛИ (конъюнкторе) (рис. 1.2), а логическое отрицание представляется инверсным контактом реле или выполняется логическим элементом НЕ (инвертором) (рис. 1.3). Функции, выполняемые представленными на этих рисунках элементами, можно записать в виде таблиц соответствия (табл. 1.1 - 1.3).

$e:\disc\__тду ат\tdy\m1a\3.gif$

Функции, выполняемые представленными на этих рисунках элементами, можно записать в виде таблиц соответствия (табл. 1.1 _ 1.3).

$e:\disc\__тду ат\tdy\m1a\4.gif$

Временные диаграммы работы логических схем И, ИЛИ и НЕ приведены на рис. 1.4 (а, б).

$e:\disc\__тду ат\tdy\m1a\5.gif$

Система ФАЛ {И, ИЛИ, НЕ} является функционально полной, но не минимальной. Минимальной функционально полной системой называется такая система, исключение из которой хотя бы одной функции делает систему неполной. К ним относятся системы функций {И, НЕ } и {ИЛИ, НЕ}. Любую логическую функцию, записанную в выражениях базиса {И, ИЛИ, НЕ}, можно записать и в базисах {И, НЕ}, {ИЛИ, НЕ}. Переход от одного базиса к другому осуществляется с использованием закона двойного инвертирования и правила де Моргана (см. ниже). Применение мини-мальных базисов удобно, поскольку на их основе можно записать ФАЛ любой сложности. Физическая реализация логических функций, записанных в минимальных базисах, осуществляется на универсальных логических элементах И-НЕ (элемент Шеффера) и ИЛИ-НЕ (элемент Вебба). Условные обозначения и временные диаграммы работы этих элементов приведены на рис. 1.5 и 1.6 соответственно.

$e:\disc\__тду ат\tdy\m1a\6.gif$

Соотношения между входными и выходными сигналами элементов И-НЕ и ИЛИ-НЕ приведены в табл. 1.4.

$e:\disc\__тду ат\tdy\m1a\7.gif$

Современные логические микросхемы в основном составлены на основе элементов Шеффера и Вебба, а элементы базиса {И, ИЛИ, НЕ} чаще всего используются в качестве буферов, ключей и элементов с третьим (высокоомным) состоянием.

Практическое задание -3

«Упрощение логических выражений по законам алгебры логики.»

Составить таблицу истинности для логической функции по варианту практической задачи ПЗ-2 выбором из списка группы;
Представить данные форматом документа Word из импортируемой таблицы Excel (или скан рисунка)

Пример выполнения ПЗ-3 для варианта ((A и B ) и ( С и D )) или ( A и-не B ) файл primer_logika1.xls

Скан представлен ниже.

Электронные источники:

Подготовил Шабронов А.А. тс +7-913-905-8839 shabronov@ngs.ru

Ред.2018-9-18