Аналитическая запись функций алгебры логики

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

Свойства операций алгебры логики
Свойства операции отрицание
a) Закон двойного отрицания:
b)
Следствие: знак отрицания, стоящий над всем выражением, можно переносить в другую часть равносильности

Свойства операций конъюнкция и дизъюнкция
a) Законы нулевого множества:
b) Законы универсального множества:

c) Законы идемпотентности:
d) Закон исключенного третьего:
e) Закон логического противоречия:
Свойства операций конъюнкция и дизъюнкция

Свойства операций конъюнкция и дизъюнкция
f) Коммутативные законы:
g) Ассоциативные законы:

Свойства операций конъюнкция и дизъюнкция
h) Дистрибутивные законы
- конъюнкции относительно дизъюнкции:

Свойства операций конъюнкция и дизъюнкция
h) Дистрибутивные законы
- конъюнкции относительно дизъюнкции:
- дизъюнкции относительно конъюнкции:

Свойства операций конъюнкция и дизъюнкция
i) Законы де Моргана:
Связь конъюнкции и дизъюнкции :

Свойства операций конъюнкция и дизъюнкция
j) Правила склеивания:
Доказательство:
Пример:

Свойства операций конъюнкция и дизъюнкция
k) Правила поглощения:
Доказательство:
Пример:
Правила склеивания и поглощения могут быть применены и в обратном направлении:

Свойства операций штрих Шеффера и стрелка Пирса
a) Коммутативный закон:
b) Несправедлив ассоциативный закон:
c) Выражение операций штрих Шеффера и стрелка Пирса через операции конъюнкция, дизъюнкция и отрицание:

Свойства операций штрих Шеффера и стрелка Пирса
d) Выражение операций отрицание,
конъюнкция и дизъюнкция
через операцию штрих Шеффера
Одна операция штрих Шеффера образует базис.
Аналогично эти операции можно выразить и через операцию стрелка Пирса.
Одна операция стрелка Пирса образует базис.

Свойства операций штрих Шеффера и стрелка Пирса
Пример: Записать формулу
с помощью одной операции штрих Шеффера
a V b V c = a b c

Свойства операций импликация и запрет
a) Несправедлив коммутативный закон
b) Несправедлив ассоциативный закон
c) Выражение операций импликация и запрет через операции конъюнкция, дизъюнкция и отрицание:
Логический элемент Логический элемент
Импликатор Запрет

Свойства операций импликация и запрет
d) Выражение операций отрицание, конъюнкция и дизъюнкция
через операцию импликация
доказательство:
Операция импликация и константа 0 образуют базис:
Аналогично эти операции можно выразить и через операцию запрет.
Операция запрет и константа 1 образуют базис.

Свойства операций эквивалентность,
сложение по модулю два и исключающее ИЛИ
a) Справедлив коммутативный закон
b) Справедлив ассоциативный закон (?)
c) Выражение операций эквивалентность, сложение по модулю два и исключающее ИЛИ через операции конъюнкция, дизъюнкция и отрицание:

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

Частично заданные функции
Такие функции называются не полностью определенные или частично заданные функции.
Наборы, на которых функция не определена, называются запрещенными наборами, а
в таблице истинности на данных наборах ставится символ *.
Это не какое-то третье состояние, это значит, что значение функции на данном наборе неважно, поэтому
вместо * можно поставить
и 0, и 1.

Частично заданные функции
В числовом задании для частично заданных функций отдельно указывают номера наборов, на которых функция не определена:
Разрешенные наборы
Запрещенные наборы

Пример

b
c
d
e
f
DC
a
b
c
d
e
f
g
1
2
4
8
CT
10
+1
1
2
4
8
счетчик
дешифратор для
7-сегментного индикатора
7-сегментный индикатор
1 1 1 1 1 1 0
0 1 1 0 0 0 0
1 1 0 1 1 0 1
1 1 1 1 0 0 1
g
0 1 1 0 0 1 1
1 0 1 1 0 1 1
1 0 1 1 1 1 1
1 1 1 0 0 0 0
1 1 1 1 1 1 1
1 1 1 1 0 1 1
a
x4
x3
x2
x1
Таблица истинности для дешифратора

Частично заданные функции
Чтобы записать частично заданную функцию аналитически, ее нужно доопределить, т.е. вместо всех * поставить нули или единицы.
Если функция не определена на
q наборах, ее можно доопределить
2q способами.
Следовательно, из одной частично заданной функции можно получить
2q полностью заданных функций.

Аналитическая запись
функций алгебры логики
в базисе И, ИЛИ, НЕ

Функционально полная система
Функционально полная система (базис) – набор некоторых операций (или даже всего одной), который позволяет записывать любую, сколь угодно сложную функцию алгебры логики.
Примеры базисов:
дизъюнкция, конъюнкция и отрицание; (основной базис)
импликация и константа 0;
запрет и константа 1;
штрих Шеффера;
стрелка Пирса.
Минимальным базисом называется такой базис, для которого исключение хотя бы одной из составляющих его функций превращает данную систему функций в неполную.
Минимальный базис:
дизъюнкция и отрицание;
конъюнкция и отрицание;

