Елементи логіки

1. Висловлення та формули

Одним з основних понять логіки є висловлення – розповідне речення, про яке можна стверджувати, що воно є або істинним, або хибним.

Звичайно, в мові існують речення, про які не можна сказати, істинні вони чи хибні. Наприклад, речення "Це речення є хибним". Якщо припустити, що воно є істинним, то з нього випливає його хибність, а якщо воно є хибним, то маємо, що воно істинне. Отже, це речення не можна розглядати як висловлення. Насправді воно є варіантом відомого парадокса брехуна: неможливо сказати, чи є істинною або хибною фраза брехуна "Я брешу".

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

Хибність чи істинність висловлень може змінюватися, наприклад, у часі ("Зараз ніч"), у просторі ("Ми летимо над Африкою") тощо. Будемо дивитися на висловлення як на змінну, що може мати одне з двох значень – "хибність" або "істина", позначені 0 і 1 відповідно. Ці значення вважаються протилежними одне до одного.

Означення. Змінна з можливими значеннями "хибність" або "істина" називається пропозиційною.

Будемо позначати пропозиційні змінні великими літерами A, B, C, …, можливо, з індексами. Ці літери також називаються пропозиційними.

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

Означення. Висловлення вигляду "Не A" записується A й називається запереченням висловлення A. Його значення є протилежним до значення A.

Означення. Висловлення вигляду "A та B" записується як A&B або AB або AB і називається кон'юнкцією висловлень A і B, або їх логічним добутком. Висловлення A і B називаються співмножниками кон'юнкції. Вона істинна, коли кожний із співмножників істинний. Якщо ж хоча б один із них хибний, то й вона хибна. Її ще записують у вигляді .

Означення. Висловлення вигляду "A або B" записується як AB і називається диз'юнкцією висловлень A і B, або логічною сумою (доданків диз'юнкції). Вона істинна, коли хоча б один із доданків істинний (можливо, і обидва). Якщо ж обидва доданки хибні, то й вона хибна. Її ще записують у вигляді .

Означення. Висловлення вигляду "Якщо A, то B" записується як AB і називається імплікацією з засновком A і висновком B. Імплікація хибна, коли засновок істинний, а висновок хибний. В усіх інших випадках вона істинна. Наприклад, висловлення "Якщо 2*2=4, то Сонце обертається навколо Землі" за цим означенням є хибним, а висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" – істинним. Імплікацію часто позначають знаком "": AB.

Зауважимо, що запис AB читається також, як "B є необхідною умовою для A", або як "A є достатньою умовою для B", або як "З A випливає B", або як "A тільки тоді, коли B", або як "B тоді, коли A".

Імплікація "З не B випливає не A", що позначається (B)(A), називається висловленням, протилежним до висловлення AB. Імплікація "З B випливає A", що позначається BA, називається висловленням, оберненим до висловлення AB.

Означення. Висловлення вигляду "A тоді й тільки тоді, коли B" записується як AB і називається еквівалентністю висловлень A і B. Вона істинна, коли значення висловлень A і B збігаються. Якщо ж вони різні, то еквівалентність хибна. Наприклад, висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" є істинним. Еквівалентність часто позначають не знаком "", а знаком "".

Зауважимо, що запис AB читається також як "B є необхідною і достатньою умовою для A", а також як "Якщо A, то B, і якщо B, то A". Заперечення еквівалентності (AB) читається як "Або A, або B". Складений сполучник "або …, або …" інколи називається "виключне або". Підкреслимо, що диз'юнкція AB відрізняється від заперечення еквівалентності (AB).