2.6: Логічні квантифікатори

Вираз не\[x>5 \nonumber\] є ні істинним, ні помилковим. Насправді, ми навіть не можемо визначити його істинну цінність, якщо не знаємо цінності\(x\). Це приклад пропозіційної функції, оскільки вона поводиться як функція\(x\), вона стає пропозицією, коли присвоюється певне значення\(x\). Пропозиційні функції також називаються предикатами.

Приклад\(\PageIndex{1}\)

Позначимо супозиційну функцію «\(x > 5\)» по\(p(x)\). Ми часто пишемо\[p(x): \quad x>5. \nonumber\] Це не пропозиція, оскільки її істинна цінність не піддається вирішенню\(p(6)\), але\(p(3)\) і\(p(-1)\) є пропозиціями.

Приклад\(\PageIndex{2}\label{eg:quant-02}\)

Визначте\[q(x,y): \quad x+y=1. \nonumber\], які з нижчеперелічених є пропозиціями; які ні?

1. \(q(x,y)\)
2. \(q(x,3)\)
3. \(q(1,1)\)
4. \(q(5,-4)\)

Для тих, що є, визначають їх істинні цінності.

Відповідь

Обидва (a) і (b) не є пропозиціями, оскільки містять принаймні одну змінну. Обидва (c) і (d) є пропозиціями;\(q(1,1)\) є хибним і\(q(5,-4)\) є істинним.

практичні вправи\(\PageIndex{1}\label{he:quant-01}\)

Визначте значення істинності цих тверджень, де\(q(x,y)\) визначено в прикладі 2.6.2.

1. \(q(5,-7)\)
2. \(q(-6,7)\)
3. \(q(x+1,-x)\)

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

Визначення

Універсальна\(p(x)\) кількісна оцінка є пропозицією в будь-якій з наступних форм:

• \(p(x)\)вірно для всіх значень\(x\).
• Для всіх\(x\),\(p(x)\).
• Для кожного\(x\),\(p(x)\).
• Для кожного\(x\),\(p(x)\).
• З огляду на будь-який\(x\),\(p(x)\).

Всі вони символічно позначаються,\[\forall x \, p(x), \nonumber\] яким вимовляється як:

«для всіх\(x\)\(p(x)\)».

Символ\(\forall\) називається універсальним квантором, і може бути розширений на кілька змінних.

Приклад\(\PageIndex{3}\label{eg:quant-03}\)

Заява

«Для будь-якого реального числа\(x\) ми завжди маємо\(x^2\geq0\)»

це правда. Символічно, ми можемо написати

\[\forall x \in \mathbb{R} \, (x^2 \geq 0), \qquad\mbox{or}\qquad \forall x \, (x \in \mathbb{R} \Rightarrow x^2 \geq 0).\label{eg:forallx}\]

Друга форма трохи багатослівна, але може бути корисною в деяких ситуаціях.

Приклад\(\PageIndex{4}\label{eg:quant-04}\)

Твердження\[\forall x\in\mathbb{R}\, (x > 5) \nonumber\] є помилковим\(x\), оскільки не завжди перевищує 5. Щоб спростувати позов, досить привести тільки один контрприклад. Ми можемо використовувати\(x=4\) як контрприклад.

Однак приклади не можуть бути використані для підтвердження універсально кількісного твердження. Розглянемо твердження.\[\forall x\in\mathbb{R}\, (x^2\geq0). \nonumber\] Прямими розрахунками можна продемонструвати,\(x^2\geq0\) що вірно для багатьох\(x\) -значень. Але це не доводить, що це вірно для кожного\(x\), тому що може бути зустрічний приклад, якого ми ще не знайшли. Доводиться використовувати математичний і логічний аргумент, щоб довести твердження виду «»\(\forall x \, p(x)\).

Приклад\(\PageIndex{5}\label{eg:quant-05}\)

Заява

«Кожен студент дискретної математики взяв обчислення I та обчислення II»

