Булевые функции от 1 и 2 переменных . Примеры
Рассмотрим примеры
функций алгебры логики. Данные функции
часто употребляются в математической
логике и кибернетике и играют такую же
роль, как, например,
или
в анализе, поэтому их можно считать
"элементарными" функциями:
-
константа
0;
- константа 1;
- тождественная
функция;
- отрицание
(
читается "не
");
- конъюнкция
и
(читается "
и
"). Вместо знака & употребляется
знак ˙ или вообще знак опускается, т.
е. пишут
.
Эту функцию часто называют логическим
умножением;
- дизъюнкция
и
(читается "
или
").
Эту функцию часто называют логическим
сложением;
- импликация
и
(читается "из
следует
").
Эту функцию часто называют логическим
следованием;
- сложение
и
по mod
2;
или
-
функция Шеффера (штрих Шеффера).
функция
Пирса (стрелка Пирса).
Заметим, что
,
,
,
если
.
Представим результаты перечисленных выше операций в виде таблицы 5.
Таблица 5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
Условные обозначения логических элементов, выполняющих указанные операции:
а) б) в)
г
)
д)
е)
Р
еализация
функций формулами
Пример 1.
Пусть
-
множество "элементарных" функций.
Следующее выражение является формулами
над подмножеством
:
;
2)
- это формула, а
- символы из алфавита. Если нет скобок,
то это выражение.
Пример 2.
Пусть
функции,
соответствующие формулам из примера
1.
Формула
строится за три шага. Мы имеем следующие
подформулы:
В таблице 6
приводятся соответствующие им функции,
которые вычисляются с использованием
таблицы 5. Последний столбец определяет
функцию
Очевидно, что
Таблица 6
|
|
|
|
0 0 0 1 1 0 1 1 |
0 0 0 1 |
0 0 1 0 |
0 1 1 1 |
Таблица 7
|
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 1 1 0 0 0 0 0 |
Функцию будем строить иным путем (также вытекающим из определения). Для каждого набора
найдем
(см. таблицу 7).
Введенный язык формул удобен для записи функций алгебры логики, описывающих различные условия или высказывания.