2.2: Вступ до логіки

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

Визначення 2.16. Пропозиція - це речення, яке є істинним або хибним, але ніколи не обидва. Істинне значення (або логічне значення) пропозиції посилається на його атрибут бути істинним чи хибним.

Наприклад, пропозиція «У всіх собак чотири ноги» - помилкове судження. Однак цілком гарне речення «x = 1» не є пропозицією сама по собі, оскільки ми насправді не знаємо, що таке х.

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

(а) Всі автомобілі червоного кольору.

(б) Кожна людина, чиє ім'я починається на J, має ім'я Джо.

(в) х ² = 4.

(г) Існує дійсне число х таке, що х ² = 4.

(e) Для всіх дійсних чисел x, x ² = 4.

(f) √2 - ірраціональне число.

(g) p є простим.

(h) Йде дощ?

(i) Завтра буде дощ

(j) Led Zeppelin - найкраща група всіх часів.

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

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

Визначення 2.18. Нехай A і B будуть пропозиціями.

(а) Пропозиція «не А» є істинною, якщо A є помилковою; виражається символічно як\(¬A\) і називається запереченням А.

(b) Пропозиція «A і B» є істинною, якщо і A, і B є істинними; виражається символічно як\(A∧B\) і називається сполученням A і B.

(c) Пропозиція «A або B» є істинною, якщо хоча б одна з A або B є істинною; виражається символічно як\(A∨B\) і називається диз'юнкцією A і B.

(d) Пропозиція «Якщо A, то B» є істинною, якщо і A і B є істинними, або A є хибним; виражається символічно як\(A =⇒ B\) і називається умовною пропозицією (або імплікацією). В цьому випадку А називається гіпотезою, а В - висновком. Зверніть увагу, що A = всякий раз, коли A». ⇒ B також може читатися як «A означає B», «A, тільки якщо B», «B, якщо A» або «B

(e) Пропозиція «A, якщо і тільки тоді, коли B» (альтернативно, «A необхідна і достатня для B») є істинною, якщо і A, і B мають однакове значення істинності; виражається символічно як\(A ⇐⇒ B\) і називається біумовним судженням. Якщо A ⇒ B вірно, ми говоримо, що A і B логічно еквівалентні.

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

Варто зазначити, що визначення в математиці зазвичай пишуться у формі «B, якщо A» (або «B за умови, що A» або «B щоразу A»), де B містить термін або фразу, яку ми визначаємо, а А забезпечує значення поняття, яке ми визначаємо. Що стосується визначень, ми завжди повинні інтерпретувати «B if A» як описує саме сукупність «об'єктів» (наприклад, чисел, множин, функцій тощо), які слід ідентифікувати терміном або фразою, яку ми визначаємо. Тобто, якщо об'єкт не відповідає умові, заданому в А, то він ніколи не посилається визначальним терміном або фразою. Деякі автори напишуть визначення у вигляді «B якщо і тільки якщо A». Однак визначення зовсім не таке ж твердження, як звичайне біумовне, оскільки одна з двох сторін не визначена, поки не буде зроблено визначення. Визначення - це дійсно твердження про те, що щойно визначений термін або фраза є синонімом раніше визначеного поняття.

Ми можемо сформувати складні складні пропозиції з декількома компонентами, використовуючи логічні зв'язки.

Проблема 2.19. Нехай A представляють «6 - парне ціле число», а B представляють «4 ділить 6». Висловіть кожне з наступних складних пропозицій у звичайному англійському реченні, а потім визначте його істинне значення.

(а) A B

(б) A B

(c) ¬А

(г) ¬Б

(е) ¬ (AB)

(f) ¬ (AB)

(г) А = ⇒ Б

Визначення 2.20. Таблиця істинності для складеного пропозиції - це таблиця, яка ілюструє всі можливі комбінації значень істинності для компонентів складової пропозиції разом з результуючим значенням істинності для кожної комбінації.

Приклад 2.21. Якщо A і B є пропозиціями, то таблиця істинності для складеного пропозиції A B дається наступним.

A	Б	AB
Т	Т	Т
Т	F	F
F	Т	F
F	F	F

