4.6: Контрприклади (реприза)

Last updated
Save as PDF

Page ID: 65355

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Ми обговорювали докази в цьому розділі, але ви повинні мати на увазі, що зустрічні приклади також є важливою частиною логіки:

Щоб показати, що відрахування дійсний, надайте докази.
Щоб показати, що відрахування недійсний, наведемо зустрічнийприклад.

Приклад\(4.6.1\).

Показати, що таке відрахування не є дійсним:\[\exists x,(x \in A), \quad \therefore \forall x,(x \in A).\]

Подряпини. Щоб отримати уявлення про те, що відбувається, може бути корисно перевести відрахування на англійську мову. Наприклад, ми могли б використовувати ключ символізації

\(\mathcal{U}\): речі на кухонному столі

\(A\): застосовується на кухонному столі

У цій установці відрахування стає:

На кухонному столі є яблуко. Все на кухонному столі - яблуко.

Цей відрахування явно не дійсний: легко уявити ситуацію, в якій одна річ на кухонному столі - яблуко, а щось інше на кухонному столі - це не яблуко.

Щоб знайти офіційне рішення, зробимо щось аналогічне, але використовуючи позначення First-Order Logic, замість того, щоб говорити про яблуках і стільницях. Для того щоб побудувати контрприклад, ми хочемо, щоб гіпотеза вирахування була правдивою, а висновок - помилковим.

Щоб гіпотеза\(\exists x,(x \in A)\) була правдивою, нам потрібно щось бути елементом\(A\). Наприклад, ми могли б дозволити\(1 \in A\).
Щоб зробити висновок\(\forall x,(x \in A)\) помилковим, ми хочемо, щоб його заперечення було правдою: ми\(\exists x,(x \notin A)\) хочемо бути правдою. Наприклад, ми могли б це організувати\(2 \notin A \text {. }\).

Щоб задовольнити дві вищевказані умови, дозволимо\(A =\{1\}\). Оскільки 1 і 2 є єдиними елементами, згаданими в обговоренні, ми можемо дозволити\(\mathcal{U}=\{1,2\}\). Це призводить до контрприкладу, який ми сподівалися знайти.

Рішення

Наводимо контрприклад. Нехай\[\mathcal{U}=\{1,2\} \text { and } A=\{1\}\]
тоді:\[1 \in A \text { is true, so } \exists x,(x \in A) \text { is true, so the hypothesis is true, }\]
але\[2 \notin A, \text { so } \forall x,(x \in A) \text { is false, so the conclusion is false. }\]
Оскільки у нас є ситуація, в якій гіпотеза вірна, але висновок помилковий, вирахування не є дійсним.

Приклад\(4.6.2\).

Показати, що таке відрахування не є дійсним:

Гіпотези:

\(\forall x,((x \in A) \vee(x \in B))\)
\(A \neq \varnothing\)
\(B \neq \varnothing\)

Висновок:\(\exists x,((x \in A) \&(x \in B)) .\)

Подряпини. Для того щоб побудувати контрприклад, ми хочемо, щоб всі гіпотези вирахування були правдивими і заперечення висновку було правдою. Заперечення висновку полягає в тому\[\forall x,((x \notin A) \vee(x \notin B)) ,\]
, що логічно еквівалентно\(4.6.3\)\[\forall x,((x \in A) \Rightarrow(x \notin B))\]
Now:

Щоб зробити гіпотезу 2 правдивою, ми можемо дозволити\(1 \in A\).
Щоб гіпотеза 3 була правдивою, ми повинні щось покласти в набір\(B\). Однак важливо зазначити, що (\(4.6.3\)) говорить нам\(1 \notin B\), тому ми повинні вкласти щось інше\(B\). Наприклад, ми можемо дозволити\(2 \in B\).
Тепер, після\(A\) і\(B\) були побудовані, ми можемо зробити гіпотезу 1 істинною, дозволивши\(\mathcal{U} = A \cup B\).

Щоб задовольнити всі три з цих умов, ми можемо дозволити\(A=\{1\}, B=\{2\}, \text { and } \mathcal{U}=A \cup B=\{1,2\}\).

Рішення

Наводимо контрприклад. Нехай\[\mathcal{U}=\{1,2\}, \quad A=\{1\}, \quad \text { and } \quad B=\{2\}\]
тоді:

