Проверка соотношения подмножеств

[timber]

Цитата:

$C \subset A \wedge C \subset B \stackrel{\textrm{def}}{\Leftrightarrow} (\forall x) (x \in C \to x \in A) \wedge (\forall x)(x \in C \to x \in B) \Leftrightarrow (\forall x)(\overline{x \in C} \vee (x \in A \wedge x \in B)) \Leftrightarrow (\forall x)(x \in C \to (x \in A \wedge x \in B)) \stackrel{\textrm{def}}{\Leftrightarrow} C \subset (A \cap B) $

Не понимаю зачем нужен дополнительный переход:

$\begin{array}{l} (\forall x) (x \in C \to x \in A) \wedge (\forall x)(x \in C \to x \in B) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg (x \in C) \vee (x \in A \wedge x \in B)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(x \in C \to (x \in A \wedge x \in B)) \end{array}$

Почему сразу нельзя записать:

$\begin{array}{l} (\forall x) (x \in C \to x \in A) \wedge (\forall x)(x \in C \to x \in B) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(x \in C \to (x \in A \wedge x \in B)) \end{array}$

[kernel1983]

timber в сообщении #1120719 писал(а):

Почему сразу нельзя записать:

Можно. Если Вы знаете, что квантор общности и импликация дистрибутивны относительно конъюнкции.

[Someone]

gefest_md в сообщении #1120644 писал(а):

$C$ является собственным подмножеством $A$

Если мы интерпретируем значок "$\subset$" как собственное включение, то есть, если $C\subset A$ означает, кроме всего прочего, что $C\neq A$, то импликация $C\subset A\wedge C\subset B\Rightarrow C\subset A\cap B$ может оказаться ложной.
Если же мы этот значок интерпретируем как просто включение, то импликация будет истинной и без условия $C\neq A$. И даже если $A\cap B=\varnothing$.

[timber]

С вашей помощью начинает что-то проясняться. Спасибо за советы!
Посмотрел в учебнике В.И. Игошина, там на стр.42 перечисляются основные теоремы равносильности, которые получены из соответствующих тавтологий, которые в свою очередь определяются с помощью таблиц истинности. Выходит, что без них (таблиц) никуда. Получается, что таблицы (понятно, что не сами таблицы, а табличные результаты) -- это в каком то смысле основа проверки всей логики, а далее идут готовые формулы, которые необходимо либо заучивать наизусть и применять, веря на слово в других доказательствах, в частности при построении цепочки равносильностей, либо опять таки перепроверять (если не уверен в самих формулах/правилах) с помощью таблиц истинности.

-- 04.05.2016, 02:33 --

Для закрепления. Подскажите, пожалуйста, а это верно?

$\begin{array}{l} (A \subset C) \wedge (B \subset C) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x) (x \in A \to x \in C) \wedge (\forall x)(x \in B \to x \in C) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg (x \in A) \vee (x \in C)) \wedge (\forall x) (\neg (x \in B) \vee (x \in C)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg (x \in A) \wedge \neg (x \in B) \vee (x \in C)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg ((x \in A) \vee (x \in B)) \wedge (x \in C)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x) ((x \in A \vee x \in B) \to x \in C) \Leftrightarrow\, \\ \,\Leftrightarrow\, (A \cup B) \subset C \end{array}$

[kernel1983]

timber в сообщении #1120741 писал(а):

формулы, которые необходимо либо заучивать наизусть

Что касается формул (точнее, тавтолологий) логики высказываний и логики предикатов, то для равносильных преобразований нужно около трёх-четырёх десятков формул (штук двадцать из логики высказываний и штук пятнадцать из логики предикатов).

-- 04.05.2016, 12:13 --

timber в сообщении #1120741 писал(а):

а это верно?

Результат - да. А ход доказательства, по-моему, - не очень (третью строчку с конца посмотрите).

[timber]

kernel1983 в сообщении #1120858 писал(а):

Результат - да. А ход доказательства, по-моему, - не очень (третью строчку с конца посмотрите).

Я спрашивал про верность хода доказательства.
Согласен. Там конечно же будет такое выражение: (\forall x)(\neg ((x \in A) \wedge (x \in B)) \vee (x \in C)).
Ну а кроме этого, все верно?

[kernel1983]

timber в сообщении #1120929 писал(а):

Там конечно же будет такое выражение

У Вас конъюнкция вместо дизъюнкции.

[gefest_md]

Someone в сообщении #1120732 писал(а):

