Основы дискретной математики. Щипцов В.В - 18 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

18
виде таблицы с 2
n
строками, так как это сделано в нижеследующем примере для
булевой функции от трех аргументов (табл.4).
Таблица 4
x
1
x
2
x
3
f(x
1
, x
2
, x
3
) Аналогично тому, как символы 0 и 1
0 0 0 1 отождествляются с ложным и истин
0 0 1 0 ным высказыванием, так и табл.4
0 1 0 0 представляет собой таблицу, опреде-
0 1 1 0 ляющую ложность и истинность сло-
1 0 0 1 жного высказывания f(x
1
, x
2
, x
3
) в
1 0 1 0 зависимости от истинности и ложно-
1 1 0 1 сти высказываний x
1
, x
2
, x
3
.
1 1 1 1
Заметим, что так как каждому набору аргументов ( x
1
, x
2
, ... , x
n
) может
быть сопоставлено только два значения функции: 0 или 1, то число различных
булевых функций, зависящих от n аргументов, равно
n
(
)
.
2
2
Две булевых функции f(x
1
,x
2
,... ,x
n
) и ϕ(x
1
, x
2
,...,x
n
) называются равными,
если на всех возможных наборах значений аргументов они принимают
одинаковые значения, т.е.
f(x
1
, x
2
,...,x
n
) = ϕ(x
1
, x
2
,...,х
n
).
Говорят, что булева функция f(x
1
,x
2
,...,x
n
) существенно зависит от
аргумента x
i
, если найдется хотя бы один такой набор значений
x
1
, x
2
,..., x
i-1
, x
i+1
,...,x
n
, для которого имеет место соотношение
f(x
1
, x
2
, ... , x
i-1
,0, x
i+1
, ... , x
n
) ≠ f(x
1
, x
2
, ... , x
i-1
,1, x
i+1
, ... , x
n
).
В противном случае говорят, что функция f зависит несущественно от x
i
,
или что x
i
есть фиктивный аргумент. Ясно, что булева функция не изменится,
если к множеству ее аргументов добавить или выбросить любое число
фиктивных аргументов.
Функции алгебры логики широко используются в приложениях. Любая
ЭВМ, значительная часть автоматических устройств, включают в себя, как
правило, двухпозиционные элементы, о которых речь шла выше. Соединенные
между собой определенным образом, эти элементы, которым соответствуют
двоичные переменные x
1
, x
2
, ... ,x
n
, в процессе работы устройства формируют
на выходе сигнал, представляющий собой не что иное, как булеву функцию
f(x
1
, x
2
, ... ,x
n
), значения которой зависят от значений сигналов x
1
, x
2
, ... ,x
n
,
подаваемых на вход.
§ 2.3. Элементарные функции. Сложные функции
Подобно тому, как построение “обычной” математики начинается с
основных элементарных операций, так и в алгебре логики вначале определяют
некоторые исходные логические операции над высказываниями или, так
называемые, элементарные функции
алгебры логики. К их числу относятся:

Страницы