явно є універсально кількісною пропозицією. Щоб висловити це в логічній формулі, ми можемо використовувати імплікацію:\[\forall x \, (x \mbox{ is a Discrete Mathematics student} \Rightarrow x \mbox{ has taken Calculus~I and Calculus~II}) \nonumber\] Альтернативою є сказати,\[\forall x \in S \, (x \mbox{ has taken Calculus~I and Calculus~II})\] де\(S\) представляє набір усіх студентів дискретної математики. Хоча друга форма виглядає простіше, ми повинні визначити, що\(S\) означає.

Визначення

Екзистенціальна кількісна оцінка\(p(x)\) приймає одну з таких форм:

• Існує\(x\) таке, що\(p(x)\).
• Для деяких\(x\),\(p(x)\).
• Є\(x\) такі, що\(p(x)\).

Пишемо, символом,\[\exists x \, p(x), \nonumber\] який вимовляється як

«Існує\(x\) таке, що»\(p(x)\).

Символ\(\exists\) називається екзистенціальним квантором. Його можна розширити на кілька змінних.

Приклад\(\PageIndex{6}\label{eg:quant-06}\)

Щоб довести, що твердження виду «\(\exists x \, p(x)\)» вірно, досить знайти приклад\(x\) такого, що\(p(x)\) є істинним. Використовуючи цей орієнтир, ви можете визначити, чи є ці дві пропозиції

1. \(\exists x\in\mathbb{R}\,(x>5)\)
2. \(\exists x\in\mathbb{R}\,(\sqrt{x}=0)\)

правдиві?

Відповідь

1. Правда. Наприклад:\(x=6\).
2. Правда. Наприклад:\(x=0\).

Приклад\(\PageIndex{7}\label{eg:quant-07}\)

Пропозиція

«Існує просте число\(x\) таке, що також\(x+2\) є простим»

це правда. Називаємо таку пару простих чисел подвійними простими числами.

практичні вправи\(\PageIndex{2}\label{he:quant-02}\)

Назвіть ще кілька прикладів подвійних простих чисел.

Приклад\(\PageIndex{8}\label{eg:quant-08}\)

Пропозиція

«Існує реальне число\(x\) таке, що\(x>5\)»

може бути виражено символічно, як\[\exists x\in\mathbb{R}\, (x>5), \qquad\mbox{or}\qquad \exists x\, (x\in\mathbb{R}\, \wedge x>5). \nonumber\] Зауважте, що в екзистенціальній кількісній оцінці ми використовуємо\(\wedge\) замість того,\(\Rightarrow\) щоб вказати, що\(x\) є дійсним числом.

практичні вправи\(\PageIndex{3}\label{he:quant-03}\)

Визначте істинну цінність кожного з наступних пропозицій:

1. Для будь-якого простого числа число\(x\)\(x+1\) є складовим. 0.4in
2. Для будь-якого простого числа число\(x>2\)\(x+1\) є складовим. 0.4in
3. Існує ціле число\(k\)\(2k+1\) таке, що парне. 0.4in
4. Для всіх цілих\(k\) чисел число\(2k\) парне. 0.4in
5. Для будь-якого дійсного числа\(x\), якщо\(x^2\) є цілим числом, то також\(x\) є цілим числом.

практичні вправи\(\PageIndex{4}\label{he:quant-04}\)

Пропозиція

«Квадрат будь-якого дійсного числа позитивний»

універсальна кількісна оцінка

«Для будь-якого дійсного числа\(x\)»\(x^2>0\).

Це правда чи брехня?

Приклад\(\PageIndex{9}\label{eg:quant-09}\)

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

1. \(\forall x \in \mathbb{Z} \; \exists y \in \mathbb{R}^* \, (xy < 1)\)
2. \(\exists y \in \mathbb{R}^* \; \forall x \in \mathbb{Z} \, (xy < 1)\)

Тут\(\mathbb{R}^*\) позначає множину всіх ненульових дійсних чисел.

