Составители:
Рубрика:
37
модулю 2. Остатки от деления (0 или 1), начиная с младшего по номеру
разряда, и последнее частное (1 – как старший разряд) определяют зна-
чения функции. Незаполненные вверху таблицы значения функции до-
полняются нулями.
Например, для функции f
253
(x, y, z) определим последовательность
ее булевых значений: 253/2 = 126 (остаток 1 – младший разряд); 126/2 =
63 (0); 63/2 = 31 (1); 31/2 = 15 (1); 15/2 = 7 (1); 7/2 = 3 (1); 3/2 = 1 (1).
Последовательность цифр: 1 0 1 1 1 1 1 1 (старший разряд) определяет
булевы значения заданной функции, что видно из таблицы истинности
функции для предыдущего примера.
На практике мы говорим о булевых функциях, а пишем формулы,
хотя это не одно и то же. Количество n-местных булевых функций
конечно, а количество представляющих их формул безгранично. Напри-
мер, функции для двух переменных f
8
(стрелка Пирса) и f
14
(штрих
Шеффера) можно представить двумя формулами (см. с. 15).
Тождественность соотношений A (x, y, z, …) = B (x, y, z, …) для формул,
представляющих одну и ту же булеву функцию, можно доказать или
опровергнуть построением таблиц истинности для формул А и В и
проверкой совпадений или несовпадений значений этих представле-
ний на всех наборах значений переменных x, y, z, …. Это общий алго-
ритм проверки любых тождественных соотношений в булевой алгебре,
поскольку ввиду конечности числа наборов значений для любого ко-
нечного множества булевых переменных описанная процедура всегда
заканчивается через конечное число шагов.
На практике тождественность формул доказывается аналитически пу-
тем приведения их к ДНФ с помощью правил булевой алгебры, суперпози-
ции (т.е. замены одних формул другими равносильными формулами со-
гласно таблицам булевых функций одной и двух переменных (табл. 1 и 2)),
эквивалентных преобразований и минимизации формул (1–22).
Пример. Рассмотрим функцию предыдущего примера. Из табл. 6
видно, что она содержит одну конституенту 0 вида:
,
xyz
∨∨
т. е.
функцию можно представить следующей формулой
(,,)
.
fxyz x y
z
=∨∨
Докажем аналитически тождественность двух формул представле-
ния функции:
