Основные понятия алгебры логики Лямин Андрей Владимирович

Основные термины Алгебра логики Логическое высказывание Логические связки: –«НЕ»; –«И»; –«ИЛИ»; –«ЕСЛИ …, ТО …»; –«… ТОГДА И ТОЛЬКО ТОГДА …".

Логические операции Отрицание Конъюнкция Дизъюнкция Импликация Эквиваленция

Отрицание Логическая связка: «НЕ». Обозначение:

Конъюнкция Логическая связка: «И». Обозначение: ; ;

Дизъюнкция Логическая связка: «ИЛИ». Обозначение: ;

Импликация Логическая связки: «ЕСЛИ …, ТО», «ИЗ … СЛЕДУЕТ», «… ВЛЕЧЕТ …». Обозначение:

Эквиваленция Логическая связки: «тогда и только тогда», «необходимо и достаточно», « … равносильно …». Обозначение:

Логическая функция Функцией алгебры логики f (x 1, x 2,...,x n ) от n - переменных x 1, x 2,...,x n, принимающих значения 0 или 1, называется функция, принимающая значения 0 или 1.

Таблица истинности x1x1 x2x2 …xnxn f (x 1, x 2,...,x n ) 00…0f (0, 0,...,0) 00…1f (0, 0,...,1) …………… 11…0f (1, 1,...,0) 11…1f (1, 1,...,1)

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

Минимизация логических функций Применение законов алгебры логики Метод Куайна-Маккласки Метод карт Карно

Коммутативный закон

Ассоциативный закон

Дистрибутивный закон

Теорема де Моргана

Свойство идемпотенции

Свойство поглощения

Операция переменной с инверсией

Операции с константами

Пример 1:

Метод Куайна-Маккласки Метод минимизации логических функций Куайна- Маккласки основан на том факте, что вынос общего множителя за скобки в формуле эквивалентен объединению двух строк в одну в таблице истинности. В комбинируемых строках должны совпадать все значения переменных, кроме одной - сравниваемые строки отличаются на одну единицу. Значение "не совпавшей" переменной безразлично и может быть обозначено звездочкой "*"

Пример 2: x1x1 x2x2 x3x3 f x1x1 x2x2 x3x3 f 1*11

Пример 3: Номера строкx1x1 x2x2 x3x3 fКол-во единиц

Номера строкx1x1 x2x2 x3x3 fКол-во единиц Номера строкx1x1 x2x2 x3x3 fКол-во единиц 3, 401*11 3, 7*1011 4, 8*1112 7, 811*12

Номера строкx1x1 x2x2 x3x3 fКол-во единиц 3, 401*11 3, 7*1011 4, 8*1112 7, 811*12 Номера строкx1x1 x2x2 x3x3 fКол-во единиц 3, 4, 7, 8*1*11 3, 7, 4, 8*1*11 Номера строкx1x1 x2x2 x3x3 fКол-во единиц 3, 4, 7, 8*1*11

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

Примеры карт Карно

Пример 4: x1x1 x2x2 x3x3 f