Пошукова робота
на тему:
Елементи логіки
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 |
Обчислимо значення формули, наприклад, (A®B)&(B®A) при всіх можливих наборах значень змінних A і B. Обчислення подамо такою таблицею:
| A B | A®B | B®A | (A®B)&(B®A) |
| 0 0 | 1 | 1 | 1 |
| 0 1 | 1 | 0 | 0 |
| 1 0 | 0 | 1 | 0 |
| 1 1 | 1 | 1 | 1 |
Таблиці, в яких представлено залежність значень формул від пропозиційних змінних, називаються таблицями істинності.
Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за "силою тяжіння до формул" подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+2´3 позначає суму 1 і 2´3, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка Ø вважається найсильнішою, тобто ØAÙB є скороченням від (ØA)ÙB, а не від Ø(AÙB). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, Ú, ®, º. Отже, формулу AÚBÙC можна розглядати, як скорочений запис формули AÚ(BÙC), а формулу AºB®CÚA – як Aº(B®(CÚA)).
Всі двомісні зв'язки мають властивість лівобічного зв'язування. Це означає, що якщо праворуч і ліворуч від підформули записано без дужок знаки двомісних зв'язок, "сила тяжіння" яких однакова, то першою до підформули застосовується ліва з них. Наприклад, AÚBÚC є скороченим записом формули (AÚB)ÚC.
Означення. Дві формули називаються еквівалентними, або рівносильними, якщо приймають однакові значення при всіх можливих значеннях пропозиційних змінних. Рівносильність формул позначається знаком º і в логіці називається законом.
Наприклад, неважко переконатися, що за довільних формул A, B, C наступні рівносильності є законами (праворуч указано назви деяких з них):
(1) AÙB º BÙA, AÚB º BÚA – закони комутативності
(2) AÙ(BÙC) º (AÙB)ÙC, AÚ(BÚC) º (AÚB)ÚC – закони асоціативності
(3) AÙ(BÚC) º (AÙB)Ú(AÙC), AÚ(BÙC) º (AÚB)Ù(AÚC) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції