Главная / Информатика / Полнота и замкнутость

Полнота и замкнутость

Пусть P2 – множество Всех булевых функций, М — его подмножество.

Определение 2.5. Множество М называется замкнутым, если его логическая оболочка P(M) Совпадает с ним самим; M называется полным, если P(M)= P2.

Примеры: 1) М = {0;1} P(М) = {0;1} М замкнуто и неполно;

2) М = P2 P(М) = P2 М замкнуто и полно;

3) М={} P(М) = P2 М незамкнуто и полно.

Замечание: Пусть – множество функций от N переменных, тогда .

Очевидны следующие утверждения:

1) M P(М) , M P2 ;

2) P(P(М)) = P(М), M P2;

3) M1ÍМ2 P(М1ÍP(М2), M1, M2 ÍP2 ;

4) (MМ2 и M1 полно) М2 полно;

5) (MМ2 и M2 неполно) М1 неполно.

Оставить комментарий