4.3: Заперечення

Згадайте частину символізаційного ключа Розділу\(4.1\):

\(\mathcal{U}\): Безліч всіх людей.

\(A\): Безліч всіх розлючених людей.

\(H(x)\): Безліч всіх щасливих людей.

Розглянемо ці подальші твердження:

15. Ніхто не злиться.
16. Не всі задоволені.

Твердження 15. можна перефразувати як: «Це не той випадок, що хтось злиться». (Іншими словами, «Це не так, що існує людина, яка сердита».) Це заперечення твердження про те, що існує розлючена людина, тому його можна перекласти за допомогою «не» і «існує»:\(\neg \exists x,(x \in A)\).

Важливо зауважити, що твердження 15. еквівалентно твердженню про те, що «Всі не сердиті». Це твердження можна перекласти за допомогою «для всіх» і «not»:\(\forall x, \neg (x \in A)\), або, іншими словами,\(\forall x, (x \notin A)\). Загалом:\[\neg \exists x, \mathcal{A} \text { is logically equivalent to } \forall x, \neg \mathcal{A} \text {. }\]
Це означає, що заперечення твердження «\(\exists\)» є твердженням «\(\forall\)».

Твердження 16. говорить, що це неправда, що всі щасливі. Це заперечення твердження про те, що всі задоволені, тому його можна перекласти, використовуючи «не» і «\(\forall\)»:\(\neg\forall x,(x \in H)\).

Більш того, сказати, що не всі щасливі - це те ж саме, що сказати, що хтось не щасливий. Це останнє твердження перекладається на\(\exists x, (x \notin H)\). Загалом:\[\neg \forall x, \mathcal{A} \text { is logically equivalent to } \exists x, \neg \mathcal{A} \text {. }\]
Це означає, що заперечення твердження «\(\forall\)» є твердженням «\(\exists\)».

Так само, як і для «\(\forall x\)»\(\exists x\), обмежені кількісні показники «\(\forall x \in X\)» та «\(\exists x \in X\)» змінюються між собою під запереченням:

