Законы де Моргана

[Konst24]

Здравствуйте.
Помогите, пожалуйста, с доказательством законов де Моргана для трех множеств. Не могу разобраться с первым.
Расписываю так:
$A \setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$
$(x\in A)\wedge (x\notin (B \cup C)$
Дальше возникает проблема с раскрытием не содержания $x$ в объединении. Почему мы не можем расписать, что
$x\notin B\vee x\notin C$
?

[mihaild]

Потому что там отрицание на $\in$ висит. Можно так: $x \notin (B \cup C) \to \neg (x \in B \cup C) \to \neg (x \in B \vee x \in C)$. А дальше нужно занести отрицание внутрь - как это сделать?

[svv]

Пусть $x\notin B \wedge x\in C$.
Тогда $x\notin B \vee x\notin C$ истинно, а $x\notin(B\cup C)$ ложно.

[Konst24]

mihaild в сообщении #1388577 писал(а):

Потому что там отрицание на $\in$ висит. Можно так: $x \notin (B \cup C) \to \neg (x \in B \cup C) \to \neg (x \in B \vee x \in C)$. А дальше нужно занести отрицание внутрь - как это сделать?

Как бы интуитивно понятно, что отрицание. Но не совсем понимаю, почему мы можем с квантора принадлежности перейти к отрицанию.
Дальше мы пользуемся тем, что отрицание ИЛИ - это два отрицания взятых как И. Но опять же, как это доказать.

[mihaild]

Konst24 в сообщении #1388588 писал(а):

Но не совсем понимаю, почему мы можем с квантора принадлежности перейти к отрицанию

Это не квантор, это предикатный символ. Либо вообще сокращение - просто по определению пишем $a \notin b$, подразумеваем $\neg (a \in b)$.

Konst24 в сообщении #1388588 писал(а):

отрицание ИЛИ - это два отрицания взятых как И

Ну например это закон де Моргана:)
Если хотите его доказать - то берите аксиомы и доказывайте. Либо просто напишите таблицы истинности для $\neg(a \wedge b)$ и $(\neg a) \vee (\neg b)$.

[Konst24]

mihaild в сообщении #1388596 писал(а):

Ну например это закон де Моргана:)

То есть получается закон двойственности де Моргана доказывается через другой закон де Моргана?

Тогда получаем:
$(x\in A) \wedge ((x\notin B)\wedge (x\notin C))$
Я так понимаю, что мы должны воспользоваться свойством ассоциативности операции И? Но тогда мы ничего в "кучу" не соберём..

Как же сложно, когда не хватает знаний.

-- 19.04.2019, 20:33 --

И еще, забыл уточнить. У нас же доказательство по сути сразу идёт в две стороны? Т.е. не нужно в обратную сторону доказывать?

[mihaild]

Konst24 в сообщении #1388599 писал(а):

То есть получается закон двойственности де Моргана доказывается через другой закон де Моргана?

Да, доказываем закон для множеств через закон для высказываний.

Konst24 в сообщении #1388599 писал(а):

Я так понимаю, что мы должны воспользоваться свойством ассоциативности операции И?

А вы напишите, какую формулу мы в итоге хотим получить (распишите $\setminus$ через $\in$ и $\notin$), скорее всего станет понятно что куда надо переносить и с чем группировать.

[Konst24]

mihaild в сообщении #1388600 писал(а):

А вы напишите, какую формулу мы в итоге хотим получить (распишите $\setminus$ через $\in$ и $\notin$), скорее всего станет понятно что куда надо переносить и с чем группировать.

Должны получить
$((x\in A)\wedge (x\notin B))\wedge ((x\in A)\wedge (x\notin C))$
Но у нас $(x\in A)$ всего одно. А нам нужно два. Здесь напоминает какую-то особенную дистрибутивность.

-- 19.04.2019, 21:00 --

Хотя в принципе, ничего не изменится, если мы добавим одно И с $(x\in A)$
Тогда по сути ничего не изменится. Но мы сможем перегруппировать эти высказывания и получим необходимую формулу. Но можно ли так делать..

[mihaild]

Konst24 в сообщении #1388603 писал(а):

Но можно ли так делать

Формулы $x \in A$ и $(x \in A) \wedge (x \in A)$ эквивалентны, соответственно можно подставить вторую вместо первой.

[Konst24]

mihaild в сообщении #1388609 писал(а):

Konst24 в сообщении #1388603 писал(а):

Но можно ли так делать

Формулы $x \in A$ и $(x \in A) \wedge (x \in A)$ эквивалентны, соответственно можно подставить вторую вместо первой.

Спасибо понял. А проверяем мы такие высказывания (правильно назвал?) через таблицы истинности? Где за аксиомы берутся несколько таблиц истинности для импликации, эквивалентности, отрицания, дизъюнкции и конъюнкции. И если обе части высказывания дают одинаковый результат {истина, ложь} на одинаковых входящих значениях, то высказывание верно?

Это раздел "Математическая логика" же?

[mihaild]

Konst24 в сообщении #1388610 писал(а):

А проверяем мы такие высказывания (правильно назвал?) через таблицы истинности? Где за аксиомы берутся несколько таблиц истинности для импликации, эквивалентности, отрицания, дизъюнкции и конъюнкции

Аксиомы и таблицы истинности - это два разных подхода (и есть две важных теоремы, дающие их эквивалентность: теорема о корректности говорит, что вывод из аксиом согласуется с таблицами истинности; теорема о полноте говорит, что всё, что согласуется с таблицами истинности, можно вывести).

Можно взять таблицы истинности для базовых связок, и с их использованием составлять таблицы истинности для произвольных формул исчисления высказываний. А можно взять аксиомы исчисления высказываний, и по modus ponens из них что-то выводить.
В любом случае, $P \wedge (Q \wedge R) \leftrightarrow ((P \wedge Q) \wedge (P \wedge R))$ является тавтологией исчисления высказываний. А любая формула, получающаяся подстановкой формул вместо пропозициональных переменных в тавтологию исчисления высказываний, является тавтологией исчисления предикатов.

Вообще, вам на каком уровне строгости это всё нужно? Обычно в таких доказательствах исчисление высказываний считается "уже известным".

[Konst24]

mihaild в сообщении #1388614 писал(а):

Вообще, вам на каком уровне строгости это всё нужно? Обычно в таких доказательствах исчисление высказываний считается "уже известным".

По сути нужно для изучения основ теории множеств на математическом анализе. Но надо бы понять что от куда берется, хотя бы один раз.

[iifat]

Konst24 в сообщении #1388616 писал(а):

понять что от куда берется

Ну дык нарисуйте круги Эйлера-Венна, да помедитируйте. Штука достаточно базовая, любое доказательство, как вам уже наглядно, имхо, продемонстрировано, ведёт к замкнутому кругу. Вон вам уже глобальную теорему о эквивалентности выводимости и таблиц истинности советуют... Рискну предположить, что вывод её как раз таки на правила де Моргана (среди многого прочего) опирается.