2.4: Введення в кількісну оцінку

У цьому розділі та наступному ми вводимо логіку першого порядку, яку також називають логікою предикатів, логікою кількісного визначення та численням предикатів першого порядку. Речення «x > 0» само по собі не є пропозицією, оскільки його істинне значення залежить від x, в цьому випадку ми говоримо, що x є вільною змінною. Речення з хоча б однією вільною змінною називається присудком (або відкритим реченням). Щоб перетворити присудок у пропозицію, ми повинні або замінити значення для кожної вільної змінної, або «кількісно» вільні змінні. Ми будемо використовувати такі позначення, як\(P (x)\) і\(Q(a,b)\) для представлення предикатів з вільними змінними x і a, b відповідно. Букви «P» та «Q», які ми використовували в попередньому реченні, не є особливими; ми можемо використовувати будь-яку літеру чи символ, який ми хочемо. Наприклад, кожне з наступних являє собою присудок із зазначеними вільними змінними.

• S (x) B «х2 − 4 = 0»
• Л (а, б) Б «а < б»
• F (x, y) B «х дружить з y»

Зверніть увагу, що ми використовували лапки вище, щоб усунути деяку неоднозначність. Що означало б S (x) = x ² − 4 = 0? Схоже, S (x) дорівнює 0, але насправді ми хочемо, щоб S (x) представляла ціле речення «x ² − 4 = 0». Крім того, зверніть увагу, що порядок, в якому ми використовуємо вільні змінні може мати значення. Наприклад, порівняйте L (a, b) з L (b, a).

Один із способів, яким ми можемо зробити пропозиції з предикатів, - це присвоєння конкретних значень вільним змінним. Тобто, якщо P (x) є присудком, а x0 є специфічним значенням для x, то P (x0) тепер є пропозицією, яка є або істинним, або помилковим.

Проблема 2.58. Розглянемо S (x) і L (a, b), як визначено вище. Визначте значення істинності S (0), S (−2), L (2,1) та L (−3, −2). L (2, b) є пропозицією або присудком?

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

Проблема 2.59. Обидва наступних речення є пропозиціями. Вирішіть, чи є кожен істинним чи хибним. Що б знадобилося, щоб виправдати ваші відповіді?

(а) Для всіх x R, x ² − 4 = 0.

(b) Існує x R такий, що x ² − 4 = 0.

Визначення 2.60. «Для всіх» - універсальний квантор і «існує... такий, що» є екзистенціальним квантором.

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

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

Ми повинні подбати про те, щоб вказати колекцію прийнятних значень для вільних змінних. Розглянемо пропозицію «Для всіх х, х > 0». Це речення істинне чи хибне? Відповідь залежить від того, до якого набору застосовується універсальний квантор. Звичайно, речення є помилковим, якщо ми застосовуємо його для всіх x Z. проте речення вірно для всіх x N. Контекст може вирішити неясності, але в іншому випадку ми повинні чітко написати: «Для всіх x Z, x > 0» або «Для всіх x N, x > 0». Колекція намічених значень для змінної називається всесвітом дискурсу.

Проблема 2.61. Припустимо, наш Всесвіт дискурсу - це набір цілих чисел.

(a) Наведіть приклад присудка P (x) таким чином, що «Для всіх x, P (x)» є істинним.

(b) Надайте приклад присудка Q (x) таким чином, що «Для всіх x, Q (x)» є помилковим, тоді як «Існує x такий, що Q (x)» є істинним.

Якщо присудок має більше однієї вільної змінної, то ми можемо побудувати пропозиції, кількісно оцінюючи кожну змінну. Однак порядок кількісних показників надзвичайно важливий!

Проблема 2.62. Нехай P (x, y) бути присудком з вільними змінними x і y у всесвіті дискурсу U. одним із способів кількісної оцінки змінних є «Для всіх x U існує y U такий, що P (x, y)». Як ще можна кількісно оцінити змінні?

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

Проблема 2.63. Припустимо, всесвіт дискурсу - це сукупність людей і вважають присудок M (x, y) B «х одружений на y». Ми можемо інтерпретувати формальне твердження «Для всіх х існує y таке, що M (x, y)» як означає «Кожен одружений з кимось». Тлумачити сенс кожного з наведених нижче тверджень подібним чином.

(а) Для всіх х існує y такий, що M (x, y).

(б) Існує y таке, що для всіх x, M (x, y).

(c) Для всіх х, для всіх y, M (x, y).

(d) Існує х такий, що існує y такий, що M (x, y).

Проблема 2.64. Припустимо, всесвіт дискурсу являє собою набір дійсних чисел і розглянемо присудок F (x, y) B «x = y ²». Тлумачити значення кожного з наступних тверджень.

(а) Існує х такий, що існує у такий, що F (x, y).

(б) Існує y таке, що існує х такий, що F (x, y).

(c) Для всіх y, для всіх x, F (x, y).

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

