Контрольная работа: Булевы функции
Рассмотрим наиболее употребимые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 5.
Таблица 5
| f(х) | х | Усл. | Наименование | |
| 0 | 1 | обозн | ||
| f0 (х) | 0 | 0 | 0 | тождественный ноль (константа 0); |
| f1 (х) | 0 | 1 | х | тождественная функция |
| f2 (х) | 1 | 0 |  | отрицание х (инверсия); |
| f3 (х) | 1 | 1 | 1 | тождественная единица (константа 1). |
Функции двух переменных представлены в табл. 6.
Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов).
Отметим, что реально элементарной функции соответствует реализующий ее элемент, а суперпозиции булевых функций соответствует соединение элементов.
Таблица 6
| х1 | 0 | 0 | 1 | 1 | Наименование функции | |
| х2 | 0 | 1 | 0 | 1 | ||
| f0 (х1,х2) | 0 | 0 | 0 | 0 | константа 0 | |
| f1 (х1,х2) | 0 | 0 | 0 | 1 | конъюнкция | |
| f2 (х1,х2) | 0 | 0 | 1 | 0 | запрет по х2 | |
| f3 (х1,х2) | 0 | 0 | 1 | 1 | переменная х1 | |
| f4 (х1,х2) | 0 | 1 | 0 | 0 | запрет по х1 | |
| f5 (х1,х2) | 0 | 1 | 0 | 1 | переменная х2 | |
| f6 (х1,х2) | 0 | 1 | 1 | 0 | сумма по модулю 2 | |
| f7 (х1,х2) | 0 | 1 | 1 | 1 | дизъюнкция | |
| f8 (х1,х2) | 1 | 0 | 0 | 0 | операция Пирса (ф-ция Вебба) | |
| f9 (х1,х2) | 1 | 0 | 0 | 1 | логическая равнозначность | |
| f10 (х1,х2) | 1 | 0 | 1 | 0 | инверсия х2 | |
| f11 (х1,х2) | 1 | 0 | 1 | 1 | импликация от х2 к х1 | |
| f12 (х1,х2) | 1 | 1 | 0 | 0 | инверсия х1 | |
| f13 (х1,х2) | 1 | 1 | 0 | 1 | импликация от х1 к х2 | |
| f14 (х1,х2) | 1 | 1 | 1 | 0 | штрих Шеффера | |
| f15 (х1,х2) | 1 | 1 | 1 | 1 | константа 1 | |
Суперпозиция булевых функций представляется в виде логических формул. Однако следует отметить:
- одна и та же функция может быть представлена разными формулами;
- каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;
- между формулами представления булевых функций и схемами, их реализующими, существует взаимнооднозначное соответствие.
Очевидно, среди схем, реализующих данную функцию, есть наиболее простая. Поиск логической формулы, соответствующей этой схеме, представляет большой практический интерес, а преобразование формул булевых функций основано на использовании соотношений булевой алгебры.
4.Основные законы и тождества булевой алгебры
Для булевой алгебры определены одна одноместная (унарная) операция “отрицание” и две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются «Ù», «Ú» соответственно). Приведем некоторые основные формулы.
Под бинарной операцией на множестве А, в общем случае понимают отображение декартового произведения множеств (А х А) в множество А. Иными словами, результат применения бинарной операции к любой упорядоченной паре элементов из А есть также элемент из множества А.
Под унарной операцией на множестве А понимают выделение (фиксацию) какого-либо элемента множества А.
Преобразование формул булевых функций применением только аксиом булевой алгебры малоэффективно. Для упрощения формул используется целый ряд соотношений. Из коммутативности и ассоциативности дизъюнкции следует, что дизъюнкция нескольких переменных может выполняться последовательно, причем порядок взятия дизъюнкции не влияет на результат. Формулы де Моргана:
Следствия из формул де Моргана:
Формулы для системы функций:
операция поглощения (х поглощает у): хÚху=х; или х(хÚу)=х.
операция склеивания: хуÚх
=х, или (хÚу)Ù(хÚ)=х
5.Аналитическое представление булевых функций
Рассмотрим универсальные (канонические) формы представления, дающие возможность получить аналитическую форму непосредственно по таблице истинности для произвольной булевой функции. Эта форма в дальнейшем может быть упрощена. Поскольку между множеством аналитических представлений и множеством схем, реализующих булеву функцию, существует взаимно однозначное соответствие, отыскание канонической формы представления булевой функции является начальным этапом синтеза схемы, ее реализующей. Наиболее широкое распространение получила совершенная дизъюнктивная нормальная форма (СДНФ). Прежде чем перейти к ее изучению, приведем определение конституенты единицы — понятия, которым будем широко пользоваться в дальнейшем.
Конституентой единицы (коньюнктивным термом) называется функция f(x1,x2,...,xn), принимающая значение 1 только на единственном наборе.
Конституента единицы записывается как логическое произведение nразличных булевых переменных, некоторые из них могут быть с отрицаниями. Можно легко выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна 1.
Дизъюнкция конституент 1, равных 1 на тех же наборах, что и заданная функция, называется совершенной дизъюнктивной нормальной формой переключательной функции( СДНФ).
Наборы, на которых функция fпринимает значение 1, часто называются единичными, остальные — нулевыми наборами. Выписывать в СДНФ имеет смысл только конституенты единицы, соответствующие единичным наборам.
Пример. Выпишем СДНФ для функций, заданных таблицей истинности (табл. 7.).
|
Таблица 7.
|
fСДНФ(х1,х2,х3)=