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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Пример 2. Формула
F = f
2
(f
1
(x
1
, x
2
), f
3
(x
2
, f
2
(x
1
, x
3
)))
имеет подформулы f
1
(x
1
, x
2
), f
3
(x
2
, f
2
(x
1
, x
3
)), f
2
(x
1
, x
3
), x
1
, x
2
, x
3
.
Часто вместо такой функциональной записи используется ин-
фиксная запись, например, если f
1
— дизъюнкция, f
2
— циклическое
сложение, f
3
— конъюнкция, то F = (x
1
∨ x
2
) 4 (x
2
∧ (x
1
4 x
3
)) или
(x
1
+ x
2
) ⊕ (x
2
· (x
1
⊕ x
3
)).
Каждая формула представляет определенную функцию, таблицу
значений которой можно построить обычным образом. Однако пред-
ставление функции формулой неединственно, например,
стрелку Пирса можно представить
1
через функции +, ·, ¬:
x
1
↓ x
2
= x
1
+ x
2
= x
1
· x
2
;
штрих Шеффера — аналогично :
x
1
| x
2
= x
1
· x
2
= x
1
+ x
2
;
отрицание, конъюнкцию и дизъюнкцию — наоборот, через ↓ или | :
x = x ↓ x = x | x,
x
1
· x
2
= x
1
↓ x
2
= (x
1
↓ x
1
) ↓ (x
2
↓ x
2
),
x
1
+ x
2
= x
1
↓ x
2
= (x
1
↓ x
2
) ↓ (x
1
↓ x
2
).
4. Совершенная дизъюнктивная нормальная
форма
Введем обозначения x
0
= x, x
1
= x. Пусть α — параметр, равный
0 или 1. Тогда x
α
= (x ⇔ α). В частности, α
α
=1.
Теорема 1. Всякая логическая функция f(x
1
, x
2
, . . . , x
n
) может
быть представлена в виде
2
f(x
1
, . . . , x
m
, x
m+1
, . . . , x
n
) =
=
W
(α
1
,...,α
m
)
x
α
1
1
. . . x
α
m
m
f(α
1
, . . . , α
m
, x
m+1
, . . . , x
n
), (1)
где m 6 n, а дизъюнкция берется по всем 2
m
наборам значений
(α
1
, . . . , α
m
), α
i
∈ B.
1
Формулы, представляющие одну и ту же функцию, мы связываем в настоящем
параграфе знаком =.
2
Далее в этом параграфе конъюнкция обозначается как умножение, а дизъюнк-
ция как сложение.
17

Страницы