close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Основные понятия
алгебры логики
Лямин Андрей Владимирович
Основные термины
• Алгебра логики
• Логическое высказывание
• Логические связки:
–
–
–
–
–
«НЕ»;
«И»;
«ИЛИ»;
«ЕСЛИ …, ТО …»;
«… ТОГДА И ТОЛЬКО ТОГДА …".
Логические операции
•
•
•
•
•
Отрицание
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция
Отрицание
• Логическая связка: «НЕ».
• Обозначение: A .
A
A
0
1
1
0
Конъюнкция
• Логическая связка: «И».
• Обозначение: A B ; A B ; A & B .
A
B
A B
0
0
0
0
1
0
1
0
0
1
1
1
Дизъюнкция
• Логическая связка: «ИЛИ».
• Обозначение: A B ; A B .
A
B
A B
0
0
0
0
1
1
1
0
1
1
1
1
Импликация
• Логическая связки: «ЕСЛИ …, ТО», «ИЗ
… СЛЕДУЕТ», «… ВЛЕЧЕТ …».
• Обозначение: A B.
A
B
A B
0
0
1
0
1
1
1
0
0
1
1
1
Эквиваленция
• Логическая связки: «тогда и только
тогда», «необходимо и достаточно», « …
равносильно …».
• Обозначение: A B .
A
B
A
B
0
0
1
0
1
0
1
0
0
1
1
1
Логическая функция
Функцией алгебры логики f (x1, x2, ... ,xn) от
n - переменных x1, x2, ... ,xn, принимающих
значения 0 или 1, называется функция,
принимающая значения 0 или 1.
Таблица истинности
x1
x2
…
xn
f (x1, x2, ... ,xn)
0
0
…
0
f (0, 0, ... ,0)
0
0
…
1
f (0, 0, ... ,1)
…
…
…
…
…
1
1
…
0
f (1, 1, ... ,0)
1
1
…
1
f (1, 1, ... ,1)
Логическая формула
• Суперпозицией функций f1,...,fm называется
функция f, полученная с помощью подстановок
этих функций друг в друга, а формулой
называется выражение, описывающее эту
суперпозицию.
• Для записи формулы функции алгебры логики
необходимо либо перечислить все ситуации, в
которых она истинна, либо исключить все
ситуации, в которых она ложна.
Минимизация
логических функций
• Применение законов алгебры логики
• Метод Куайна-Маккласки
• Метод карт Карно
Коммутативный закон
x1 x 2 x 2 x1
x1 x 2 x 2 x1
Ассоциативный закон
x1 ( x 2 x 3 ) ( x1 x 2 ) x 3
( x1 x 2 ) x 3 x1 ( x 2 x 3 )
Дистрибутивный закон
x1 ( x 2 x3 ) x1 x 2 x1 x3
( x1 x 2 ) ( x1 x 3 ) x1 x 2 x 3
Теорема де Моргана
x1 x 2 x1 x 2
x1 x 2 x1 x 2
Свойство идемпотенции
x1 x1 x1
x1 x1 x1
Свойство поглощения
x1 x1 x 2 x1
x1 ( x1 x 2 ) x1
Операция
переменной с инверсией
x1 x1 1
x1 x1 0
Операции с константами
x1 0 x1
x1 1 1
x1 0 0
x1 1 x1
Пример 1:
f x1 x 2 x 3 x1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x1 x 2 ( x 3 x 3 ) x 1 x 2 ( x 3 x 3 ) x 2 ( x1 x1 ) x 2
Метод Куайна-Маккласки
Метод минимизации логических функций КуайнаМаккласки основан на том факте, что вынос общего
множителя за скобки в формуле эквивалентен
объединению двух строк в одну в таблице
истинности. В комбинируемых строках должны
совпадать все значения переменных, кроме одной сравниваемые строки отличаются на одну единицу.
Значение "не совпавшей" переменной безразлично и
может быть обозначено звездочкой "*"
Пример 2:
x1
x2
x3
f
1
0
1
1
1
1
1
1
x1
x2
x3
f
1
*
1
1
Пример 3:
Номера строк
1
2
3
4
5
6
7
8
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
0
0
1
1
0
0
1
1
Кол-во единиц
1
2
2
3
Номера строк
3
4
7
8
x1
0
0
1
1
x2
1
1
1
1
x3
0
1
0
1
f
1
1
1
1
Кол-во единиц
1
2
2
3
Номера строк
3, 4
3, 7
4, 8
7, 8
x1
0
*
*
1
x2
1
1
1
1
x3
*
0
1
*
f
1
1
1
1
Кол-во единиц
1
1
2
2
Номера строк
3, 4
3, 7
4, 8
7, 8
x1
0
*
*
1
x2
1
1
1
1
x3
*
0
1
*
f
1
1
1
1
Кол-во единиц
1
1
2
2
Номера строк
3, 4, 7, 8
3, 7, 4, 8
x1
*
*
x2
1
1
x3
*
*
f
1
1
Кол-во единиц
1
1
Номера строк
3, 4, 7, 8
x1
*
x2
1
x3
*
f
1
Кол-во единиц
1
f x2
Метод карт Карно
Карта Карно представляет прямоугольник
разделенный на квадраты, каждому из
которых соответствует определенная
комбинация всех входных переменных.
Внутри каждого квадрата записывается
значение функции на данной комбинации
входных переменных.
Примеры карт Карно
x2
x2
x1
x1
x1
x1
x 4 x1
x 4 x1
x 4 x1
x 4 x1
x3
x2
x3
x2
x3
x2
x3
x2
x3
x2
x3
x2
x3
x2
x3
x2
Пример 4:
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
0
0
1
1
0
0
1
1
x1
x1
x3
x2
x3
x2
x3
x2
x3
x2
1
1
1
1
0
0
0
0
f x2
Документ
Категория
Презентации по информатике
Просмотров
46
Размер файла
288 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа