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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Следствие 1. Если функция f(x
1
, . . . , x
n
) представлена фор-
мулой F над {¬, ∧, ∨}, то для получения двойственной формулы F
∗
,
представляющей функцию f
∗
(x
1
, . . . , x
n
), нужно в формуле F всюду
заменить ∧ на ∨ и ∨ на ∧.
Пример 9. Двойственной к f(x
1
, x
2
) = (x
1
∧ x
2
) ∨ x
1
является
f
∗
(x
1
, x
2
) = (x
1
∨ x
2
) ∧ x
1
.
Следствие 2. Если формулы F и G представляют одну и ту же
логическую функцию: F = G, то F
∗
= G
∗
.
Объединение этих двух следствий, называемое принципом двой-
ственности, позволяет почти вдвое сокращать усилия на вывод логи-
ческих тождеств.
Пример 10. Отметим несколько пар двойственных тождеств:
1) ¬(x
1
∧ x
2
) = x
1
∨ x
2
и ¬(x
1
∨ x
2
) = x
1
∧ x
2
;
2) x
1
∨ (x
1
∧ x
2
) = x
1
и x
1
∧ (x
1
∨ x
2
) = x
1
;
3) x = (x ⊕ 1) и x = (x ⇔ 0).
4. Замкнутые классы
Определение 5. Множество Σ логических функций называется
(функционально) замкнутым классом, если [Σ] = Σ.
Пример 11. Σ = Λ является замкнутым классом, в то время как
Σ = {1, ⊕} — незамкнутый класс.
Замыкание [Σ] любого множества Σ логических функций являет-
ся замкнутым классом.
Рассмотрим важнейшие замкнутые классы.
T
0
— класс всех логических функций, сохраняющих констан-
ту 0, т.е. функций f(x
1
, . . . , x
n
), для которых выполнено равенство
f(0, . . . , 0) = 0. Классу T
0
принадлежат функции 0, x, x
1
∧ x
2
,
x
1
∨ x
2
, x
1
⊕ x
2
, и не принадлежат функции 1, x . Таблицы значений
функций класса T
0
характеризуются тем, что в первой строке они со-
держат 0. Число всех функций этого класса равно |T
0
| =
1
2
·2
2
n
. Класс T
0
замкнут, поскольку если f, f
1
, . . . , f
m
∈ T
0
, то F = f(f
1
, . . . , f
m
) ∈ T
0
:
F (0, . . . , 0) = f(f
1
(0, . . . , 0), . . . , f
m
(0, . . . , 0)) = f(0, . . . , 0) = 0.
T
1
— класс всех логических функций, сохраняющих констан-
ту 1, т.е. функций f(x
1
, . . . , x
n
), для которых выполнено равенство
f(1, . . . , 1) = 1. Классу T
1
принадлежат функции 1, x, x
1
∧ x
2
,
x
1
∨ x
2
, x
1
⇔ x
2
, и не принадлежат функции 0, x. Таблицы значе-
ний функций класса T
1
характеризуются тем, что в последней строке
32

Страницы