Зверніть увагу, що у нас є стовпці для кожного з A та B. Рядки для цих двох стовпців відповідають усім можливим комбінаціям значень істинності для A та B. Третій стовпець дає значення істинності A B, враховуючи можливі значення істинності для A та B.

Кожна складова складової пропозиції має два можливих значення істинності, а саме істинне чи хибне. Таким чином, якщо складна пропозиція побудована з n складових пропозицій, то таблиця істинності зажадає 2n рядків.

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

(а) ¬А

(б) AB

(с) ¬ (AB)

(г) ¬А¬Б

Проблема 2.23. Тренер обіцяє своїм гравцям: «Якщо ми виграємо сьогодні ввечері, то я куплю тобі піцу завтра». Визначте випадки, в яких гравці можуть справедливо стверджувати, що їх брехали. Якщо команда програла гру і тренер все одно вирішив купити їм піцу, вона брехала?

Проблема 2.24. Скористайтеся визначенням 2.18 (d) для побудови таблиці істинності для A =⇒ B. Порівняйте таблицю істинності з задачею 2.23. Поєднання, на яке слід звернути особливу увагу, - це коли гіпотеза помилкова, а висновок вірний.

Відповідно до Визначення 2.18 (d), умовна пропозиція A =⇒ B є помилковою лише тоді, коли гіпотеза істинна, а висновок помилковий. Можливо, вас турбує той факт, що A =⇒ B є істинним, коли A є помилковим незалежно від того, яке значення істинності B. Слід пам'ятати, що істинне значення A = ⇒ B спирається на дуже конкретне визначення і не завжди може погодитися з розмовним вживанням тверджень «Якщо., то.», з якими ми стикаємося в повсякденній мові. Наприклад, якщо хтось скаже: «Якщо ви порушите правила, то вас покарають», спікер, швидше за все, має намір тлумачити заяву як «Ви будете покарані тоді і тільки в тому випадку, якщо ви порушите правила». У логіці та математиці ми прагнемо усунути таку неоднозначність, прямо кажучи, що саме ми маємо на увазі. Для наших цілей ми повинні розглядати умовну пропозицію як договір або зобов'язання. Якщо гіпотеза помилкова і висновок вірний, договір не порушується. З іншого боку, якщо гіпотеза вірна, а висновок помилковий, то договір розривається.

Часто ми можемо довести факти, що стосуються логічних тверджень, використовуючи таблиці істинності. Нагадаємо, що дві пропозиції P і Q (обидва з яких можуть бути складними складними пропозиціями) логічно еквівалентні, якщо вірно P ⇒ Q (див. Визначення 2.18 (e)). Це відбувається, коли P і Q мають однакове значення істинності. Ми можемо перевірити, чи мають P і Q однакове значення істинності, побудувавши таблицю істинності, яка включає стовпці для кожного з компонентів P і Q, перерахувавши всі можливі комбінації їх істинних значень, а також стовпці для P і Q, які перераховують їхні результуючі значення істинності. Якщо значення істинності в стовпцях для P і Q згодні, то P і Q логічно еквівалентні, а в іншому вони логічно не еквівалентні. При побудові таблиць істинності, щоб перевірити, чи є P і Q логічно еквівалентними, ви повинні додати будь-які необхідні проміжні стовпці, щоб допомогти у ваших «розрахунках». Використовуйте таблиці істинності при спробі виправдати наступні кілька проблем.

Теорема 2.25. Якщо A є пропозицією, то ¬ (¬А) логічно еквівалентно А.

Наступна теорема, іменована як Закон Де Моргана, забезпечує метод заперечення складної пропозиції, що включає кон'юнкцію.

Теорема 2.26 (Закон Де Моргана). Якщо A і B є пропозиціями, то ¬ (A B) логічно еквівалентно ¬A ≠ ¬B.

Проблема 2.27 (Закон Де Моргана). Нехай A і B будуть пропозиціями. Згадайте твердження, подібне до теореми 2.26 для пропозиції ¬ (AB), а потім доведіть його. Це також називається законом Де Моргана.

Ми будемо регулярно використовувати обидві версії Закону Де Моргана. Іноді сполучники і диз'юнкції «закопуються» в математичному твердженні, що робить заперечення тверджень хитрим справою. Майте це на увазі при наближенні до наступної проблеми.

