БУЛЕВЫ ФУНКЦИИ.
В отличие от функций непрерывной математики в алгебре логики рассматривают функции, в которых и аргументы и значения функции принимают значения из множества {0,1}. Эти функции называют булевыми функциями.
Значения
аргументов в дальнейшем будем называть
набором аргументов или просто набором.
Из определения булевой функции
следует, что для ее задания достаточно
указать значение функции для каждого
набора аргументов, т.е. записать таблицу.
Число
строк таблицы определяется числом
возможных наборов аргументов и равно
,
где
- число аргументов.
Если
две функции
и
принимают на всех возможных наборах
аргументов одинаковые значения, то
функции
и
называют равными.
Функция
существенно зависит от аргумента
,
если имеет место неравенство
.
В противном случае
является фиктивным аргументом и его
можно удалить.
Доказано,
что число всех функций, зависящих от
аргументов конечно и равно
.
Рассмотрим
функции одного аргумента
.
Столбец
- это значение аргумента, а столбцы
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Ф
ункция
равна нулю при любом значении аргумента
и называется константой ноль.
Записывается
.
В дискретных устройствах логический
ноль реализуется низким уровнем
напряжения:
Значения
функции
совпадает со значением аргумента,
поэтому она называется аргумент x.
Обозначается
Значения
функции
противоположны значению аргумента. Эта
функция называется инверсией аргумента
x, иногда ее называют НЕ-
.
Обозначается
.
В
цифровых устройствах эта функция
реализуется логическим элементом,
который называется инвертором:
Значения
функции
всегда равны единице. Она называется
константой единица. Обозначается
и реализуется высоким уровнем напряжения:
+E
Для двух аргументов существует уже 16 булевых функций.
|
0 |
0 |
1 |
1 |
Название функции |
Обозначение |
|
0 |
1 |
0 |
1 |
||
|
0 |
0 |
0 |
0 |
Константа ноль |
0 |
|
0 |
0 |
0 |
1 |
Произведение (конъюнкция) |
|
|
0 |
0 |
1 |
0 |
Запрет по |
|
|
0 |
0 |
1 |
1 |
Переменная |
|
|
0 |
1 |
0 |
0 |
Запрет по |
|
|
0 |
1 |
0 |
1 |
Переменная |
|
|
0 |
1 |
1 |
0 |
Сумма по модулю 2 |
|
|
0 |
1 |
1 |
1 |
Сумма (дизъюнкция) |
|
|
1 |
0 |
0 |
0 |
Операция Пирса (ИЛИ-НЕ) |
|
|
1 |
0 |
0 |
1 |
Логическая равнозначность |
|
|
1 |
0 |
1 |
0 |
Инверсия (НЕ- ) |
|
|
1 |
0 |
1 |
1 |
Импликация от к |
|
|
1 |
1 |
0 |
0 |
Инверсия (НЕ- ) |
|
|
1 |
1 |
0 |
1 |
Импликация от к |
|
|
1 |
1 |
1 |
0 |
Операция Шеффера (И-НЕ) |
|
|
1 |
1 |
1 |
1 |
Константа 1 |
1 |
Среди этих функций следует особо выделить функции конъюнкции, дизъюнкции, Шеффера, Пирса, суммы по модулю 2:
-конъюнкция
.
Эту функцию иногда называют логическим
произведением, либо функцией И. В
литературе можно встретить различные
обозначения этой функции:
.
-дизъюнкция
.
Эта функция также имеет другие названия:
логическое сложение, операция ИЛИ.
-операция Шеффера (штрих Шеффера, функция Шеффера, И-НЕ)
.
-операция
Пирса (стрелка Пирса, функция Пирса,
ИЛИ-НЕ)
.
-сумма
по модулю 2 (исключающее ИЛИ)
.
В дискретных устройствах эти функции реализуются логическими элементами И, ИЛИ, И-НЕ, ИЛИ-НЕ и элементом сумма по модулю 2.
И ИЛИ И-НЕ ИЛИ-НЕ Сумма по mod 2
Рассмотренные
функции позволяют строить новые функции
путем перестановки аргументов и путем
подстановки в функцию новых функций
вместо аргументов. Функцию, полученную
из функций
путем применения этих правил называют
суперпозицией функций
.
При
дальнейшем увеличении числа аргументов
количество функций быстро возрастает:
при 3 аргументах существует 256 функций,
при 4 аргументах – 65536 функций,… Среди
этих функций есть и уже известные функции
0, 1,
,
,
,
,…,
а также многоместные функции конъюнкции,
дизъюнкции, Шеффера и Пирса. При любом
числе аргументов для этих функций
справедливо следующее:
- конъюнкция (И). Если хотя бы один аргумент равен 0, то функция равна 0. Функция равна 1, если все аргументы равны 1;
- штрих Шеффера (И-НЕ). Если хотя бы один аргумент равен 0, то функция равна 1. Функция равна 0, если все аргументы равны 1;
- дизъюнкция (ИЛИ). Если хотя бы один аргумент равен 1, то функция равна 1. Функция равна 0, если все аргументы равны 0;
- стрелка Пирса (ИЛИ-НЕ). Если хотя бы один аргумент равен 1, то функция равна 0. Функция равна 1, если все аргументы равны 0.
Основные формулы булевой алгебры.
Для доказательства формул можно пользоваться табличным методом. При его использовании строятся таблицы истинности для левой и правой частей доказываемого соотношения. Если эти таблицы совпадают, то имеет место тождество.
Свойства конъюнкции, дизъюнкции и отрицания.
,
,
,
,
,
,
.
Для
последнего соотношения нет аналога в
обычной алгебре
,
но в булевой алгебре это тождество.
Проверим его справедливость табличным
методом:
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Пятый и восьмой столбцы соответствуют значениям левой и правой частей на всех возможных наборах аргументов. Совпадение этих столбцов доказывает тождество.
Существование последних двух тождеств (распределительных законов) делает законы булевой алгебры полностью двойственными. Это означает, что если существует какое–либо равенство, то существует и второе равенство, в котором символы дизъюнкции заменены символами конъюнкции, а символы конъюнкции – символами дизъюнкции.
Пример.
Справедливо равенство
,
в силу свойства двойственности справедливо
и равенство
.
Эти тождества называются соотношениями
Блека – Порецкого.
,
,
,
,
,
,
,
,
,
,
,
,
последние два тождества называются правилами де Моргана. Эти правила можно обобщить для нескольких аргументов:
,
.
Правила
поглощения:
,
,
,
.
Правила
склеивания по переменной
:
,
.
Вынесение
за скобки:
,
.
Свойства функций Шеффера, Пирса, суммы по модулю 2.
,
,
,
,
,
.
,
.
Для функций Шеффера и Пирса имеет место переместительный закон:
,
,
Но сочетательный закон для них НЕ справедлив!
,
,
,
,
,
,
,
,
,
.
Существуют тождества похожие на правила де Моргана:
,
.
На практике часто возникает необходимость преобразовать функцию, аргументы которой связаны операцией Шеффера или Пирса к выражению, содержащему только операции конъюнкции, дизъюнкции и отрицания. Если символы отрицания расположены над одиночными символами переменных, то такая булева функция называется нормальной. Именно такие представления функций наиболее просто воспринимаются человеком. Для подобного преобразования в литературе обычно используют правила де Моргана, однако существует очень простой прием, позволяющий сразу записать искомый результат:
1) заменить в выражении операции Пирса и Шеффера на операции И-НЕ и ИЛИ-НЕ соответственно;
2) подсчитать число инверсий над каждой буквой, если оно четно, то в преобразуемое выражение эта буква будет входить без отрицания, если нечетно – с отрицанием;
3) подсчитать число инверсий над каждой логической операцией, если число инверсий четно, то операция не меняется, если нечетно, то логическая операция заменяется дуальной логической операцией.
Пример:
Для функций Шеффера и Пирса можно вывести тождества, похожие на правила склеивания:
,
действительно,
,
,
Аналитическая запись булевых функций в булевом базисе.
Определение: конституентой единицы булевой функции называют произведение всех ее аргументов, записанных с отрицанием или без него.
Пример:
если рассмотреть функцию трех аргументов
,
то
,
,
-конституенты единицы. Напишем несколько
выражений не являющихся конституентами
единицы:
(не все аргументы),
- используя правило де Моргана, получим:
,
а это противоречит определению
конституенты единицы.
Следствие: любая конституента единицы равна единице только на одном наборе аргументов, на остальных наборах эта конституента равна нулю.
Для
того чтобы определить набор на котором
конституента единицы равна 1 следует
найти такие значения аргументов, которые
дают значение 1 каждому члену произведения.
Пример:
,
если
,
а это возможно только на наборе 101.
Теорема: Любая булева функция может быть записана в виде дизъюнкции конституент единицы, соответствующих тем наборам на которых функция равна 1.
Доказательство. Выберем в таблице истинности произвольный набор. При этом возможны два случая:
Если на данном наборе функция равна 1, то из множества конституент выберем конституенту равную 1 на этом наборе (на остальных наборах она будет равна нулю) и записываем ее в формулу. Учитывая свойство дизъюнкции 1+…=1, мы обеспечиваем единичное значение функции на этом наборе.
Если на этом наборе функция равна нулю, то конституента равная 1 на этом наборе в формулу не вписывается, а значит на этом наборе функция будет равна 0.
После рассмотрения всех наборов мы получим аналитическую запись булевой функции в дизъюнктивной совершенной нормальной форме (ДСНФ).
Алгоритм перехода к ДСНФ:
- Выбрать в таблице истинности все наборы на которых функция равна единице.
- Записать конституенты 1 равные единице на этих наборах. При этом, если аргумент в наборе равен 1, то в конституенту единицы этого набора он записывается без отрицания. Если же аргумент в наборе равен нулю, то он записывается с отрицанием.
- Полученные конституенты соединить операцией дизъюнкции.
П
|
|
с |
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Определение: конституентой нуля называют дизъюнкцию всех переменных, записанных с отрицанием или без него.
Любая конституента нуля равна нулю только на одном наборе, на остальных наборах она равна 1.
Теорема. Любая булева функция может быть записана как конъюнкция конституент нуля, записанных для наборов, где функция равна нулю.
Доказательство.
Выбираем в таблице истинности произвольный
набор. Если на этом наборе функция равна
нулю, то записываем конституенту нуля
равную нулю на этом наборе. Поскольку
свойство конъюнкции
,
то на данном наборе функция будет равна
нулю. Если же функция равна на наборе
1, то конституенту нуля равную нулю на
этом наборе не выписываем, а т.к. остальные
конституенты на этом наборе равны 1, то
и их произведение будет равно 1. Такая
запись булевой функции называется
конъюнктивной совершенной нормальной
формой (КСНФ).
Алгоритм перехода к КСНФ:
-Выбрать в таблице истинности наборы на которых функция равна нулю.
-Записать конституенты нуля равные нулю на этих наборах. Для этого, если аргумент набора равен нулю, то он входит в конституенту без отрицания, если же аргумент входит в набор как 1, то в соответствующую конституенту нуля вписывается его отрицание.
-Все записанные конституенты нуля соединяем знаком конъюнкции.
Запишем КСНФ для функции из предыдущего примера:
.
Дешифраторы.
При работе с дискретными устройствами приходится решать задачи анализа схем и задачи синтеза схем. При решении задачи синтеза после получения технического задания на проектирование устройства составляется математическая модель устройства, а затем разрабатывается схема устройства. Задача анализа обратная задаче синтеза. Решим задачу анализа, рассматривая схему простейшего дешифратора с прямыми выходами.
В
схеме два входа
,
и четыре выхода, которые описываются
булевыми уравнениями:
,
,
,
.
Построим таблицы истинности для этих
уравнений:
|
|
|
|
|
Видно,
что такой дешифратор формирует на
своих выходах все конституенты единицы
булевых функций двух аргументов:
,
,
,
. |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
Итак, если на вход дешифратора подать аргументы булевой функции, то на
выходах
дешифратора можно получить все
конституенты единицы. Число входов
дешифратора
связано с числом выходов
соотношением
.
Дешифраторы с двумя, тремя, четырьмя
и т.д. входами можно рассматривать как
генераторы конституент единицы для
функций 2, 3, 4, и т.д. аргументов. Суммируя
конституенты единицы для наборов, где
функция равна 1, мы получаем реализацию
этой функции.
Приведем условные графические обозначения ( УГО) дешифраторов с 2 и 3 входами:
Пример: реализовать систему булевых функций на дешифраторе с прямыми выходами.
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
* |
0 |
1 |
0 |
* |
0 |
1 |
1 |
0 |
1 |
* |
0 |
1 |
1 |
* |
0 |
1 |
1 |
1 |
0 |
0 |
Функции и зависят от трех аргументов, следовательно, необходим дешифратор с тремя входами. Особенностью этих функций является то, что они заданы не на всех наборах. Такие функции называют не полностью определенными булевыми функциями. Наборы, на которых функция не определена, помечены символом *. Эти функции необходимо доопределить, т. е. приписать функциям нам этих наборах значения 0 или 1.
Доопределение проводят таким образом, чтобы получить наиболее простую схему. Для данного примера выгодно доопределить эти наборы нулями.
Существуют дешифраторы с инверсными выходами. Схема такого дешифратора имеет вид:
Запишем уравнения для этого дешифратора:
,
,
,
.
Построим таблицы истинности для этих уравнений:
|
|
|
|
|
Видно,
что такой дешифратор формирует на
своих выходах все конституенты нуля
булевых функций двух аргументов:
,
,. |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
,
,
,
Условные графические обозначения дешифраторов с инверсными выходами отличаются от дешифраторов с прямыми выходами наличием значков инверсии на выходах:
в
ходами:
Такие дешифраторы являются генераторами конституент нуля и позволяют реализовывать булевы функции путем перемножения конституент нуля. Если реализовать функции из предыдущего примера на таких дешифраторах, то получим схему:
Мультиплексоры.
Проведем анализ еще одной простейшей схемы, которую называют
мультиплексором:
Запишем уравнение для выходного сигнала мультиплексора:
.
Функция зависит от шести аргументов,
поэтому таблица истинности будет слишком
громоздкой. Вычислим значения функции
задавая
только значения
и
:
|
|
|
0 |
0 |
|
0 |
1 |
|
1 |
0 |
|
1 |
1 |
|
Входы и мультиплексора называют адресными, а входы , , , -селектируемыми. Из таблицы видно, что мультиплексор подключает к своему выходу один из селектируемых входов, номер которого определяется кодом на адресных шинах.
Число селектируемых входов равно , где - число адресных входов.
В
литературе тип мультиплексора часто
задают обозначением
,
здесь
- число селектируемых входов мультиплексора,
которые коммутируются на 1 выход.
Существуют мультиплексоры 2x1, 4x1, 8x1,
16x1, 32x1 и т.д. Мы рассмотрели мультиплексор
4x1. Принцип работы других мультиплексоров
подобен работе мультиплексора 4x1.
Например функционирование мультиплексора
8x1 можно пояснить аналогичной таблицей:
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
Постройте самостоятельно подобные таблицы для мультиплексоров 2x1 и 16x1.
Приведем условные графические обозначения (УГО) некоторых мультиплексоров:
2x
2x1
4x1
Как выглядят УГО мультиплексоров 8x1 и 16x1?
Любую булеву функцию можно реализовать с помощью мультиплексора. Для этого аргументы функции подают на адресные входы мультиплексора, а значения функции на соответствующие селектируемые входы.
Пример. Реализовать на мультиплексоре функцию:
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
Не следует думать, что число аргументов реализуемой функции должно быть обязательно равно числу адресных входов мультиплексора. Число аргументов может быть большим, но логика формирования селектируемых сигналов обычно усложняется.
Пример: Реализовать на мультиплексоре 4x1 функцию:
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Подключим
к адресным входам мультиплексора 4x1 два
аргумента, например
и
.
При таком подключении сигнал на адресном
входе
совпадает с
,
а на входе
с
.
Поскольку на первых четырех наборах
,
то сигнал на выходе мультиплексора
совпадает с сигналом на шине
.
Нижняя строчка таблицы на наборах 0, 1,
2, 3 показывает какой сигнал должен
формироваться на шине
.
Эти сигнал не постоянен, следовательно
он зависит от еще не учтенных аргументов
и
:
.
Легко увидеть, что логика формирования
сигнала
.
Рассуждая
аналогично можно найти логику формирования
сигналов на остальных селектируемых
шинах:
,
,
.
№ набора |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Сигнал на Сигнал на Сигнал на Сигнал на
Сложность логики, формирующей сигналы на селектируемых входах, зависит от того, какие аргументы подключены к адресным входам. Оптимальную схему можно получить, выполнив синтез для всех возможных комбинаций адресных сигналов.
Если брать мультиплексор с числом адресных входов на единицу меньше, чем число аргументов функции, то для реализации функции потребуется мультиплексор и, возможно, один инвертор.
Пример: Реализовать функцию заданную таблично
№ набора |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
Заметим, что если бы на нулевом наборе функция была бы равна нулю, а на первом наборе – равна единице, инвертор не понадобился бы.
Функциональная полнота систем булевых функций.
Одно из основных требований к системе логических элементов, состоит в том, чтобы из элементов этой системы можно было построить любую логическую схему. Техническая задача отыскания такой системы элементов сводится к математической задаче определения набора функций, из которых методом суперпозиции можно получить любую функцию.
Система булевых функций называется функционально полной, если произвольную булеву функцию можно представить суперпозицией функций этой системы.
Для решения задачи были выделены пять классов булевых функций:
-
сохраняющие нуль – это функции
равные нулю на нулевом наборе аргументов:
;
- сохраняющие единицу – это функции равные единице на единичном наборе:
;
-
самодвойственные булевы функции
на каждой паре противоположных наборов
принимают противоположные значения:
;
-
линейные булевы функции - это функции,
которые можно представить линейным
полиномом:
,
где
.
Если значения каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор не меньше второго. Следует заметить, что не все наборы являются сравнимыми, например (1,0,1) и (0,1,0) не сравнимы.
- монотонной булевой функцией называют функцию, у которой при любом возрастании набора аргументов значения функции не убывают.
Известна теорема о функциональной полноте: для того чтобы система булевых функций была функционально полной, необходимо и достаточно, чтобы эта система включала:
- хотя бы одну функцию, не сохраняющую нуль;
- хотя бы одну функцию, не сохраняющую единицу;
- хотя бы одну нелинейную функцию;
-хотя бы одну немонотонную функцию;
-хотя бы одну несамодвойственную функцию.
В таблице показано, к каким классам относятся функции двух аргументов:
Функция |
Сохраняет нуль |
Сохраняет единицу |
Самодвойст-венная |
Монотонная |
Линейная |
0 |
x |
|
|
x |
x |
|
x |
x |
|
x |
|
|
x |
|
|
|
|
|
x |
x |
x |
x |
x |
|
x |
|
|
|
|
|
x |
x |
x |
x |
x |
|
x |
|
|
|
x |
|
x |
x |
|
x |
|
|
|
|
|
|
|
|
|
x |
|
|
x |
|
|
|
x |
|
x |
|
|
x |
|
|
|
|
|
|
x |
|
x |
|
|
x |
|
|
|
|
|
|
|
|
|
1 |
|
x |
|
x |
x |
При рассмотрении таблицы можно выделить 44 функционально полных системы булевых функций: 2 – одно функциональных, 16 – двух функциональных, 23 –трех функциональных, 3 – четырех функциональных.
Система функций, которая является функционально полной, называется базисом.
Минимальным базисом называется такой базис, удаление из которого хотя бы одной функции превращает систему в неполную.
В настоящее время используются три базиса - базис Шеффера, базис Пирса и булев базис, в котором содержатся три функции И, ИЛИ, инверсия.
Заметим, что булев базис не является минимальным, т.к. из него можно удалить либо функцию И, либо функцию ИЛИ.
Аналитическая запись булевых функций в базисе Пирса.
Будем использовать следующее обозначение:
.
Вспомним
запись булевой функции в совершенной
дизъюнктивной нормальной форме:
.
Символ
означает, что дизъюнкция берется только
для таких наборов
на которых функция равна единице:
.
Попробуем записать эту функцию таким
образом, чтобы оно содержало только
функции Пирса и отрицания (отрицание
также реализуется функцией Пирса:
).
Просуммируем конституенты единицы
наборов, где функция равно нулю. Мы
получили новую функцию, значения которой
противоположны исходной функции,
поэтому:
.
Но последнее выражение есть не что
иное, как функция Пирса:
.
Однако конституенты единицы представляют
собой конъюнкции переменных и от
конъюнкций нужно также избавиться. Для
этого преобразуем конституенты единицы:
.
Таким образом, алгоритм перехода от табличного задания функции к аналитической записи в базисе Пирса таков:
1) выбрать в таблице все наборы аргументов, на которых функция равна нулю;
2) аргументы каждого из этих наборов объединяются функцией Пирса. Причем, если аргумент равен 1, то он записывается с отрицанием; если – 0, то без отрицания;
3) все полученные составляющие (термы) объединяются функцией Пирса.
Пример:
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
Выбираем наборы 010, 101, 111;
,
,
;
3)
.
По аналитической записи функции можно нарисовать схему её реализующую:
Запись функций в базисе Шеффера.
Конституента нуля для набора записывается так:
.
Действительно, в силу определения
конституенты нуля
она равна нулю на этом наборе, следовательно все слагаемые в конституенте должны быть равны нулю. Отсюда следует правило, если в наборе аргумент равен единице, то в конституенту нуля он записывается с отрицанием, если нулю – без отрицания.
Известно,
что любую функцию можно записать в
совершенной конъюнктивной нормальной
форме в виде произведения конституент
нуля. Однако ее можно записать и как
инверсию функции
значения которой противоположны исходной
функции:
Символы
(
)
обозначают, что конъюнкциями связываются
конституенты нуля наборов на которых
исходная функция равна нулю (единице).
Действительно, если на наборе
функция
равна единице, то можно указать для
этого набора конституенту нуля равную
нулю на этом наборе и единице – на
остальных наборах. Конъюнкция этих
конституент представляет собой новую
функцию
равную нулю на тех наборах, где функция
равна единице, т.е.
и
.
Полученное выражение – это функция
Шеффера над конституентами нуля:
.
Для получения окончательной записи
функции преобразуем конституенты нуля:
Окончательное
представление функции:
.
Следовательно, алгоритм перехода от
таблицы истинности к аналитической
записи в базисе Шеффера таков:
Выбрать в таблице все наборы аргументов на которых функция равна единице;
Аргументы каждого из этих наборов связать операцией Шеффера, причем, если аргумент равен 1, то он записывается без отрицания, если нулю – с отрицанием.
Все полученные выражения также связываются операцией Шеффера.
Пример:
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
000, 010, 111;
,
,
;
Минимизация булевых функций.
Одну и ту же булеву функцию можно представить в виде различных логических выражений тождественных друг другу. Практический интерес имеют выражения, содержащие наименьшее число букв, т. к. они позволяют упростить устройство, реализующее эту функцию. Такие функции называют минимальными. Поскольку в настоящее время используются три базиса: булев, Пирса и Шеффера, то будем изучать методы минимизации функций в булевом базисе, когда уравнения представляются в минимальных дизъюнктивных нормальных формах (МДНФ); в булевом базисе, когда уравнения записываются в минимальных конъюнктивных нормальных формах (МКНФ); в базисе Пирса и базисе Шеффера.
Проблеме минимизации посвящено огромное число работ, известно большое число различных методов минимизации. При небольшом числе аргументов булевой функции используют диаграммы Вейча (карты Карно). Метод чрезвычайно удобен при числе аргументов не более пяти. Диаграммы Вейча – это графическое представление таблиц истинности, когда таблица размещается на торе, естественно, что при использовании таблицы используют развертку тора. При выполнении заданных формальных правил «автоматически» производится выполнение операций склеивания и поглощения, а результатом будет минимальная форма булевой функции.
В литературе описаны методы получения МДНФ и МКНФ. При необходимости получения минимальных форм в базисе Пирса или Шеффера используют тождественные преобразования МДНФ или МКНФ. Такой подход вряд ли можно считать оправданным, т.к. минимальные формы функции в базисах Пирса и Шеффера можно легко получить по тем же самым диаграммам Вейча.
Получение минимальных дизъюнктивных нормальных
форм с помощью диаграмм Вейча.
При использовании диаграмм Вейча строится прямоугольная таблица (развертка тора), число клеток которой равно числу возможных наборов аргументов. Каждой клетке этой таблицы соответствует набор аргументов и конституента единицы равная единице на этом наборе. Требуется, чтобы в соседних клетках эти конституенты отличались только одним сомножителем.
Диаграммы Вейча для функции 2 и 3 аргументов соответственно.
Для правильной разметки достаточно отводить половину таблицы под аргумент, а другую половину таблицы – под инверсию аргумента, при этом скобки на противоположных сторонах таблицы не должны совпадать! Естественно, что возможно несколько вариантов разметки одной и той же таблицы.
Диаграмма Вейча для функции четырех аргументов.
Все
клетки, которые отличаются значением
только одной переменной, являются
соседними. Для функции пяти и более
переменных эти клетки могут быть
расположены не рядом. Пример: клетке 3
соответствует конституента единицы
.
Клеткам 2, 4, 6, 27 – конституенты единицы
,
,
,
.
Все эти клетки соседние для клетки 3.
При минимизации следует руководствоваться следующими правилами:
1) Строится и размечается прямоугольная таблица, число клеток которой равно числу возможных наборов аргументов.
2) В клетки таблицы заносятся значения булевой функции. При поиске клеточки таблицы аргумент набора равный 1 берется без отрицания, а равный нулю – с отрицанием. В найденную клетку записывают значение функции.
3) Обводят контурами все 1 с соблюдением следующих правил:
- контур должен быть прямоугольным;
- внутри контура не должно быть нулей;
- при обводке следует получить минимальное число контуров максимальной площади;
- число единиц в контуре должно быть равно степени числа 2 (1, 2, 4, 8, 16,…);
- одна и та же клетка, заполненная единицей может входить в несколько контуров;
- при обводке следует учитывать, что самая верхняя и самая нижняя строки таблицы являются соседними. Соседними являются также крайний левый и крайний правый столбцы.
- количество контуров должно быть как можно меньше, а площадь контуров – как можно больше.
4)
Записывают минимальное выражение как
дизъюнкцию логических произведений,
которые описывают контура таблицы. Для
поиска логического выражения для контура
выясняют от каких аргументов он зависит.
Если все 1 контура приписаны к аргументу
,
то в логическое произведение этот
аргумент входит. Если все единицы контура
помечены инверсией аргумента, то в
произведение вписывается
.
Если в контуре есть 1, помеченные
и 1, помеченные
,
то в описание контура этот аргумент не
входит.
Минимизируемая функция должна быть задана таблицей, либо дизъюнктивной нормальной формой.
Пример:
Найти МДНФ функции
В
этом таблице три контура. Один из них
«разрезан» при развертке тора. Минимальное
выражение:
Пример: минимизировать не полностью определенную булеву функцию, заданную таблицей.
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
В
данном примере не полностью определенная
функция была доопределена таким образом,
чтобы получить минимальное число
контуров максимальной площади, что
обеспечивает наиболее простое логическое
выражение функции. Естественно, что
обведенные пустые клетки доопределены
единицами, а не обведенные – нулями.
Результат:
.
В некоторых случаях МДНФ инверсной функции проще, чем МДНФ исходной функции. Пример:
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
Минимизация булевых функции в базисе Шеффера.
Обычно, при необходимости получения минимального выражения в базисе Пирса или Шеффера функцию минимизируют в булевом базисе, а затем, используя правила де Моргана, преобразуют функцию.
Пример:
запишем функции
и
в базисе Шеффера:
;
.
Однако, ранее рассмотренные свойства операций Шеффера и Пирса позволяют записывать минимальные формы функций в базисах Шеффера и Пирса используя диаграммы Вейча.