Определение булевой функции
Определение: |
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики, англ. Boolean function) от | переменных — отображение , где — булево множество.
Элементы булева множества
и обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается , а от n переменных — . Булевы функции названы так по фамилии математика Джорджа Буля.Основные сведения
Определение: |
А́рность (англ. arity) функции — количество ее аргументов. |
Каждая булева функция арности
полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины . Число таких векторов равно . Поскольку на каждом векторе булева функция может принимать значение либо , либо , то количество всех n-арных булевых функций равно . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
Таблица истинности | |||||
---|---|---|---|---|---|
Практически все булевы функции малых арностей (
и ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).Нульарные функции
При
количество булевых функций равно , первая из них тождественно равна , а вторая . Их называют булевыми константами — тождественный нуль и тождественная единица.Унарные функции
При
число булевых функций равно .Таблица значений булевых функций от одной переменной:
Функции от одной переменной | ||||
---|---|---|---|---|
0 | ||||
1 | ||||
Сохраняет 0 | ✓ | ✓ | ||
Сохраняет 1 | ✓ | ✓ | ||
Самодвойственная | ✓ | ✓ | ||
Монотонная | ✓ | ✓ | ✓ | |
Линейная | ✓ | ✓ | ✓ | ✓ |
Названия булевых функций от одной переменной:
Обозначение | Название |
---|---|
тождественный ноль, тождественная ложь, тождественное "НЕТ" | |
тождественная функция, логическое "ДА", "YES"(англ.) | |
отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.) | |
тождественная единица, тождественная истина, тождественное "ДА", тавтология |
Бинарные функции
При
число булевых функций равно .Таблица значений булевых функций от двух переменных:
Функции от двух переменных: | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x | y | ||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Сохраняет 0 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
Сохраняет 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||
Самодвойственная | ✓ | ✓ | ✓ | ✓ | |||||||||||||
Монотонная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
Линейная | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Названия булевых функций от двух переменных:
Обозначение | Другие обозначения | Название |
---|---|---|
тождественный ноль, тождественная ложь, тождественное "НЕТ" | ||
И И | 2И, конъюнкция | |
больше, инверсия прямой импликации | ||
ДА1 | первый операнд | |
меньше, инверсия обратной импликации | ||
ДА2 | второй операнд | |
сложение по модулю 2, не равно, ксор, исключающее «или» | ||
ИЛИ ИЛИ | 2ИЛИ, дизъюнкция | |
ИЛИ-НЕ ИЛИ-НЕ | НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса | |
равенство, эквивалентность | ||
НЕ2 | отрицание (негация, инверсия) второго операнда | |
больше или равно, обратная импликация (от второго аргумента к первому) | ||
НЕ1 | отрицание (негация, инверсия) первого операнда | |
меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) | ||
И-НЕ И-НЕ | НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера | |
тождественная единица, тождественная истина, тождественное "ДА", тавтология |
Тернарные функции
При
число булевых функций равно . Некоторые из них определены в следующей таблице:Таблица истинности некоторых тернарных функций | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Названия булевых функций трех переменных:
Обозначения | Другие обозначения | Названия |
---|---|---|
3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса | ||
Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией | ||
Неравенство | ||
3-И-НЕ, штрих Шеффера | ||
И И И | 3-И, минимум | |
Равенство | ||
Тернарное сложение по модулю 2 | ||
И ИЛИ И ИЛИ И | переключатель по большинству, 3-ППБ, мажоритарный клапан | |
Разряд займа при тернарном вычитании | ||
Разряд переноса при тернарном сложении | ||
ИЛИ ИЛИ ИЛИ | 3-ИЛИ, максимум |
Представление функции формулой
Определение: |
Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula). |
Например, если
, то функция представляется в видеТождественность и двойственность
Определение: |
Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. |
Тождественность функций f и g можно записать, например, так:
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
(законы де Моргана) |
(дистрибутивность конъюнкции и дизъюнкции)
Определение: |
Функция | называется двойственной (англ. duality) функции , если .
Легко показать, что в этом равенстве
и можно поменять местами, то есть функции и двойственны друг другу. Из простейших функций двойственны друг другу константы и , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Суперпозиции
Полнота системы, критерий Поста
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций
. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
- Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Определение: |
Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов. |
Примеры ДНФ:
.
.
Конъюнктивная нормальная форма (КНФ)
Определение: |
Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. |
Пример КНФ:
Полином Жегалкина
Определение: |
Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида | и , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.
Полином Жегалкина имеет следующий вид:
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: теореме Поста является полным.
, который, в свою очередь, поПримеры:
Схемы из функциональных элементов
Определение: |
Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе 1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные); 2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса ). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса . | , в котором:
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Некоторые логические элементы:
И | ИЛИ | НЕ | Штрих Шеффера | Стрелка Пирса |
---|---|---|---|---|
![]() |
![]() |
![]() |
![]() |
![]() |
См. также
- Специальные формы КНФ
- Сокращенная и минимальная ДНФ
- Пороговая функция
- Cумматор
- Полные системы функций. Теорема Поста о полной системе функций
Источники информации
- Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
- Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
- Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
- Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
- Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
- Учебные пособия кафедры математической кибернетики ВМиК МГУ
- Булева функция — Википедия
- http://psi-logic.narod.ru/bool/bool.htm