Реферат: Елементи логіки

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).

Означення. Висловлення записують у вигляді формул за такими правилами:

1) пропозиційна літера є формулою;

2) якщо X і Y – формули, то (ØX), (XÙY), (XÚY), (X®Y), (X«Y) також є формулами;

3) інших формул немає.

За цими правилами, наприклад, Ø(A®B), ((A«B)&(Ø(AÚB))) є формулами, AÚBÙC – ні. Далі ми розглянемо узгодження, які дозволяють скорочувати запис формул. Зокрема, ці узгодження дозволяють розглядати AÚBÙC як формулу. Тут лише зауважимо, що можна не записувати зовнішні дужки формул, наприклад, писати X®Y.

2. Таблиці істинності формул і закони

Формула є словом, тобто послідовністю символів – імен пропозиційних змінних, знаків зв'язок і дужок. Це слово має певну структуру, обмежену правилами побудови формул. Підслово цього слова, яке є формулою, називається підформулою. Наприклад, у формулі ((A«B)&(Ø(AÚB))) є підформули A, B, (A«B), (AÚB), (Ø(AÚB)).

Формула, що позначає висловлення, складене з інших, простіших, має значення, яке залежить від значень цих складових висловлень. Для його обчислення спочатку кожній пропозиційній змінній ставиться у відповідність одне зі значень "хибність" чи "істина" (0 чи 1). Далі за означеннями пропозиційних зв'язок обчислюється значення підформул, починаючи від найпростіших і закінчуючи всією формулою. Значення формул з однією двомісною зв'язкою при всіх можливих наборах значень змінних наведено в таблиці:

A B	AÙB	AÚB	A®B	A«B
0 0	0	0	1	1
0 1	0	1	1	0
1 0	0	1	0	0
1 1	1	1	1	1