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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Порядок перечисления наборов значений переменных в таблице
значений можно зафиксировать, если рассматривать наборы как дво-
ичные числа и располагать их порядке возрастания: 000, 001, 010, 011
и т.д. В таком случае каждая логическая функция будет задаваться
одним своим столбцом, т.е. перечислением всех своих значений на упо-
рядоченном списке наборов. Например, функция голосования будет за-
дана в виде (0,0,0,1,0,1,1,1).
Предложение 1. |Λ(n)| = 2
2
n
.
Следует из доказанной в курсе дискретной математики теоремы о
числе отображений из m-элементного множества в n-элементное, рав-
ном n
m
.
Таким образом, имеется несколько способов представления логи-
ческих функций: таблицей значений, множеством единичных наборов,
перечислением значений, логической формулой.
2. Примеры логических функций
Рассмотрим логические функции от 0, 1 и 2 переменных.
a) n = 0 , |Λ(0)| = 2. Две нульарные логические функции — это
функции-константы: ϕ
0
= 0 и ϕ
1
= 1;
b) n = 1, |Λ(1)| = 4. Составим таблицу значений унарных логи-
ческих функций.
x f
0
f
1
f
2
f
3
0 0 0 1 1
1 0 1 0 1
Здесь f
0
и f
3
— функции-константы 0 и 1 соответственно; посколь-
ку они не зависят от переменной x, эта переменная называется несуще-
ственной. Функция f
1
— тождественная функция: f
1
(x) = x; функция
f
2
— отрицание, для нее используют ряд обозначений: x, ¬x, x
0
, ∼x;
c) n = 2, |Λ(2)| = 16. Перечислим все 16 бинарных логических
функций.
x
1
x
2
f
0
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
∧ 6⇒ : ⊕ ∨ ↓ ⇔ ⇐ ⇒ |
15

Страницы