Відповідь

1. Щоб довести, що твердження є істинним, ми повинні показати, що незалежно від того, з якого цілого числа\(x\) ми починаємо, ми завжди можемо знайти ненульове дійсне число\(y\) таке, що\(xy<1\). Для\(x\leq 0\), ми можемо підібрати\(y=1\), що робить\(xy=x\leq0<1\). Бо\(x>0\), нехай\(y=\frac{1}{x+1}\), тоді\(xy=\frac{x}{x+1}<1\). На цьому завершується доказ того, що перше твердження вірно.
2. Нехай\(y=1\). Чи можемо ми знайти ціле число\(x\) таке, що\(xy\mathbb{N}less 1\)? Однозначно! Наприклад, ми можемо встановити\(x=2\). Цей контрприклад показує, що друге твердження є помилковим.

практичні вправи\(\PageIndex{1}\label{he:quant-05}\)

Правда чи брехня:\(\exists y\in\mathbb{R}\, \forall x\in\mathbb{Z}\, (xy<1)\)?

Приклад\(\PageIndex{10}\label{eg:quant-10}\)

Багато теореми в математиці можуть бути виражені у вигляді кількісних тверджень. Розглянемо

«Якщо\(x\)\(y\) раціонально і нераціонально,\(x+y\) то нераціонально».

Це те саме, що сказати

«Всякий раз\(x\), коли\(y\) є раціональним і нераціональним, то\(x+y\) є ірраціональним».

Ключове слово «всякий раз» передбачає, що ми повинні використовувати універсальний квантор. \[\forall x,y\,(x\mbox{ is rational} \wedge y\mbox{ is irrational} \Rightarrow x+y\mbox{ is irrational}). \nonumber\]Він також може бути написаний як\[\forall x\in\mathbb{Q}\,\forall y\notin\mathbb{Q}\, (x+y\mbox{ is irrational}). \nonumber\] Хоча ця форма виглядає складною і здається важкою для розуміння (перш за все тому, що вона досить символічна, отже, здається абстрактною і незрозумілою для багатьох студентів), вона забезпечує легку форму для заперечення. Дивіться обговорення нижче.

Той факт, що імплікація може бути виражена як універсально кількісне твердження, звучить знайомо. Див. Приклад [наприклад: ізостриг].

Ми вивчимо кілька основних прийомів доказів у розділі 3. Деякі з них вимагають заперечення логічного твердження. Оскільки багато математичних результатів викладені як кількісні твердження, нам необхідно навчитися звести нанівець кількісну оцінку. Правило досить просте. Обмін\(\forall\) і\(\exists\), і скасовують твердження, яке кількісно оцінюється. Іншими словами,

\[\overline{\forall x\,p(x)} \equiv \exists x\,\overline{p(x)}, \qquad\mbox{and}\qquad \overline{\exists x\,p(x)} \equiv \forall x\,\overline{p(x)}. \nonumber\]

Якщо у нас є\(\forall x\in\mathbb{Z}\), ми змінюємо його лише тоді,\(\exists x \in \mathbb{Z}\) коли беремо заперечення. Його не слід зводити нанівець як\(\exists x \mathbb{N}ot\in \mathbb{Z}\). Причина полягає в тому, що ми лише заперечуємо кількісну оцінку, а не членство\(x\). В символах пишемо

\[\overline{\forall x\in\mathbb{Z}\,p(x)} \equiv \exists x\in\mathbb{Z}\,\overline{p(x)}. \nonumber\]

Аналогічним чином виходить заперечення «\(\exists x\in\mathbb{Z}\,p(x)\)».

Приклад\(\PageIndex{11}\label{eg:quant-11}\)

Ми знаходимо\[\overline{\forall x \in \mathbb{Z} \; \exists y \in \mathbb{R}^* \, (xy < 1)} \equiv \exists x\in\mathbb{Z}\; \forall y\in\mathbb{R}^*\,(xy\geq1), \nonumber\] і\[\overline{\exists y \in \mathbb{R}^* \; \forall x \in \mathbb{Z} \, (xy < 1)} \equiv \forall y\in\mathbb{R}^*\;\exists x\in\mathbb{Z}\,(xy\geq1). \nonumber\] Пам'ятаємо, що ми не змінюємо членство\(x\) і\(y\).

практичні вправи\(\PageIndex{6}\label{he:quant-06}\)

Звести нанівець пропозиції в практичній вправі 2.6.3.

Приклад\(\PageIndex{12}\label{eg:quant-12}\)

Заява

«Всі дійсні числа\(x\) задовольняють\(x^2\geq0\)»

може бути написано як, символічно,\(\forall x\in\mathbb{R} \, (x^2 \geq 0)\). Його заперечення є\(\exists x\in\mathbb{R} \, (x^2 < 0)\). На словах він говорить: «Існує дійсне число\(x\), яке задовольняє»\(x^2<0\).

практичні вправи\(\PageIndex{7}\label{he:quant-07}\)

Звести нанівець твердження

«Кожен студент дискретної математики взяв обчислення I та обчислення II».

Резюме та огляд

• Існує два способи кількісної оцінки пропозиції функції: універсальна кількісна оцінка та екзистенціальна кількісна оцінка.
• Вони пишуться у вигляді «\(\forall x\,p(x)\)» і «\(\exists x\,p(x)\)» відповідно.
• Щоб звести нанівець кількісне твердження,\(\forall\) змініть на\(\exists\), і\(\exists\) до\(\forall\), а потім звести нанівець твердження.

Вправи

Вправа\(\PageIndex{1}\label{ex:quant-01}\)

Розглянемо ці пропозіційні функції:

\(p(n)\):	\(n\)є прем'єр-міністром
\(q(n)\):	\(n\)є парним
\(r(n)\):	\(n>2\)

Висловіть ці формули словами:

