A: Деякі правила логіки

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

1. \(x =x\)тримає для всіх\(x\). [Рефлексивність.]
2. Якщо\(x= y\) тоді\(y=x\). [Симетрія.]
3. Якщо\(x=y\) і\(y=z\) тоді\(x=z\). [Транзитивність.]

Наприклад, якщо ми в змозі довести\(x=y\),\(z=w\) і\(y=z\)\(w=r\), то ми можемо зробити висновок про транзитивність рівності, що\(x=r\). Рефлексивність і симетрія рівності також дуже корисні. Не варто цитувати ці правила кожного разу, коли вони використовуються, але добре бути в курсі їх (на випадок, якщо хтось запитає).

Наслідки мають вирішальне значення для розвитку математики. Імплікація - це заява форми

\[\begin{align} \mbox{ If $P$ then $Q$} \label{A1}\end{align}\]де\(P\) і\(Q\) є заяви. Замість (A.1) ми іноді напишемо

\[\begin{align} P \Longrightarrow Q . \label{A2} \end{align}\]Заява (А.2) читається, «\(P\)має на увазі\(Q\)». \(P\)Називаємо гіпотезу і,\(Q\) висновок імплікації (А.2). Учні повинні бути обережними при використанні цього позначення. Наприклад, не пишіть,\[\nonumber {\mbox{If} \ P \Longrightarrow Q}\] коли маєте на увазі

\[\begin{align} \label{implication} P \Longrightarrow Q \end{align}\]

Щоб довести наслідки\(P \Longrightarrow Q\), почніть з припущення, що\(P\) це правда, і використовуйте це припущення для встановлення обґрунтованості\(Q\). Іноді простіше довести еквівалентне твердження\[\begin{align} \label{contrapositive} \mbox{$Q$ is false} \Longrightarrow \mbox{$P$ is false} \end{align}\] Це називається контрапозитивом імплікації (А.3).

пишемо

\[\begin{align} P \Longleftrightarrow Q \label{A3} \end{align}\]як абревіатура для двох тверджень\[P \Longrightarrow Q \quad \mbox{ and } \quad Q \Longrightarrow P\] Так, наприклад, якщо вам потрібно довести, що у\(P \Longleftrightarrow Q\) вас дійсно є дві речі, щоб довести: обидва\(P \Longrightarrow Q\) і\(Q \Longrightarrow P\). Твердження (A.5) читається\[\mbox{``$P$ is equivalent to $Q$''},\] або\[\mbox{``$P$ holds if and only if $Q$ holds.''}\] І іноді ми використовуємо абревіатуру «iff» для «якщо і тільки якщо». Тож прийнятною альтернативою (А.5) є\[\mbox{$P$ \ iff \ $Q$}\].

Ми припускаємо, що імплікація задовольняє наступним правилам:

1. \(P \Longrightarrow P\)тримає для всіх\(P\). [Рефлексивність.]
2. Якщо\(P \Longrightarrow Q\) і\(Q \Longrightarrow R\) тоді\(P \Longrightarrow R\). [Транзитивність.]

Ми припускаємо, що еквівалентність задовольняє наступним правилам.

1. \(P \Longleftrightarrow P\)тримає для всіх\(P\). [Рефлексивність.]
2. Якщо\(P \Longleftrightarrow Q\) тоді\(Q \Longleftrightarrow P\). [Симетрія.]
3. Якщо\(P \Longleftrightarrow Q\) і\(Q \Longleftrightarrow R\) тоді\(P \Longleftrightarrow R\). [Транзитивність.]

Ми часто будемо використовувати ці правила для імплікації та еквівалентності без коментарів.

Конвенція У визначеннях слово if означає якщо і тільки якщо. Порівняйте, наприклад, визначення 2.2.

Важливі фрази Окрім пошуку наслідків та еквівалентів, студенти повинні звернути пильну увагу на наступні слова та фрази:

1. існує
2. є
3. є
4. для всіх
5. для кожного
6. для кожного
7. для деяких
8. унікальні
9. один і тільки один
10. максимум один
11. хоча б один
12. на
13. а, ан
14. такий, що
15. має на увазі
16. звідси
17. тому

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