Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 33 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

33
Тема. Полнота и замкнутость систем логических функций.
8. Основные определения. Основные замкнутые классы.
Основные определения.
Определение. Система функций {f
1
,f
2
,…,f
n
} из P
2
называется
функционально полной,
если любая логическая функция может
быть записана в виде формулы через функции этой системы.
Примеры полных систем:
а)
P
2
- полная система,
б) система
{
⎤
,
∨
,
∧
} - полная система.
Не каждая система является полной. Так
{0,1} не является,
очевидно, полной.
Теорема 8.1
. Пусть даны две системы функций из P
2
:
F={f
1
,…,f
n
},
G={g
1
,…,g
m
}.
Пусть система F -полна и каждая ее функция выражается в виде
формулы через функции системы
G. Тогда система G -полна.
Доказательство.
Пусть h -произвольная функция из P
2
. В силу
полноты
F ее можно представить в виде h=u(f
1
,…,f
n
). По условию
теоремы
f
1
=u
1
(g
1
,…,g
m
)
…………………
f
n
=u
n
(g
1
,…,g
m
)
Тогда h=u(f
1
,…,f
n
)=u(u
1
(g
1
,…,g
m
),…,u
n
(g
1
,…,g
m
))=u
′
(g
1
,…,g
m
).
Из теоремы, например, вытекает:
а) система
{
⎤
,
∨
} является полной, что следует из полноты
системы
{
⎤
,
∨
,
∧
} и равенства
1212
x
xxx∨=
б) система
{
⎤
,
∧
} является полной, что может быть доказано
либо аналогично предыдущему, либо через принцип
двойственности.
Определение.
Пусть F- некоторое подмножество функций из P
2
.
Замыканием
F называется множество всех логических функций,
представляемых в виде формул через функции из
F.
Замыкание множества
F обозначается через [F].
Примеры замыканий:

Страницы