Булевы функции одной и двух переменных

,

. */

Любая булева функция многих переменных может быть представлена логическим выражением (формулой).

/*Пример 3.2

Определение булевых функций двух переменных (3.2) дает возможность убедиться в справедливости следующих равенств

(4.1)

На основании этого можно записать следующие тождества:

(4.2)

; (4.3)

, ; (4.4)

, ; (4.5)

, ; (4.6)

, . (4.7)

С этих формул следует, что любая формула (булева функция) может быть представлена с помощью операции отрицание и любой операции из вышеперечисленных пар операций (1,0), , , , . Такие операции называются элементарными (базовыми), а их совокупность ― системой элементарных (базовых) операций.

Примером (одним из важнейших) систем элементарных операций есть

(4.8)

Эта система элементарных операций ― избыточна. Это следует из истинности равенств

, (4.9)

, (4.10)

Эти равенства доказываются с использованием таблицы истинности:

Из равенств (4.9) и (4.10) следует, что систему элементарных операций (4.8) можно сократить, например, к системе:

( (4.11)

Система элементарных операций (4.11) очень удобна и широко используется на практике. Она избыточна, так как

, (4.12)

, (4.13)

и поэтому ее можно сократить до

(4.14а)

или

. (4.14б)

Однако, и эти системы избыточны, если учесть тождества

, (4.15)

, (4.16)

. (4.17)

С этих формул следует, что системы (4.14а) и (4.14б) можно сократить до одной операции:

(4.18)

или

. (4.19)

Впрочем, особенного практического значения это не имеет.

При вычислениях значений формул с операциями (4.8) следует учитывать их приоритеты:

– отрицание ;

– конъюнкция ;

– дизъюнкция

– импликация

– эквивалентность

(сначала выполняются операции с меньшим номером в этом списке ― операции с большим приоритетом).

Порядок выполнения логических операций, противоречащий их приоритетам, устанавливается круглыми скобками.

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

/*Пример 4.1.

Вычислить значение выражения

при , , , .

Выполнение:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. . * /

5. БУЛЕВЫ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