Если же мы этот значок интерпретируем как просто включение

Я это же и имел в виду на четвёртой странице, рассуждая по поводу $C\subset A$ и $C\subset B$. Но в начале забыл про пустое $C.$

ewert в сообщении #1120548 писал(а):

А если пусто?

Тогда $C\subset A\cap B.$

-- Ср май 04, 2016 20:38:50 --

(Оффтоп)

Someone в сообщении #1120732 писал(а):

импликация $C\subset A\wedge C\subset B\Rightarrow C\subset A\cap B$ может оказаться ложной

Я сам привык всегда писать $\subseteq$

[timber]

Продолжаю разбираться с задачами из Зорича, подсматривая в формулы тавтологий из Игошина.
Посмотрите еще, пожалуйста, верно ли будет построение такой цепочки равносильностей (где $C_{M}A, C_{M}B$ -- дополнения $A, B$ в $M$ соответственно):

$\begin{array}{l} (A \subset C_{M}B) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x) (x \in A \to \neg (x \in B)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg (x \in A) \vee \neg (x \in B)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(\neg (x \in B) \vee (x \in C_{M}A)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)((x \in B) \to (x \in C_{M}A)) \Leftrightarrow\, \\ \,\Leftrightarrow\, (B \subset C_{M}A) \end{array}$

[arseniiv]

Я бы предпочёл, чтобы там упоминалось и $M$. В конце концов, $C_MA = M\setminus A$. Заодно стоит упоминать в доказательстве, что $A,B\subset M$, потому что без этого ограничения штука не работает.

[timber]

Ну с $M$ вроде бы более длинная цепочка получается.
Я так сначала и начал, но по ходу стала получаться какая-то абракадабра. В итоге запутался и решил упростить доказательство.
И получилось вот именно так, как здесь написал. Поэтому и думаю, можно ли оставить так или нужно продолжать ковыряться с $M$.

[arseniiv]

timber в сообщении #1121666 писал(а):

Ну с $M$ вроде бы более длинная цепочка получается.

Зато и более правильная.

Ваше доказательство прекрасно подойдёт к утверждению $A\subset\overline B\Leftrightarrow B\subset\overline A$ о классах ($x\in\overline A\Leftrightarrow x\notin A$; классы $A$ и $\overline A$ не могут одновременно быть множествами), но тут нет. Можете для быстроты попробовать использовать характеристические функции — раз $A, B\subset M$, у них есть характеристические функции, определённые на одном и том же $M$, и учёт этого $M$, по счастью, дальше уже не понадобится.

[timber]

arseniiv, спасибо за объяснение и советы.
Только вот с методом доказательства через характеристические функции я пока что особо не знаком.
Интересно, это очень критично для дальнейшего изучения математики и в частности анализа?
Постараюсь все-таки построить цепочку с упоминанием $M$, и если получу что-то адекватное, напишу сюда, если не против.

[arseniiv]

timber в сообщении #1121709 писал(а):

Интересно, это очень критично для дальнейшего изучения математики и в частности анализа?

Я бы не описывал в таких терминах. Это, наверно, не нужно в анализе больше, чем где-то ещё, но притом это и вещь несложная.

timber в сообщении #1121709 писал(а):

напишу сюда, если не против

Не уверен, что вот так можно отвечать на вопрос, задаваемый, по идее, всем участникам темы. Я не против — ничего страшного вы, видится, не делали.

[timber]

Попробовал с характеристическими функциями.
Для составления функций пришлось в начале выполнить такие преобразования:

$\begin{array}{l} (A \subset C_{M}B) \Leftrightarrow\, (\bar{A} \cup (M \setminus B)) \end{array}$
$\begin{array}{l} (B \subset C_{M}A) \Leftrightarrow\, (\bar{B} \cup (M \setminus A)) \end{array}$

Таким образом нам нужно показать, что:
$\begin{array}{l} (\bar{A} \cup (M \setminus B)) \Leftrightarrow\, (\bar{B} \cup (M \setminus A)) \end{array}$

Для левой части получилось:
$1-\chi_{A}(x)+\chi_{A}(x)\chi_{M}(x)(1-\chi_{B}(x))$.
Правая часть:
$1-\chi_{B}(x)+\chi_{B}(x)\chi_{M}(x)(1-\chi_{A}(x))$.
Учитывая, что $\chi_{M}(x)=1$, легко проверить равенство левой и правой части.
Так можно делать или это какая-то подгонка результата?