Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л
4. Булевы функции
4.1. Основные понятия
Функцию
,
принимающую одно из двух значений 0 или
1, от п переменных, каждая из которых
принимает одно из двух значений 0 или
1, будем называть булевой функцией
от п переменных, называемых
пропозиционными.
Булева функция от п переменных сопоставляет каждому упорядоченному набору (кортежу), составленному из п элементов, 0 и 1, либо 1, либо 0.
Две булевы функции называются равными,
если для любых одинаковых наборов
значений переменных обе функции принимают
одинаковые значения. Булевых функций
одной переменной четыре, а двух переменных
— шестнадцать и т. д. Число булевых
функций от п переменных равно
.
Рассмотрим функции одной и двух переменных, которые называются «элементарными» функциями и с помощью которых можно определить функции большего количества переменных.
Рассмотрим таблицы истинности таких функций. В таблице, задающей булевы функции, наборы значений переменных пишут в лексикографическом порядке, который совпадает с порядком возрастания наборов, рассматриваемых как числа в двоичной системе счисления.
Таблица истинности булевой функции одной переменной:
Таблица 22.
-
x
0
0
0
1
1
1
0
1
0
1
Функции и называются константами — соответственно 0 и 1.
Функция
совпадает с переменной х и
называется тождественной
.
Функция
принимает значения, противоположные
значениям аргумента х, и называется
отрицанием х, обозначается
:
Таблица истинности булевой функции двух переменных:
Таблица 23.
x1 |
x2 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
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 |
l |
l |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
l |
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 |
Следует отметить, что здесь к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной.
1. Функции
и
представляют собой константы 0 и 1.
2. Функции
,
существенно зависят только от одной
переменной:
.
3. Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:
а) функция
и называется конъюнкцией,
б) функция
и называется дизъюнкцией,
в) функция
и называется эквивалентностью,
г)
функция
и называется суммой по модулю два, или
суммой Жегалкина,
д) функция
и называется конверсией,
е) функция
и называется импликацией,
ж) функция
и называется штрих Шеффера,
з) функция
и называется стрелкой Пирса,
и) функции
и
логически несовместимы с импликацией
и конверсией и называются функциями
запрета.
4.2. Свойства элементарных булевых функций
Для булевых функций справедливы равенства, аналогичные формулам, сформулированным для высказываний.
1. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности.
2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности.
3. Закон де Моргана:
,
.
4. Закон двойного отрицания:
=
х.
5. Выражение дизъюнкции через конъюнкцию
и суммы по модулю два:
.
6. Выражение дизъюнкции через импликацию:
.
7. Выражение отрицания через штрих
Шеффера, стрелку Пирса, сумму по модулю
два и эквивалентность:
.
8. Выражение конъюнкции через штрих
Шеффера:
9. Выражение дизъюнкции через стрелку
Пирса:
.
10. Закон поглощения:
,
.
11. Закон склеивания:
.
12. Для функций: конъюнкция, дизъюнкция и сумма по модулю два справедливы следующие тождества:
,