У нас є
- \(1 \in A\)правда, так і\((1 \in A) \vee(1 \in B)\) правда, і
- \(2 \in B\)правда, так\((2 \in A) \vee(2 \in B)\) і правда.
  Оскільки 1 і 2 є єдиними елементами\(\mathcal{U}\), це означає, для кожного\(x\),\((x \in A) \vee(x \in B)\) що вірно. Так Гіпотеза 1 вірна.
\(1 \in A\), Отже\(A \neq \varnothing\). Отже, гіпотеза 2 вірна.
\(2 \in B\), Отже\(B \neq \varnothing\). Отже, гіпотеза 3 вірна.

Однак:

\(1 \notin B\), так\((1 \in A) \& (1 \in B)\) помилково, і
\(2 \notin A\), так\((2 \in A) \&(2 \in B)\) помилково.

Оскільки 1 і 2 є єдиними елементами\(\mathcal{U}\), це означає, що немає,\(x\) для чого твердження\((x \in A) \&(x \in B)\) вірно. Значить, твердження\(\exists x,((x \in A) \&(x \in B))\) помилкове; іншими словами, висновок відрахування помилковий. Оскільки у нас є ситуація, в якій гіпотеза вірна, але висновок помилковий, відрахування не є дійсним.

Приклад\(4.6.4\).

Поясніть, як ви знаєте, що таке відрахування не дійсне:\[X \cap Y \subset D, \quad \therefore X \subset Y \cup D .\]

Рішення

Наводимо контрприклад. Нехай\(X=\{1\}, Y=\{2\}, \text { and } D=\{3\}\). Тоді\(X \cap Y=\{1\} \cap\{2\}=\varnothing\), так\(X \cap Y \subset D\), тому що порожній набір є підмножиною кожного набору. Це означає, що гіпотеза вірна.

Однак,\(Y \cup D=\{2\} \cup\{3\}=\{2,3\} .\). Тому\[1 \in\{1\}=X \text { and } 1 \notin\{2,3\}=Y \cup D, \text { so } X \not \subset Y \cup D .\]
Це означає, що висновок помилковий.

Оскільки у нас є ситуація, в якій гіпотеза вірна, але висновок помилковий, відрахування не є дійсним.

Вправа\(4.6.5\).

Поясніть, як ви знаєте, що кожне з наступних відрахувань не є дійсним.

\(\exists x,(x \in A), \quad \exists x,(x \in B), \quad \therefore \exists x,((x \in A) \&(x \in B))\)
\(\forall a \in A, \exists b \in B,(a \neq b), \quad A \neq \varnothing, \quad \therefore \forall b \in B, \exists a \in A,(a \neq b)\)
\(A \neq B, \therefore A \cup B \neq A\)
\(\forall x \in A,(x \notin B), \quad \forall x \in B,(x \notin A), \therefore A \neq B \text {. }\)

Вправа\(4.6.6\).

Поясніть, як ви знаєте, що кожне з цих відрахувань не є дійсним.

\(A \cup B \subset E \cup F, \quad \therefore A \cap B \subset E \cap F\)
\(A \subset B, X \subset Y, \quad \therefore A \backslash X \subset B \backslash Y\)
\(A \cap B \neq \varnothing, B \subset C, \quad \therefore A \subset C\)
\(\exists x,((x \in P) \&(x \notin Q)), \quad \therefore \forall x,((x \in P) \Rightarrow(x \notin Q))\)
\(\forall x \in X,(x R x), \quad \therefore \forall x_{1} \in X, \forall x_{2} \in X,\left(\left(x_{1} R x_{2}\right) \Rightarrow\left(x_{2} R x_{1}\right)\right)\)

Вправа\(4.6.7\).

Визначте, чи є дійсним кожне з наступних відрахувань, і обґрунтуйте свою відповідь, надавши доказ або зустрічний приклад.

\(\exists u \in U,(u \notin V), \quad \therefore \forall u \in U,(u \notin V)\)
\(\forall x,((x \in S) \Rightarrow(1 \in T)), \quad S \neq \varnothing, \quad \therefore 1 \in T\)
\(\forall a \in A,(a \in B), \quad \forall b \in B,(b \in C), \quad \therefore \forall a \in A,(a \in C) .\)
\(D \cup E \neq \varnothing, \quad D \subset F, \quad \therefore D \cap F \neq \varnothing\)
\(\forall a_{1} \in A, \forall a_{2} \in A,\left(\left(a_{1} R a_{2}\right) \vee\left(a_{2} R a_{1}\right)\right), \quad 2 \in A, \quad \therefore 2 R 2 .\)