Минимизация ФАЛ
Нахождение кратчайшей аналитической записи функции алгебры логики в некотором базисе называется минимизацией.
Лучше всего подходит основной базис:
дизъюнкция, конъюнкция и отрицание
Для записи произвольной функции, заданной с помощью таблицы истинности, используют так называемые дизъюнктивные и конъюнктивные нормальные формы.

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

Элементарная конъюнкция, в которую входят все аргументы данной функции, называется элементарной конъюнкцией высшего ранга, или минтермом.
Минтерм
Минтерм – это функция, которая равна 1 на одном наборе и 0 – на всех остальных.
Чтобы записать минтерм для i-того набора, нужно записать конъюнкцию всех аргументов функции, причем если аргумент входит в данный набор как 0, то он пишется с отрицанием, а если как 1 – без отрицания.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.
ДНФ для функции f(x1 x2…xn ), состоящая только из минтермов, называется совершенной дизъюнктивной нормальной формой (СДНФ).
Минимальной ДНФ (МДНФ) называется ДНФ, содержащая наименьшее количество операций дизъюнкция и конъюнкция по сравнению с другими ДНФ данной функции.
Дизъюнктивные нормальные формы

Чтобы записать функцию в СДНФ нужно выписать минтермы тех наборов, на которых функция равна 1, и объединить их знаками дизъюнкции.
Аналитическая запись ФАЛ

Упрощение ДНФ может быть достигнуто за счет уменьшения числа входящих в ДНФ элементарных конъюнкций и за счет уменьшения ранга самих конъюнкций.
Ранг элементарных конъюнкций может быть уменьшен путем их попарного сравнения и склеивания.
Самые короткие элементарные конъюнкции, возможные для данной функции, называются простыми импликантами.
МДНФ должна состоять из простых импликант. У функции может быть несколько ДНФ, состоящих только из простых импликант.
ДНФ, в которую входят все возможные простые импликанты данной функции, называется сокращенной дизъюнктивной нормальной формой (СокрДНФ).
Аналитическая запись ФАЛ

Чтобы найти СокрДНФ, нужно в СДНФ провести все возможные склеивания.
Если из СокрДНФ выбрасывать лишние простые импликанты, можно получить новые ДНФ, состоящие тоже из простых импликант, но более короткие.
Тупиковой ДНФ (ТДНФ) называется ДНФ, состоящая из простых импликант, у которой при удалении из неё любой импликанты получаемая в результате ДНФ не является эквивалентной исходной.
Очевидно, что МДНФ функции является одной из её ТДНФ.
Аналитическая запись ФАЛ

Элементарной дизъюнкцией называется дизъюнкция, нескольких аргументов, причем каждый аргумент входит в нее не более одного раза.
Рангом элементарной дизъюнкции называется количество аргументов, входящих в эту дизъюнкцию.
Элементарная дизъюнкция
КНФ

Элементарная дизъюнкция, куда входят все аргументы функции, называется элементарной дизъюнкцией высшего ранга, или макстермом.
Макстерм
Макстерм – это функция, которая равна 0 на одном наборе и 1 – на всех остальных.
Чтобы записать макстерм для i-того набора, нужно записать дизъюнкцию всех аргументов функции, причем если аргумент входит в данный набор как 1, то он пишется с отрицанием, а если как 0 – без отрицания.
КНФ

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. У функции может быть несколько КНФ.
КНФ для функции f(x1 x2…xn ), состоящая только из макстермов, называется совершенной конъюнктивной нормальной формой (СКНФ).
Минимальной КНФ (МКНФ) называется КНФ, содержащая наименьшее количество операций дизъюнкция и конъюнкция по сравнению с другими КНФ данной функции. У функции может быть несколько МКНФ.
Конъюнктивные нормальные формы
КНФ

Чтобы записать функцию в СКНФ нужно выписать макстермы тех наборов, на которых функция равна 0, и объединить их знаками конъюнкции.
Аналитическая запись ФАЛ
КНФ

Чтобы найти все простые импликанты (т.е. сокращенную дизъюнктивную нормальную форму), нужно в СДНФ провести все возможные склеивания.
Выбрасывая из СокрДНФ лишние простые импликанты, можно получить новые ДНФ, состоящие тоже из простых импликант, но более короткие (ТДНФ).
Выбирая из ТДНФ те, у которых наименьшее число операций, находим МДНФ.
Стратегия минимизации ФАЛ
СДНФ ? СокрДНФ
СокрДНФ ? ТДНФ
ТДНФ ? МДНФ
МДНФ содержит наименьшее количество операций дизъюнкция и конъюнкция по сравнению с другими ДНФ данной функции.
МДНФ должна состоять из простых импликант.

Алгоритм метода Квайна включает два этапа:
1. Нахождение всех простых импликант функции.
2. Составление таблицы Квайна и нахождение МДНФ
Алгоритм метода Квайна