Функциональные устройства комбинационного типа. Модуль 2. Введение в цифровую схемотехнику.

Тема 6.

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

Основные понятия алгебры логики Закон исключенного третьего Если х 1, то х = 0, если х 0, то х = 1. Если х 1, то х = 0, если х 0, то х = 1. Логическая функция у = f(х1,х2,...,хn) задана, когда каждому набору х однозначно сопоставляется у. Количество функций, образуемых n переменными равно Количество функций, образуемых n переменными равно Если n = 1, то N = 4: у1 = 0, у2 = 1, у2 = 1, у3 = х, у3 = х, у4 = х. у4 = х. Для двух переменных n = 2 и N = 16. х1х1х1х1 х2х2х2х2 у1у1у1у1 у2у2у2у2 у3у3у3у3 у4у4у4у Таблица 1 Логические функции двух переменных В таблице 1 приведены некоторые из возможных функций при n=2

Элементарные логические функции Дизъюнкция Конъюнкция Инверсия Исключающее или Сумма по модулю 2

Конъюнкция (операция и, логическое умножение.) Конъюнкция нескольких переменных равна 1 лишь тогда, когда все переменные равны 1. Конъюнкция (операция и, логическое умножение.) Конъюнкция нескольких переменных равна 1 лишь тогда, когда все переменные равны 1.

Конъюнкция обозначается в виде произведения у = х 1 ·х 2, или у = х 1 х 2, или у = х 1 Λ х 2. Конъюнкция обозначается в виде произведения у = х 1 ·х 2, или у = х 1 х 2, или у = х 1 Λ х 2. Рисунок 6.1 Конъюнктор Таблица 2 - Таблица соответствия для конъюнкции

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

Дизъюнкция обозначается в виде суммы: у = х 1 +х 2, или у = х 1 Vх 2. Дизъюнкция обозначается в виде суммы: у = х 1 +х 2, или у = х 1 Vх 2. Рисунок 6.2 Дизъюнктор Таблица 3 - Таблица соответствия для дизъюнкции

Инверсия (операция не, логическое отрицание). (операция не, логическое отрицание).Инверсия

Рисунок 6.3 Инвертор Таблица 4 - Таблица соответствия для инверсии

Возможны комбинированные операции. Рисунок 6.4 Комбинированные логические элементы

Функция равна 1,когда только одна переменная равна 1. Обозначается значком Исключающее или

Функция равна 1, когда нечетное число переменных равно 1, функция равна 0, когда четное число переменных равно 1. Функция обозначается: в виде у = Σ mod 2 = х 1 х2х2... хnхn Для двух переменных Σmod2 совпадает с функцией исключающее или. Сумма по модулю 2

Для трех переменных в таблице 5 приведены данные для функций исключающее или и сумма по модулю 2. Они уже неполностью совпадают. Таблица 5 Сравнение функций

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

Аксиомы алгебры логики Их можно проверить подставляя вместо х 0 или 1.

Правила Де-Моргана: Любые логические функции могут быть построены с использованием только элементов "И-НЕ" или только элементов "ИЛИ-НЕ". Переход от операции "И" к операции "ИЛИ", а также обратный переход осуществляется с помощью законов дуальности (теорема де Моргана): Любые логические функции могут быть построены с использованием только элементов "И-НЕ" или только элементов "ИЛИ-НЕ". Переход от операции "И" к операции "ИЛИ", а также обратный переход осуществляется с помощью законов дуальности (теорема де Моргана): В предыдущей строке показана типичная ошибка, когда полагают, что произведение инверсий равно инверсии произведения этих же переменных.

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

Минимизация путем алгебраических преобразований Пусть функция задана в виде таблицы х1х1 х2х2 х3х3 У Каждая строка таблицы представляет собой конъюнкцию переменных. Если значение переменной в данной строке равно 0, то переменная берется с инверсией.

Реализация полученного выражения с помощью элементов 2и-не: Рисунок 6.5 Реализация функции, заданной таблицей

Минимизация с помощью диаграмм Карно Правило построения диаграммы Карно

Для n переменных заполняется прямоугольная таблица, содержащая 2n клеток так, чтобы в соседних клетках конъюнкции отличались не более, чем одним сомножителем. Для n переменных заполняется прямоугольная таблица, содержащая 2n клеток так, чтобы в соседних клетках конъюнкции отличались не более, чем одним сомножителем. Если минимизируемая функция при данном наборе переменных равна 1, то в соответствующую клетку ставится 1 (нули можно не ставить). В прямоугольной таблице единицы обводятся контурами и записывается функция в виде суммы произведений,описывающих контуры. Число клеток внутри контура 2к (1,2,4,8...). Следует покрыть все единицы возможно меньшим числом возможно более крупных блоков. Каждому блоку сопоставляется конъюнкция, записываемая следующим образом: 1)Если блок целиком лежит в единичной области переменной хi, то она включается в конъюнкцию без инверсии, если в нулевой области, то с инверсией. 1)Если блок целиком лежит в единичной области переменной хi, то она включается в конъюнкцию без инверсии, если в нулевой области, то с инверсией. 2) Если блок делится точно пополам между нулевой и единичной областями хi,то хi в конъюнкцию не включается (склеивание по хi). 2) Если блок делится точно пополам между нулевой и единичной областями хi,то хi в конъюнкцию не включается (склеивание по хi). Других расположений правильно выбранного блока быть не может. Других расположений правильно выбранного блока быть не может.