Элементы математической логики. Фролов И.С. - 15 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

§2. Логические функции
1. Определения
Обозначим символом B двухэлементное множество {0, 1}, ко-
торое будем интерпретировать как множество логических значений:
0 = ложь, 1 = истина.
Любая функция, отображающая B
n
в B (n > 0), называется ло-
гической функцией от n переменных; т.е. логическая функция — это
функция f(x
1
, x
2
, . . . , x
n
) от аргументов x
1
, x
2
, . . . , x
n
∈ B, принимаю-
щая значения из B. Число n называется арностью (или местностью)
функции f. Множество всех логических функций от n переменных обо-
значим Λ(n), множество всех логических функций от любого числа пе-
ременных — Λ. Множество B вместе с заданными на нем функциями
из Λ иногда называется алгеброй логики.
Вместо двухэлементного множества B можно рассматривать k-элементное
множество {0, 1, . . . , k −1} — в этом случае говорят о k-значных логических функ-
циях и о k-значной логике.
Всякая логическая функция может быть задана таблицей значе-
ний: если функция зависит от n переменных, то в левой части этой
таблицы необходимо записать 2
n
различных наборов значений пере-
менных.
Пример 1. Пусть g(x
1
, x
2
, x
3
) — функция голосования (решение
принимается, если большинство из 3 голосов «за»). Построим соответ-
ствующую ей таблицу значений.
x
1
x
2
x
3
g(x
1
, x
2
, x
3
)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Наборы значений переменных, на которых функция принима-
ет значение 1, называются единичными наборами, а те наборы, на
которых функция принимает значение 0, — нулевыми наборами. В
приведенном выше примере единичные наборы образуют множество
{(0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.
14

Страницы