Находим пары множеств, в которых одно является подмножеством другого.

Можно ли с помощью указанных операций записать любую формулу алгебры высказываний?

 

6.6. Дизъюнкция и сложение по модулю 2 .

 

 

Решение:

Для того чтобы ответить на данный вопрос, выясним, полна ли функционально система данных функций.

 

Построим таблицу истинности для каждой функции системы. При этом обозначим дизъюнкцию как , а сложение по модулю 2 как .

 

x	y

 

 

x	y

 

Исследуем на принадлежность классам Поста:

 

Сразу видим, что и , так как . Следовательно система функций не является функционально полной, а это значит, что с помощью них нельзя записать любую формулу алгебры высказываний.

 

 

Заказать контрольную работу по дискретной математике и не только Вы можете у нас на сайте http://otl.su

 

Также посетите нашу группу Вконтакте: http://vk.com/otlsu

 

OTL.SU – Быстро, качественно, доступно!

 

Находим равные множества.

 

Как видно, равны между собой, следующие множества:

 

B=F= {-2, 2}

C=G=

Находим пары множеств, в которых одно является подмножеством другого.

 

Поскольку пустое множество является подмножеством любого множества, то множества C и G являются подмножествами всех остальных множеств.

 

C=G= - подмножества множеств A, B, D, E, F, H

Поскольку множества B и F совпадают, то они являются подмножествами друг друга.

 

и

 

Находим все подмножества множества H.

 

1-элементные подмножества: , {1}, {2}, {5,6,7}, {10}, {13}

2-элементные подмножества: {1, 2}, {1, {5, 6, 7}}, {1, 10}, {1, 13}, {2, {5, 6, 7}}, {2, 10}, {2, 13}, {{5, 6, 7}, 10}, {{5, 6, 7}, 13}, {10, 13}

3-элементные подмножества: {1, 2, {5, 6, 7}}, {1, 2, 10}, {1, 2, 13}, {1, {5, 6, 7}, 10}, {1, {5, 6, 7}, 13}, {1, 10, 13}, {2, {5, 6, 7}, 10}, {2, {5, 6, 7}, 13}, {2, 10, 13}, {{5, 6, 7}, 10, 13}

4-элементные подмножества: {1, 2, {5, 6, 7}, 10}, {1, 2, {5, 6, 7}, 13}, {2, {5, 6, 7}, 10, 13}, {1, {5, 6, 7}, 10, 13}, {1, 2, 10, 13}

5-элементные подмножества: {1, 2, {5, 6, 7}, 10, 13}

 

 

Заказать контрольную работу по дискретной математике и не только Вы можете у нас на сайте http://otl.su

 

Также посетите нашу группу Вконтакте: http://vk.com/otlsu

 

OTL.SU – Быстро, качественно, доступно!