1.3. Формульное представление булевой функции
Поскольку число
строк таблицы булевой функции
равняется
,
то уже при n
= 10 таблица становится необозримой.
Функции большого числа переменных
представляются в виде формул. Дадим
индуктивное определение формулы.
Определение.
Пусть D
= {
}
– множество функций из
.
Базис индукции.
Каждое выражение
,
где
,
называется формулой над D.
Индуктивный
переход.
Пусть
и
– выражения, являющиеся либо формулами
над D,
либо символами переменных. Тогда
выражение
– формула над D.
Пример.
Пусть D
= {
,
,
},
тогда следующие выражения являются
формулами над D:
,
(заменили
на
), ( ),
(
).
Формулы будем
обозначать заглавными буквами латинского
алфавита: A,
B,
C,…
В круглых скобках будем перечислять
переменные, участвующие в построении
формулы A
(
,
,…).
В квадратных скобках будем перечислять
функции, используемые для построения
формулы: A
[
].
Пример.
Пусть задана формула A
=
(
),
тогда A
(
,
,
)
и A
[
,
,
].
Пусть заданы две
формулы A
[
]
и B
[
],
построенные таким образом, что формула
B
может быть получена из формулы A
заменой
на
,
,
тогда формулы A
и B
имеют одинаковую структуру: A
= С [
]
и B
= C
[
],
символом C
обозначается конкретная структура
формулы. Говорят, что формула A
– суперпозиция функций
,
а сам процесс получения формулы A
из функций
называется операцией суперпозиции.
Далее будем рассматривать формулы над множеством элементарных функций. Для каждой такой формулы можно построить таблицу истинности, используя таблицы истинности элементарных функций.
Пример.
Построим таблицу истинности функции
по заданной формуле
A
=
.
Для каждого набора значений переменных
x,
y,
z
по таблицам элементарных функций
вычисляем значение формулы в целом
(табл. 1.5).
|
|
|
Таблица 1.5 |
x |
y |
z |
|
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
=
=
= 0
=
=
= 1
=
=
= 0
=
=
= 0
=
=
= 1
=
=
= 0
Разрешим опускать
внешние скобки, скобки при использовании
конъюнкции. Кроме того, разрешим опускать
знак конъюнкции. Это значит, что при
вычислении по формуле конъюнкция имеет
приоритет:
.
КАДР
1.4. Существенные и фиктивные переменные
Определение.
Булева функция
из
зависит существенным образом от аргумента
,
если существуют такие значения
переменных
,
что
.
В этом случае переменная
называется существенной, иначе
несущественной или фиктивной.
Свяжем определение существенной переменной с понятием соседних наборов.
Два набора значений переменных называются соседними по i-й переменной, если они отличаются значением этой переменной.
Переменная является существенной, если для нее найдется пара соседних наборов, на которых значения функции различны.
Пример. Пусть
задана таблица истинности функции f
(
,
,
)
(табл. 1.6).
Таблица 1.6 |
|||
|
|
|
f |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Переменная несущественная, так как для всех соседних наборов по переменной значение функции одинаково.
Алгоритм удаления фиктивной переменной.
1. Вычеркиваем все строки, содержащие значения 1 (или 0) в i-м столбце.
2. Удаляем столбец, соответствующий фиктивной переменной.
3. Оставшиеся строки переставляем, если это необходимо, для того, чтобы таблица приобрела стандартный вид.
Пример. Удалим фиктивную переменную из функции f ( , , ), результат представим в табл. 1.7.
Таблице 1.7 |
||
|
|
f |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Фиктивные переменные можно вводить в таблицу, расширяя ее.
Определение. Две булевы функции f и g называются равными, если одну из них можно получить из другой, добавляя или исключая фиктивные переменные.
Определение. Формулы называются эквивалентными, если представляемые ими функции равны.
КАДР