\(\neg \forall x \in X, \mathcal{A} \text { is logically equivalent to " } \exists x \in X, \neg \mathcal{A} \text {. }\)
\(\neg \exists x \in X, \mathcal{A} \text { is logically equivalent to } " \forall x \in X, \neg \mathcal{A} \text {. }\)

Принципової різниці між цим і попереднім прикладом немає, ми просто замінили\(\mathcal{U}\) множиною\(X\).

Підсумовуючи: якщо вам потрібно звести нанівець твердження, яке починається з квантора, переключіть квантор на інший (від\(\exists\) до\(\forall\) або навпаки), а потім продовжуйте, заперечуючи залишок твердження.

Щоб виконати додаткові заперечення, ви захочете запам'ятати наступні правила з вправи\(1.7.5\):

Правила заперечення

\(\neg(A \vee B) \text { is logically equivalent to } \neg A \& \neg B \text {. }\)
\(\neg(A \& B) \text { is logically equivalent to } \neg A \vee \neg B \text {. }\)
\(\neg(A \Rightarrow B) \text { is logically equivalent to } A \& \neg B \text {. }\)
\(\neg \neg A \text { is logically equivalent to } A \text {. }\)

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

Давайте спростимо Assertion (*)\[\neg \forall s \in S,(((s \in A) \vee(s \in B)) \&((s \in C) \Rightarrow(s \notin D))) .\]
Ми приводимо\(\neg\) всередину квантора, переходячи з\(\forall\) на\(\exists\):\[\exists s \in S, \neg(((s \in A) \vee(s \in B)) \&((s \in C) \Rightarrow(s \notin D))) .\]
Тепер ми переходимо\(\&\) до\(\vee\) і застосовуємо \(\neg\)до кожного з двох термінів:\[\exists s \in S,(\neg((s \in A) \vee(s \in B)) \vee \neg((s \in C) \Rightarrow(s \notin D))) .\]
Далі сполучна\(\vee\) в лівому терміні змінюється на\(\&\) (і\(\neg\) застосовується до підтермінів), а правило заперечення\(\Rightarrow\) мається на увазі до правого терміна: \[\exists s \in S,((\neg(s \in A) \& \neg(s \in B)) \vee((s \in C) \& \neg(s \notin D))) .\]
Нарешті, ми використовуємо абревіатуру\(\notin\) в перших двох термінових і усуваємо подвійний негатив у кінцевому терміні:\[\exists s \in S,(((s \notin A) \&(s \notin B)) \vee((s \in C) \&(s \in D))) .\]
Цей кінцевий результат логічно еквівалентний Assertion (*) вище.

Рішення

Додайте сюди текст.

Ті ж принципи застосовуються і до заперечення тверджень англійською мовою.

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

Припустимо, що ми хочемо звести нанівець

«Кожній парасольці або потрібна нова ручка, або недостатньо велика».

Створюємо ключ символізації:

\(U\): Набір всіх парасольок.

\(H\): Набір всіх парасольок, яким потрібна нова ручка.

\(B\): Набір всіх парасольок, які досить великі.

Тепер ми можемо перевести твердження як\(\forall u \in U, \bigl( (u \in H) \vee (u \notin B)\bigr).\) заперечуючи це, ми щойно дізналися, що це еквівалентно\[\exists u \in U, \neg\bigl( (u \in H) \vee (u \notin B)\bigr),\]
якому можна спростити\[\exists u \in U, \bigl((u \notin H) \& \neg(u \notin B)\bigr),\]
і, нарешті, усуваючи подвійний негатив, це еквівалентно\[\neg\forall u \in U, \bigl( (u \in H) \vee (u \notin B)\bigr).\]
\[\exists u \in U, \bigl((u \notin H) \& (u \in B)\bigr).\]
Тепер перекладемо назад на англійську:

«Є парасолька, яка не потребує нової ручки і досить велика».

Систематичне застосування цих правил дозволить вам спростити заперечення будь-якого твердження (незалежно від того, виражено воно англійською або в).

Англійська мова більш відкрита для тлумачення та неточності, ніж. Тому, коли нам потрібно заперечити англійське твердження в цій главі, ми переводимо його на, виконуємо заперечення і переводимо назад. Вас також очікують зробити це. Пізніше, коли ви робите докази, ви можете працювати безпосередньо з англомовною версією, хоча вам може знадобитися пам'ятати про цю версію.

Попередження.

Щоб зробити твердження, квантори повинні бути застосовані до предикатів - вони не можуть стояти самі по собі. Тобто твердження має бути форми\(\exists x \in X, P(x)\) або\(\forall x\in X, P(x)\), а не просто\(\exists x\in X\) або\(\forall x \in X\). Наприклад, деякі студенти помилково намагаються перевести твердження «існує парасолька», як але це не твердження. Проблема полягає в тому, що це не повне речення: воно перекладається англійською мовою як «існує парасолька, така, що». (Зверніть увагу на «такий, що» залишив бовтатися в кінці.)

Один із способів отримати правильну символізацію - перефразувати оригінальне твердження як: «існує щось, що є парасолькою». Це перекладається на те\(\exists x, (x \in U)\), що є правильною символікою. Його заперечення спрощує\(\forall x, (x \notin U)\), що означає «кожна річ, яка існує, не є парасолькою».

\(\exists u \in U\)Якби було твердженням, то, застосовуючи правила заперечення, його заперечення було б «»\(\forall u \in U, \neg\), що не є повним реченням: його англійський переклад - «for all\(u\) in\(U\), це неправда». Щоб уникнути таких помилок, пам'ятайте, що кожен квантор завжди повинен слідувати присудком.

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

Зведіть нанівець кожне з тверджень у Вправі\(4.2.4\). Висловлюйте свою відповідь як на мові, так і англійською (після спрощення).

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

Звести нанівець кожне з наступних тверджень (і спростити, так що не\(\neg\) застосовується до нічого, крім предикатів або змінних тверджень). Покажіть свою роботу!

1. \((L \Rightarrow \neg M) \& (M \vee N)\)
2. \(\bigl( (a \in A) \& (b \in B) \bigr) \vee (c \in C)\)
3. \(\forall a \in A, \Bigl( \bigl( (a \in P) \vee (a \in Q) \bigr) \& (a \notin R) \Bigr)\)
4. \(\forall a \in A, \Bigl( (a \in T) \Rightarrow \exists c \in C, \bigl( (c \in Q) \& ( c \mathrel{R} a) \bigr) \Bigr)\)
5. \(\forall x, \biggl( (x \in A) \& \Bigl( \exists \ell \in L, \bigl( (x \mathrel{B} \ell ) \vee (\ell \in C) \bigr) \Bigr) \biggr)\)
6. \(A \Rightarrow \Bigl( \bigl( \exists x \in X, (x \in B) \bigr) \vee \bigl( \forall e \in E, \exists d \in D, (e \mathrel{C} d) \bigr) \Bigr)\)
7. \(\forall a \in A, \exists b \in B, \exists c \in C, \forall d \in D, \Bigl( (a \mathrel{K} b) \& \bigl( (a \mathrel{Z} c) \vee (b > d) \bigr) \Bigr)\)

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

Спростіть кожне твердження. Покажіть свою роботу!

1. \(\neg \forall a \in A, \bigl( (a \in P) \vee (a \in Q) \bigr)\)
2. \(\neg \exists a \in A, \bigl( (a \in P) \& (a \in Q) \bigr)\)
3. \(\neg \forall x \in X, \exists y \in Y, \bigl( (x \in A) \& (x \mathrel{C} y) \bigr)\)
4. \(\neg \forall s \in S, \biggl( (s \in R) \Rightarrow \Bigl( \exists t \in T, \bigl( (s \neq t) \& (s \mathrel{M} t) \bigr) \Bigr) \biggr)\)

Відповідь

Додайте сюди тексти. Не видаляйте цей текст спочатку.

Зауваження\(4.3.6\).

На жаль, не існує приємного, компактного способу заперечення тверджень, пов'язаних з унікальністю. Наприклад, якщо ми хочемо сказати: «Це не так, що є унікальна людина, яка повинна гроші Хікару», ми повинні сказати, що «Або ніхто не винен гроші Хікару, або більше однієї людини повинні гроші Хікару». Це перекладається на\[(H = \emptyset) \vee \bigl(\exists h_1 \in H, (\exists h_2 \in H, h_2 \neq h_1)\bigr).\]
Загалом, якщо ви зіткнетеся з ситуацією, коли ви хочете звести нанівець твердження, яке передбачає унікальність, це гарна ідея переписати твердження, не використовуючи «»\(\exists!\). У вас не повинно виникнути труднощів заперечити це перефразоване твердження.

4.3А. Пилососна правда.

Зверніть увагу, що якщо твердження\[\exists x \in A, \neg P(x)\]
істинне (де\(A\) будь-яка множина і\(P(x)\) є будь-яким унарним присудком), то тут повинен існувати елемент\(a\)\(A\), такий, який\(P(a)\) є false. Ігноруючи останню умову (про\(P(a)\)), ми знаємо\(a \in A\), що, так\(A \neq \emptyset\). Тобто ми знаємо:\[\text { If the assertion } \exists x \in A, \neg P(x) \text { is true, then } A \neq \varnothing \text {. }\]
Отже, контрапозитив також вірний:\[\text { If } A=\varnothing, \text { then the assertion } \exists x \in A, \exists P(x) \text { is false. }\]
Отже, твердження\(\exists x \in \emptyset, \neg P(x)\) є хибним, тому його заперечення є істинним:\[\text { The assertion } \forall x \in \varnothing, P(x) \text { is true. }\]
Оскільки\(P(x)\) є довільним присудком, це означає, що будь-який твердження про всі елементи порожньої множини вірно; ми говоримо, що це пилососно вірно. Справа в тому, що в порожньому наборі немає нічого, щоб суперечити будь-якому твердженню, яке ви дбаєте про всі елементи.

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

Якщо ви скажете: «Усі люди на Марсі мають фіолетову шкіру», а людей на Марсі немає, то ви сказали правду - інакше на Марсі повинна була б бути людина (шкіра якої не фіолетова), щоб надати контрприклад.

Підсумовуючи:

будь-яке твердження про всі елементи порожнього набору пилососно вірно.

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

Які з наступних англійських тверджень є пилососно вірними (в реальному світі)?

1. Всі п'ятиплети хворіють.
2. Всі стандартні гральні карти, які пронумеровані п'ятнадцять, мають зелений колір.
3. Всі прості числа, які діляться на 12, мають 5 цифр.
4. Всі люди, які побували на Місяці, - чоловіки.
5. Всі люди, які не дихають, мертві.

Відповідь

Додайте сюди тексти. Не видаляйте цей текст спочатку.