Презентация по теме "Алгебра логики и логические операции"

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

Основные понятия алгебры логики

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

Если n = 1, то N = 4: у1 = 0,
у2 = 1,
у3 = х,
у4 = х.
Для двух переменных n = 2 и N = 16.

Таблица 1 Логические функции двух переменных

В таблице 1 приведены некоторые из возможных функций при n=2

Дизъюнкция

Конъюнкция

Инверсия

Исключающее “или”

Сумма по модулю 2

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

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

Рисунок 6.1 Конъюнктор

Таблица 2 - Таблица соответствия для конъюнкции

Дизъюнкция
(операция “или”, логическое сложение.)

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

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

Рисунок 6.2 Дизъюнктор

Таблица 3 - Таблица соответствия для дизъюнкции

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

Рисунок 6.3 Инвертор

Таблица 4 - Таблица соответствия для инверсии

Возможны комбинированные операции.

Рисунок 6.4 Комбинированные логические элементы

Функция равна 1,когда только одна переменная равна 1.

Обозначается значком

Функция равна 1, когда нечетное число переменных равно 1,функция равна 0, когда четное число переменных равно 1.

Функция обозначается: в виде у = Σmod2 = х1

Для двух переменных Σmod2 совпадает с функцией исключающее “или”.

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

Таблица 5 Сравнение функций

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

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

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

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

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

Пусть функция задана в виде таблицы

Каждая строка таблицы представляет собой конъюнкцию переменных. Если значение переменной в данной строке равно 0, то переменная берется с инверсией.

Реализация полученного выражения с помощью элементов ”2и-не”:

Рисунок 6.5 Реализация функции, заданной таблицей

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