Задался целью доказать все основные тождества булевой алгебры. В качестве примера взял рассмотренное в видео и в лекции доказательство тождества № 3: A ∪ (B ⋂ C) = (A ∪ B) ⋂ (A ∪ C) (дистрибутивность ∪ относительно ⋂).
Не могу понять следующего логического шага в этом примере:
x ∈ A ∪ B и x ∈ A ∪ C ⇒ x ∈ A или x ∈ B и x ∈ C
Объясните, пожалуйста, доступным языком, почему одно является следствием другого? Мне кажется, что выполненное здесь преобразование как раз и является тождеством № 3, которое требуется доказать. Если это так, то разве такое действие допустимо в доказательстве?
Ещё один вопрос касательно доказательства тождеств, в которых встречается пустое множество. Возьмём, например, тождество № 5' (A ⋂ ¬A = ∅). При попытке его доказать мой ход мыслей таков:
Пусть x ∈ A ⋂ ¬A. Тогда x ∈ A и x ∈ ¬A ⇒ x ∈ ∅.
Но x не может принадлежать пустому множеству, так как пустому множеству не принадлежит ни один элемент!
К похожим ситуациям я прихожу в доказательствах тождеств № 4 (A ∪ ∅ = A) и № 7' (A ⋂ ∅ = ∅). В тождестве № 4 эту ситуацию получилось обойти, просто потому, что там получается x ∈ A или x ∈ ∅, и второй вариант просто отбрасывается из-за его невозможности, и остаётся x ∈ A. Как можно обойти эту проблему в тождествах № 5' и № 7'?
Тождество 5’
x ∈ (A ⋂ ¬A) -> (x ∈ A) ⋂ (x ∈ ¬A), т.е. (x ∈ A) ⋂ (x ∉ A) – получаем тождественно ложное высказывание. Оно равносильно другому тождественно ложному высказыванию x ∈ ∅, поэтому A ⋂ ¬A = ∅.
Попробуйте тождество 7' доказать самостоятельно. Если не получится - пишите :-)
Если я правильно понимаю, то можно написать так:
№ 4 (A ∪ ∅ = A)
Пусть x ∈ A ∪ ∅. Тогда x ∈ A или x ∈ ∅.
Если x ∈ A, то x ∈ A. :)
Если x ∈ ∅, то x не существует, т.к. ∅ не может содержать в себе элементов.
Итак, x ∈ A или x не существует ⇒ x ∈ A.
Итак, A ∪ ∅ ⊆ A.
Пусть x ∈ A. Тогда x ∈ A ∪ ∅, т.к. x ∈ ∅ - не существует.
Итак, A ⊆ A ∪ ∅.
Итак, A ∪ ∅ = A.
№ 7' (A ⋂ ∅ = ∅)
Пусть x ∈ A ⋂ ∅. Тогда x ∈ A и ∅ ⇒ x не существует.
Итак, A ⋂ ∅ ⊆ ∅.
Пусть x ∈ ∅. Тогда x не существует.
Итак, ∅ ⊆ A ⋂ ∅, т.к. A ⋂ ∅ - не существует.
Итак, A ⋂ ∅ = ∅.
Правильно. При доказательстве 7' (первого случая) можно вместо A ⋂ ∅ ⊆ ∅ написать A ⋂ ∅ = ∅.
А попробуйте построить диаграмму Венна.
При построении диаграмм к любому из тождеств оно становится самоочевидным. Я интересуюсь не потому, что не понимаю основных булевых тождеств, а потому, что не понимаю, как их письменно, без диаграмм, доказать (и можно ли это сделать вообще).
Давайте попробуем разобраться.
Итак, если x ∈ A ∪ B и x ∈ A ∪ C, то x ∈ A или x ∈ B и x ∈ A или x ∈ С. Пользуясь тождеством 6’, вместо x ∈ A и x ∈ A, получаем x ∈ A. Следовательно, x ∈ A или x ∈ B и x ∈ С .
Что-то подсказывает мне, что нельзя просто так раскрыть скобки в данном примере так, чтобы получилось
. Мне вообще начинает казаться, что выражение
является достаточным, т.к. его легко представить и опровергнуть его нельзя.
Можно, это мы используем логическую дистрибутивность (о ней говорится более подробно в теме 3): (X∪Y) & (X∪Z) = X∪ (Y&Z)