1. \(\exists n\in\mathbb{Z}\,(p(n)\wedge q(n))\)
2. \(\forall n\in\mathbb{Z}\,[r(n)\Rightarrow p(n)\vee q(n)]\)
3. \(\exists n\in\mathbb{Z}\,[p(n)\wedge(q(n)\vee r(n)]\)
4. \(\forall n\in\mathbb{Z}\,[(p(n)\wedge r(n)) \Rightarrow\overline{q(n)}]\)

Вправа\(\PageIndex{2}\label{ex:quant-02}\)

Дайте формулу для кожного з наступних тверджень:

1. Для кожного парного цілого\(n\) існує ціле число\(k\) таке, що\(n=2k\).
2. Існує прямокутний трикутник\(T\), який є рівнобедреним трикутником.
3. Задано будь-який чотирикутник\(Q\), якщо\(Q\) є паралелограмом і\(Q\) має дві суміжні сторони, які перпендикулярні, то\(Q\) є прямокутником.

Вправа\(\PageIndex{3}\label{ex:quant-03}\)

Визначте, чи є ці твердження істинними чи хибними:

1. Існує парне просте ціле число.
2. Існують цілі числа\(s\) і\(t\) такі, що\(1<s<t<187\) і\(st=187\).
3. Існує\(m\) таке ціле число, що обидва\(m/2\) є цілим і, для кожного цілого\(k\), не\(m/(2k)\) є цілим числом.
4. Дано будь-які дійсні числа\(x\) і\(y\),\(x^2-2xy+y^2>0\).
5. Для кожного цілого числа\(n\) існує ціле число\(m\) таке, що\(m>n^2\).

Вправа\(\PageIndex{4}\label{ex:quant-04}\)

Визначте, чи є ці твердження істинними чи хибними:

1. Є раціональне число\(x\) таке, що\(x^2\leq0\).
2. Існує\(x\) таке число, що для кожного дійсного числа\(y\),\(xy=0\).
3. Для всіх\(x\in\mathbb{Z}\) або\(x\) парне, або\(x\) непарне.
4. Існує унікальний номер\(x\) такий, що\(x^2=1\).

Вправа\(\PageIndex{5}\label{ex:quant-05}\)

Знайдіть заперечення (в найпростішому вигляді) кожної формули.

1. \(\forall x<0\,\forall y,z\in\mathbb{R}\,(y<z \Rightarrow xy>xz)\)
2. \(\forall x\in\mathbb{Z}\,[p(x)\vee q(x)]\)
3. \(\forall x,y\in\mathbb{R}\,[p(x,y)\Rightarrow q(x,y)]\)

Вправа\(\PageIndex{6}\label{ex:quant-06}\)

Зводять нанівець такі твердження:

1. Для всіх дійсних\(x\) чисел існує\(y\) таке ціле число, яке\(p(x,y)\) передбачає\(q(x,y)\).
2. Існує раціональне число\(x\) таке, що для всіх цілих чисел\(y\),\(p(x,y)\) або\(r(x,y)\) є істинним.
3. Для всіх цілих чисел існує ціле число\(y\) таке\(x\), що якщо\(p(x,y)\) істина, то існує ціле число\(z\) так, що\(q(x,y,z)\) є істинним.

Вправа\(\PageIndex{7}\label{ex:quant-07}\)

Для кожного твердження (i) представляють його у вигляді формули, (ii) знаходять заперечення (в найпростішому вигляді) цієї формули і (iii) висловлюють заперечення словами.

1. Для всіх дійсних чисел\(x\) і\(y\),\(x+y=y+x\).
2. Для кожного позитивного дійсного числа\(x\) існує дійсне число\(y\) таке, що\(y^2=x\).
3. Існує дійсне число,\(y\) таке, що для кожного цілого числа\(x\),\(2x^2+1>x^2y\).

Вправа\(\PageIndex{8}\label{ex:quant-08}\)

Для кожного твердження (i) представляють його у вигляді формули, (ii) знаходять заперечення (в найпростішому вигляді) цієї формули і (iii) висловлюють заперечення словами.

1. Існують раціональні числа\(x_1\) і\(x_2\) такі, що\(x_1<x_2\) і\(x_1^3-x_1 > x_2^3-x_2\).
2. Для всіх дійсних чисел\(x\) і\(y\) існує ціле число\(z\) таке, що\(2z=x+y\).
3. Для всіх дійсних чисел\(x_1\) і\(x_2\), якщо\(x_1^3+x_1-2 = x_2^3+x_2-2\), то\(x_1=x_2\).

Вправа\(\PageIndex{9}\label{ex:quant-09}\)

Найпростіший спосіб звести нанівець пропозицію

«Квадрат повинен бути паралелограмом»

варто сказати

«Неправда, що квадрат повинен бути паралелограмом».

Тим не менш, це не те саме, що сказати

«Квадрат не повинен бути паралелограмом».

Чи можете ви пояснити чому? Які ще способи висловити своє заперечення словами?

Вправа\(\PageIndex{10}\label{ex:quant-10}\)

Звести нанівець ці твердження:

1. Всі квадратні числа є додатними.
2. Всі баскетболісти мають висоту понад 6 футів.
3. Жоден захисник не є під 6 футів заввишки.

1. Деякі учні можуть бути не знайомі з матрицями. Матриця являє собою прямокутний масив чисел. Матриці є важливими інструментами в математиці. Твір двох матриць відповідних розмірів визначається досить незвичайним способом. Саме своєрідний спосіб множення двох матриць робить матриці настільки корисними в математиці. Квадрат матриці, звичайно, добуток матриці з собою. Вона добре визначена тільки тоді, коли матриця є квадратною матрицею. Як виявляється, важливий порядок множення двох матриць. Іншими словами, дані будь-які дві матриці\(A\) і\(B\), це не завжди так\(AB=BA\). ↩