2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Законы де Моргана
Сообщение19.04.2019, 14:24 
Здравствуйте.
Помогите, пожалуйста, с доказательством законов де Моргана для трех множеств. Не могу разобраться с первым.
Расписываю так:
$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$
?

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 14:30 
Аватара пользователя
Потому что там отрицание на $\in$ висит. Можно так: $x \notin (B \cup C) \to \neg (x \in B \cup C) \to \neg (x \in B \vee x \in C)$. А дальше нужно занести отрицание внутрь - как это сделать?

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 14:32 
Аватара пользователя
Пусть $x\notin B \wedge x\in C$.
Тогда $x\notin B \vee x\notin C$ истинно, а $x\notin(B\cup C)$ ложно.

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 15:33 
mihaild в сообщении #1388577 писал(а):
Потому что там отрицание на $\in$ висит. Можно так: $x \notin (B \cup C) \to \neg (x \in B \cup C) \to \neg (x \in B \vee x \in C)$. А дальше нужно занести отрицание внутрь - как это сделать?


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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 16:03 
Аватара пользователя
Konst24 в сообщении #1388588 писал(а):
Но не совсем понимаю, почему мы можем с квантора принадлежности перейти к отрицанию
Это не квантор, это предикатный символ. Либо вообще сокращение - просто по определению пишем $a \notin b$, подразумеваем $\neg (a \in b)$.
Konst24 в сообщении #1388588 писал(а):
отрицание ИЛИ - это два отрицания взятых как И
Ну например это закон де Моргана:)
Если хотите его доказать - то берите аксиомы и доказывайте. Либо просто напишите таблицы истинности для $\neg(a \wedge b)$ и $(\neg a) \vee (\neg b)$.

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 16:29 
mihaild в сообщении #1388596 писал(а):
Ну например это закон де Моргана:)

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

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

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

-- 19.04.2019, 20:33 --

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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 16:34 
Аватара пользователя
Konst24 в сообщении #1388599 писал(а):
То есть получается закон двойственности де Моргана доказывается через другой закон де Моргана?
Да, доказываем закон для множеств через закон для высказываний.
Konst24 в сообщении #1388599 писал(а):
Я так понимаю, что мы должны воспользоваться свойством ассоциативности операции И?
А вы напишите, какую формулу мы в итоге хотим получить (распишите $\setminus$ через $\in$ и $\notin$), скорее всего станет понятно что куда надо переносить и с чем группировать.

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 16:50 
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)$
Тогда по сути ничего не изменится. Но мы сможем перегруппировать эти высказывания и получим необходимую формулу. Но можно ли так делать..

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 17:11 
Аватара пользователя
Konst24 в сообщении #1388603 писал(а):
Но можно ли так делать

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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 17:15 
mihaild в сообщении #1388609 писал(а):
Konst24 в сообщении #1388603 писал(а):
Но можно ли так делать

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


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

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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 17:27 
Аватара пользователя
Konst24 в сообщении #1388610 писал(а):
А проверяем мы такие высказывания (правильно назвал?) через таблицы истинности? Где за аксиомы берутся несколько таблиц истинности для импликации, эквивалентности, отрицания, дизъюнкции и конъюнкции
Аксиомы и таблицы истинности - это два разных подхода (и есть две важных теоремы, дающие их эквивалентность: теорема о корректности говорит, что вывод из аксиом согласуется с таблицами истинности; теорема о полноте говорит, что всё, что согласуется с таблицами истинности, можно вывести).

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

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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 17:48 
mihaild в сообщении #1388614 писал(а):
Вообще, вам на каком уровне строгости это всё нужно? Обычно в таких доказательствах исчисление высказываний считается "уже известным".


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

 
 
 
 Re: Законы де Моргана
Сообщение19.04.2019, 18:28 
Konst24 в сообщении #1388616 писал(а):
понять что от куда берется
Ну дык нарисуйте круги Эйлера-Венна, да помедитируйте. Штука достаточно базовая, любое доказательство, как вам уже наглядно, имхо, продемонстрировано, ведёт к замкнутому кругу. Вон вам уже глобальную теорему о эквивалентности выводимости и таблиц истинности советуют... Рискну предположить, что вывод её как раз таки на правила де Моргана (среди многого прочего) опирается.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group