Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 9 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

9
2. Функции алгебры логики. Примеры логических
функций
Функции алгебры логики.
Рассмотрим двухэлементное множество B=
{
0,1
}
и двоичные
переменные, принимающие значения из В. Элементы 0 и 1 не
являются числами в обычном смысле, хотя по некоторым
свойствам и похожи на них. Наиболее распространенная
интерпретация двоичных переменных - логическая: 1 - «да», 0 -
«нет» или 1 - «истина», 0 - «ложь».
Алгебра, образованная множеством В вместе со всеми
возможными операциями на
нем, называется алгеброй логики.
Функцией алгебры логики от n переменных называется n-арная
операция на В, т.е. f:B
n
→
B, где B
n
=
{
(x
1
,…,x
n
)| x
1
,…,x
n
∈
B
}
. Итак,
функция алгебры логики (или логическая функция) f(x
1
,…,x
n
) - это
функция, принимающая значения 0,1, аргументы которой
принимают значения 0,1. Множество всех логических функций
обозначаются P
2
, множество всех логических функций n
переменных – P
2
(n).
Для задания функции f(x
1
,…,x
n
) достаточно указать, какие
значения функции соответствуют каждому из наборов значений
аргументов, т.е. выписать таблицу 2.1.
Таблица 2.1
x
1
,
…
,
x
n
-
1
,
x
n
f(
x
1
,
…
,
x
n
-
1
x
n
)
0
,
…
,
0
,
0
f(
0
,
,
…
,
0
,
0
)
0
,
…
,
0
,
1
f(
0
,
…
,
0
,
1
)
0
,
…
,
1
,
0
f(
0
,
…
,
1
,
0
)
0
,
…
,
1
,
1
f(
0
,
…
,
1
,
1
)
…
1
,
…
,
1
,
1
f(
1
,
…
,
1
,
1
)
Можно видеть, что наборы n переменных принимают 2
n
различных наборов значений (Это может быть доказано по
индукции). Для удобства мы будем использовать стандартное
расположение наборов значений аргументов: если набор
рассматривать как запись числа в двоичном исчислении, то
расположение наборов соответствует естественному
расположению чисел 0,1,...,2
n
-1.
Рассмотрим представление некоторого числа b в двоичной

Страницы