• Змінні явно пов'язані квантифікаторами в тому ж реченні.
• Змінні неявно пов'язані попередніми реченнями або контекстом. Твердження виду «Нехай x =...» і «Припустимо x...» зв'язують змінну x і прибирають неоднозначність.

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

Кількісна оцінка і логічні зв'язки («і», «або», «якщо., то.,» і «не») дозволяють складним математичним твердженням. Наприклад, якщо f є функцією, а c і L є дійсними числами, то формальне визначення lim _{x →c} f (x) = L, з яким ви могли зіткнутися в численні, таке:

Для всіх ε > 0 існує δ > 0 таке, що для всіх x, якщо 0 < |x − c| < δ, то |f (x) − L| < ε.

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

Визначення 2.65. Позначається універсальний квантор «для всіх»\(∀\), а екзистенціальний квантор «існує. такий, що»\(∃\).

Використовуючи наші скорочення для логічних зв'язків і квантифікаторів, ми можемо символічно представляти математичні пропозиції. Наприклад, (істинна) пропозиція «Існує x R така, що x2 −1 = 0» стає «(x R) (x2 −1 = 0)», тоді як (хибна) пропозиція «Для всіх x N існує y N така, що y < x» стає «(x N) (y < x) (y < x)».

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

(a) Існує х такий, що х ² + 1 більше нуля.

(b) Існує натуральне число n таке, що n ² = 36.

(c) Для кожного x x ² більше або дорівнює нулю.

Проблема 2.67. Висловіть формальне визначення межі (наведено вище Визначення 2.65) в логічних і математичних символах.

Якщо придивитися уважно, багато теорем, з якими ми стикалися до цього моменту, мали форму A (x) =⇒ B (x), де A (x) і B (x) є предикатами. Наприклад, розглянемо

Теорема 2.2, яка говорить: «Якщо n - парне ціле число, то n2 - парне ціле число». У цьому випадку «n - парне ціле число», а «n2 - парне ціле число» є обома предикатами. Отже, розумно було б припустити, що все твердження теореми є присудком. Однак стандартною практикою є інтерпретація речення A (x) =⇒ B (x) означає (x) (A (x) =⇒ B (x)) (де Всесвіт дискурсу для х повинен бути зрозумілий). Ми також можемо переробити такі заяви, щоб «приховати» підтекст. Зокрема, (x) (A (x) =⇒ B (x)) має те саме значення, що і (x ⟩ U0) B (x), де U0 - колекція предметів з Всесвіту дискурсу U, що робить A (x) істинним. Наприклад, ми могли б переписати твердження теореми 2.2 як «Для кожного парного цілого числа n n, n ² парне».

Проблема 2.68. Переформуйте теорему 2.7, щоб вона явно читалася як універсально кількісне твердження. Порівняти з проблемою 2.47.

Проблема 2.69. Знайдіть як мінімум два інших екземпляри теоремних тверджень, які з'явилися раніше в книзі і записані у вигляді A (x) =⇒ B (x). Перепишіть кожен еквівалентним чином, що робить універсальний квантор явним, можливо, пригнічуючи імплікацію.

Проблема 2.70. Розглянемо пропозицію «Якщо ε > 0, то існує N N таке, що 1/N < ε». Припустимо, всесвіт дискурсу - це набір R.

(а) Висловити твердження логічними та математичними символами. Чи вірно твердження?

(b) Зворотний порядок кількісних показників, щоб отримати новий оператор. Чи змінюється сенс? Якщо так, то як? Чи вірно нове твердження?

Символічний вираз (x) (y) може бути скорочено до тих\(∀x,y\) пір, поки x і y є елементами одного Всесвіту.

Проблема 2.71. Висловіть пропозицію «Для всіх x, y ⟩ R з x < y існує m θ R такий, що x < m < y», використовуючи логічні та математичні символи.

Проблема 2.72. Перепишіть кожне з наступних пропозицій словами і визначте, чи є пропозиція істинним чи хибним.

(а) (n ÷ N) (n ² ≥ 5)

(б) (n ÷ N) (n ² − 1 = 0)

(c) (N N) (n > N) (\(\dfrac{1}{n}\)< 0,01)

(d) (м, n ÷ Z) ((2|м 2|п) =⇒ 2| (м + п))

(е) (х ÷ N) (y ÷ N) (x − 2y = 0)

(f) (x ÷ N) (y ‰ N) (y ≤ х)

Проблема 2.73. Розглянемо пропозицію (x) (y) (xy = 1).

(а) Наведіть приклад всесвіту дискурсу, де ця пропозиція є істинною.

(б) Наведіть приклад всесвіту дискурсу, де ця пропозиція є помилковою.

Щоб підігріти апетит до наступного розділу, подумайте, як ви могли б довести справжню пропозицію форми «Для всіх х.» Якщо судження помилкове, то його заперечення істинно. Як би ви йшли про заперечення заяви, що включає кількісні показники?