§2. Булевы функции одной и двух переменных
В
табл. 2.1 перечислены все четыре булевы
функции одной переменной. Функции
=
0 и
=1
являются константами, т.к. не зависят
от х.
Для
и
переменная х
является фиктивной. Функция
=
х, функция
называется логическим отрицанием, она
имеет несколько общепринятых обозначений:
,
х. Отрицание
читается «не х».
В табл. 2.2 перечислены все 16 булевых функций двух переменных. Большинство логических функций двух переменных имеют собственное имя.
Таблица 2.1
х |
|
|
|
|
0 1 |
0 0 |
0 1 |
1 0 |
1 1 |
Таблица 2.2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 1 1 |
0 1 0 1 |
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 |
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.
=
0 и
=1
константы, функции с двумя фиктивными
переменными
и
.
=
,
а
=
функции, имеющие одну фиктивную
переменную. Также одну фиктивную
переменную имеют функции
=
и
=
.
2. Функция называется конъюнкцией, для неё используются следующие обозначения: , , , . Конъюнкция принимает значение 1 только в случае истинности обоих аргументов, поэтому ее называют логическим умножением. Конъюнкция читается « и ».
3. Функция называется дизъюнкцией, для неё используется следующее обозначение: . Дизъюнкция принимает истинное значение, когда хотя бы один из ее аргументов «истина»; она читается « или ».
4. Функция сложение по модулю 2. Её обозначение: . Функция =1, если и =0, если = , поэтому эту функцию иногда называют неравнозначностью или разделительным «или». Функция есть остаток от деления ( + )/2, если на логические аргументы смотреть как на двоичные числа.
5.
Функция
называется эквивалентностью; обозначается
или
.
Эквивалентность читается «
тогда и только тогда, когда
».
=1,
если
=
и
=0,
если
.
6. Функция импликация. Её обозначение ; называют посылкой импликации, следствием. Импликация «ложна» только если посылка «истина», а следствие «ложь», во всех остальных случаях она истинна. Импликация читается « если , то », «из следует ».
7. Функция стрелка Пирса. Её обозначение .
8. Функция штрих Шеффера. Её обозначение | .
Остальные функции специальных названий не имеют и, как будет показано ниже, легко выражаются через перечисленные функции.