Математическая логика и теория алгоритмов

Замечания

Задание 1: справедливость формулы нужно доказать, не используя распределительный закон. Предполагаете, что некоторый элемент x принадлежит левой части и доказываете, что x принадлежит правой, затем наоборот. Пример доказательства тождества можно посмотреть ниже:

9. A ∪ (A ∩ B) = A.

9′. A ∩ (A ∪ B) = A.

Тождества 8 и 8′ называются законами де Моргана1, а тождества 9

и 9′ — законами поглощения.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Доказательство. Докажем тождество 3. Сначала покажем, что A∪(B∩C) есть

подмножество (A ∪ B) ∩ (A ∪ C). Действительно, если x ∈ A ∪ (B ∩ C), то x ∈ A

или x ∈ B ∩ C. Если x ∈ A, то x ∈ A ∪ B и x ∈ A ∪ C. Следовательно, x принадлежит

(A∪B)∩(A∪C). Если x ∈ B∩C, то x ∈ B и x ∈ C. Отсюда x ∈ A∪B и x ∈ A∪C, а значит,

x ∈ (A∪B)∩(A∪C). Теперь покажем, что выполнено (A∪B)∩(A∪C) ⊆ A∪(B∩C).

Если x ∈ (A ∪ B) ∩ (A ∪ C), то x ∈ A ∪ B и x ∈ A ∪ C. Следовательно, x ∈ A или x ∈ B

и x ∈ C, т. е. x ∈ B ∩ C. Отсюда x ∈ A ∪ (B ∩ C).

Докажем тождество 8. Пусть x ∈ ¬(A ∪ B). Тогда x ∈ U и x ∉ A ∪ B. Следовательно, x ∉ A и x ∉ B. Отсюда x ∈ ¬A и x ∈ ¬B, а значит, x принадлежит ¬A ∩ ¬B. Итак,

¬(A ∪ B) ⊆ ¬A ∩ ¬B. Пусть теперь x ∈ ¬A ∩ ¬B. Тогда x ∈ ¬A и x ∈ ¬B. Следовательно,

x ∈ U и x ∉ A и x ∉ B. Значит, x не принадлежит A ∪ B, т. е. x ∈ ¬(A ∪ B). Итак,

¬A ∩ ¬B ⊆ ¬(A ∪ B).

Остальные тождества доказываются аналогично. Рекомендуется сделать это

самостоятельно. Если какое-то тождество не выполняется для произвольных непустых множеств, то всегда можно построить контрпример, используя круги Эйлера.

Но оказывается с помощью диаграмм можно и доказывать.

Для этого используются частный случай кругов Эйлера — диаграммы Венна2

.

При n, равном 2 и 3, диаграммы Венна обычно изображаются в виде кругов. Пусть

даны множества A1, A2, . . ., An, n > 1. Начертим диаграмму Венна, изображающую

эти множества таким образом, чтобы все подмножества вида Y1 ∩ Y2 ∩ . . . ∩ Yn,

где Yk обозначает либо Ak

, либо ¬Ak

, были не пусты. В этом случае всевозможные комбинации Y1 ∩ Y2 ∩ . . . ∩ Yn называются составляющими системы множеств

{A1, A2, . . ., An}.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Составляющие системы множеств {A1, A2, . . ., An} задаются

следующим индуктивным определением.

Базис. Составляющие {A1} суть само A1 и его дополнение.

Шаг. Если S — составляющая {A1, A2, . . ., An−1}, то S ∩ An и S ∩

∩ ¬An — составляющие {A1, A2, . . ., An}.

Система множеств независима, если все ее составляющие не

пусты.

Задание 2: закон ассоциативности не применим для данного логического вывода, у этого закона другое название.

Задание 3,4: неверная форма записи формулы. Предикаты А и В должны иметь аргумент, в данном случае x, и знак принадлежности в формуле не понадобится. Стоит также обратить внимание на выбор логической операции в формуле.

Задание 5: путаница с переменными в решении.