Проблема 2.28. Нехай х буде вашим улюбленим реальним числом. Зведіть нанівець кожне з наступних тверджень. Зверніть увагу, що твердження в частині (b) передбачає кон'юнкцію.

(а) х < −1 або x ≥ 3.

(б) 0 ≤ х < 1.

Теорема 2.29. Якщо A і B є пропозиціями, то A ⇒ B логічно еквівалентно (A =⇒ B) (B =⇒ A).

Теорема 2.30. Якщо A, B і C є пропозиціями, то (A ˈB) =⇒ C логічно еквівалентно (A =⇒ C) (B =⇒ C).

Ми вже ввели наступне поняття в обговоренні після теореми 2.11

Визначення 2.31. Якщо A і B є пропозиціями, то зворотне значення A =⇒ B дорівнює B =⇒ A.

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

Визначення 2.33. Якщо A і B є пропозиціями, то обернене A =⇒ B дорівнює ¬A =⇒ ¬B.

Проблема 2.34. Наведіть приклад істинного умовного пропозиції, обернене яким є false.

Виходячи з задач 2.32 і 2.34, можна зробити висновок, що зворотне і зворотне умовного судження не обов'язково мають таку ж істинну цінність, як початкове твердження. Більш того, зворотне і зворотне умовного судження не обов'язково мають таку ж істинну цінність, як один одного.

Проблема 2.35. Якщо можливо, наведіть приклад умовної пропозиції, зворотне вірне, але обернене помилково. Якщо це неможливо, поясніть, чому.

Що робити, якщо поміняти місцями ролі гіпотези та укладення умовної пропозиції і звести нанівець кожну?

Визначення 2.36. Якщо A і B є пропозиціями, то контрапозитив A =⇒ B дорівнює ¬B =⇒ ¬A.

Проблема 2.37. Нехай A і B представляють твердження з завдання 2.19. Висловіть кожне з наступних слів у звичайному англійському реченні.

(a) Зворотне значення A =⇒ B.

(б) Контрапозитив A = ⇒ B.

Проблема 2.38. Знайдіть зворотне і контрапозитивне наступне твердження: «Якщо Дана живе у Флагстаффі, то Дана живе в Арізоні».

Використовуйте таблицю істинності, щоб довести наступну теорему.

Теорема 2.39. Якщо A і B є пропозиціями, то A =⇒ B логічно еквівалентно його контрапозитиву.

До цих пір ми обговорювали, як заперечувати пропозиції форми A, A B, і A ˈB для пропозицій A і B. Однак нам ще належить обговорити, як звести нанівець пропозиції форми A =⇒ B. Доведіть наступний результат таблицею істинності.

Теорема 2.40. Якщо A і B є пропозиціями, то імплікація A =⇒ B логічно еквівалентна диз'юнкції ¬A B.

Наступний результат швидко випливає з теореми 2.40 разом із законом Де Моргана. Ви також можете перевірити цей результат за допомогою таблиці істинності.

Слідство 2.41. Якщо A і B є пропозиціями, то ¬ (A =⇒ B) логічно еквівалентно A ¬B.

Проблема 2.42. Нехай A і B є пропозиціями «√ 2 - ірраціональне число» і «Кожен прямокутник - трапеція» відповідно.

(а) Висловіть A =⇒ B як англійське речення, що включає диз'юнкцію «або».

(b) Висловіть ¬ (A = ⇒ B) як англійське речення, що включає сполучник «і».

Проблема 2.43. Виходить, що пропозиція «Якщо .99··· =\(dfrac{9}{10} + dfrac{9}{100} + dfrac{9}{1000} +···\), то .99 ≠ 1» є хибним. Напишіть його заперечення як сполучник.

Нагадаємо, що судження є виключно істинним або хибним - воно ніколи не може бути і тим, і іншим.

Визначення 2.44. Складене судження, яке завжди є помилковим, називається протиріччям. Складна пропозиція, яка завжди вірна, називається тавтологією.

Теорема 2.45. Якщо А - це судження, то судження ¬A A є протиріччям.

Проблема 2.46. Наведіть приклад тавтології з використанням довільних пропозицій та будь-якого з логічних зв'язків ¬, і ˈ. Доведіть, що ваш приклад насправді тавтологія.