Булевы функции

Рассмотрим 2-х элементное множество , далее n-ю декартовую степень множества , элементами этого множества являются наборы: .

Определение. Булевой функцией называется функция, у которой как переменные, так и сама функция принимают значения из .

Таким образом, булева функция отображает . Функцию удобнее всего задать в виде таблицы:

0 0 … 0 0 0 … 1 ....... 1 1 … 0 1 1 … 1	.......

Обозначим через множество всех булевых функций (или – двухзначная логика), через – множество всех функций из , зависящих от n переменных.

Утверждение 1. | |= .

Доказательство: Это соотношение непосредственно следует из табличного построения функций.

Наборов значений переменных длины из нулей и единиц в таблице – . Для набора функция принимает значение 0 или 1. Поэтому всего количество функций – .

Примеры некоторых элементарных булевых функций:

1) Функции от одной переменной:

x	0(x)	1(x)	x

2) Функции от двух переменных:

0 0 0 1 1 0 1 1

Приведем названия этих функций.

– тождественная функция.

= x – отрицание , читается «не » или «неверно, что ».

– конъюнкция и , читается « и ».

– дизъюнкция и , читается « или ».

– сумма по модулю 2 и , читается
« плюс ».

– импликация и , читается «если , то ».

– штрих Шеффера и , читается «не или не ».

– стрелка Пирса и , читается
«не и не ».

– эквиваленция и , читается
« эквивалентно ».

Определение. Рассмотрим функцию .

1. Переменная , называется существенной для функции , если такие значения , что .

2. Переменная называется несущественной или фиктивной для функции , если она не является существенной.

Примеры:

1) В функциях переменная фиктивная.

2) В функциях переменная существенная.

3) Пусть нам дана функция f (x ₁, x ₂) = .

а) проверим на существенность, пусть , тогда , тогда по определению – существенная переменная;

б) проверим на существенность, пусть , тогда ; пусть , тогда , значит, по определению существенная.

Таким образом, в функции f (x ₁, x ₂) = обе переменные существенные.

4) В функциях , , , x ₁↓ x ₂, x ₁↔ x ₂, x ₁→ x ₂ проверить переменные на существенность самостоятельно.

Определение. Две функции и называются равными , если они отличаются друг от друга только фиктивными переменными.

Примеры:

1) ;

2) .

Замечание. В дальнейшем всюду функции рассматриваются с точностью до фиктивных переменных, т.е. если задана функция , то задана и любая равная ей функция .

Как сравнивать функции с разными переменными – рассматривать функции на наборах всех различных переменных, введя последние в данную функцию как фиктивные.

Пример:

0 0 0 1 1 0 1 1

,

.

Из таблицы видно, что .