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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

т.е. h представима формулой над Σ.
Пример 3. Рассмотрим еще несколько полных систем.
Σ
(3)
= {¬, ∧}, так как функции из полной системы Σ
(2)
предста-
вимы формулами над Σ
(3)
: x
1
∨ x
2
= x
1
∧ x
2
.
Σ
(4)
= {|}, так как x = x|x, x
1
∧ x
2
= x
1
|x
2
= (x
1
|x
2
)|(x
1
|x
2
).
Σ
(5)
= {1, ∧, ⊕}, так как x = x ⊕ 1.
Упражнение 2. Проверить, что системы функций Σ
(3)
–Σ
(5)
являются базиса-
ми, а Σ
(1)
, Σ
(2)
— нет.
2. Многочлены Жегалкина
Остановимся подробнее на базисе Σ
(5)
. Выпишем ряд эквивалент-
ностей (конъюнкцию будем обозначать как умножение):
x
1
⊕ x
2
= x
2
⊕ x
1
, x ⊕ x = 0,
x
1
⊕ (x
2
⊕ x
3
) = (x
1
⊕ x
2
) ⊕ x
3
, x ⊕ 0 = x,
x
1
(x
2
⊕ x
3
) = x
1
x
2
⊕ x
1
x
3
, x ⊕ 1 = x.
(1)
Эти тождества легко проверяются с помощью таблиц значений
или применением эквивалентных преобразований, если использовать
СДНФ для x
1
⊕ x
2
= x
1
x
2
∨ x
1
x
2
.
Упражнение 3. Произведите проверку тождеств (1) указанными способами.
Определение 3. Многочленом Жегалкина от n переменных
x
1
, . . . , x
n
называется формула вида
c
0
⊕
M
i
1
,i
2
,...,i
s
c
i
1
,i
2
,...,i
s
x
i
1
x
i
2
. . . x
i
s
, (2)
где c
0
, c
i
1
,i
2
,...,i
s
∈ {0, 1}, а суммирование ведется по всем различным
строго возрастающим наборам индексов: 1 6 i
1
< i
2
< . . . < i
s
6 n
(1 6 s 6 n).
Менее формально можно сказать, что многочлен Жегалкина име-
ет вид K
1
⊕ K
2
⊕ . . . ⊕ K
m
, где K
i
— конъюнкция неповторяемых пере-
менных или 1 (1 6 i 6 m).
Пример 4. 1, x = 1 ⊕ x, x
1
⇔ x
2
= 1 ⊕ x
1
⊕ x
2
(проверьте!),
и вообще все линейные функции представлены в форме многочлена
Жегалкина; x
1
⊕ x
1
x
2
⊕ x
2
x
3
— многочлен Жегалкина нелинейной
функции.
В выражении (2) зафиксирован порядок, в котором записываются
одночлены и в каждом одночлене переменные. Желая подчеркнуть это,
будем говорить, что многочлен Жегалкина (2) имеет стандартный вид.
29

Страницы