Пошукова робота

на тему:

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

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) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції

1. AA  A, AA  A – закони ідемпотентності

2. A(AB)  A, A(AB)  A

3. (AB)  AB, (AB)  AB – закони Де Моргана

4. A  A – закон подвійного заперечення

5. A0  0, A1  A, A0  A, A1  1 – закони поглинання

6. AA  1 – закон виключеного третього

7. AA  0 – закон суперечності

8. AB  BA – закон контрапозиції

Корисно також пам'ятати ще два закони:

(12) AB  AB

(13) AB  (AB)(BA).

На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула A(AB) має рівносильні формули A(AB), A(AB), (AA)B, AB, що одержуються послідовним застосуванням законів (12), (7), (2), (4).

3. Нормальні форми висловлень

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

Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A₁A₂)A₃)…)A_n) має еквівалентний запис A₁A₂A₃…A_n. Формула в такому записі називається кон'юнкцією формул A₁, A₂, A₃, …, A_n.

Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A₁A₂A₃.

Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула ABBCD. Зауважимо, що її структуру краще видно в записі ABBCD або в записі .

Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок  і , тобто перетворити формулу до рівносильної, у якій є лише зв'язки ,  і . Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.

Приклад. Розглянемо перетворення (AB)(CB). Після знаків  у дужках указано номери законів, застосованих при черговому перетворенні:

(AB)(BC) ^{(13, 12)}

((AB)(CB))((CB)(AB)) ^{(6, 7, 2)}

 (ABCB)(BCAB) ⁽³⁾

 ABBCABAABBCBCCACB

BBCBABB ^{(1, 4, 9, 8)}

 ABCACBCBAB ⁽⁵⁾

 ABCACB

За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A₁A₂) A₃) …)A_n) і A₁A₂A₃…A_n також є еквівалентними. Остання з них називається диз'юнкцією формул A₁, A₂, A₃, …, A_n.

Означення. Елементарною диз'юнкцією називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A₁A₂A₃.

Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (AB)(BCD), яку можна подати також у вигляді .

Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: A(BC)  (AB)(AC).

Приклад. Розглянемо перетворення формули (AB)(CB) після одержання формули (ABCB)(BCAB):

(ABCB)(BCAB) ⁽³⁾

 (ABC)(ABB)(BCA)(BCB) ⁽³⁾

 (AC)(BC)(AB)(BB)(BA)(CA)

(BB)(CB) ⁽⁹⁾

 (AC)(BC)(AB)(BA)(CA)(CB)

4. Тавтології, суперечності та логічні висновки

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

Наприклад, AA чи (AB)(BA). Неважко також переконатися, що заміною знаків  на зв'язку  у законах (1)-(13), наведених у п.1.1, одержуються саме тавтології.

Тавтології характерні тим, що коли всі входження тієї самої літери замінити на будь-яке, але одне й те саме висловлення, то нове висловлення буде істинним. Наприклад, підставимо у тавтологію ((AB)B)A замість літери A висловлення "світить сонце", а замість літери B – "світять зорі". Одержане висловлення "Якщо світить сонце або світять зорі, і не світять зорі, то світить сонце" є істинним. Підкреслимо, що сама по собі структура цього висловлення вже забезпечує його істинність.

Неважко переконатися, що якщо тавтологіями є деяка формула X і формула XY, то Y також є тавтологією.

Означення. Формула називається тотожньо хибною, або суперечністю, якщо має значення 0 при всіх можливих значеннях пропозиційних змінних.

Одним із характерних прикладів суперечності є висловлення AA. Ця суперечність використовується у доведенні тверджень вигляду AB методом "від супротивного". Припускають істинність заперечення (AB), тобто істинність AB. З істинності B виводять A, одержуючи суперечність AA. Вона свідчить про хибність AB, тобто істинність AB.

Зауважимо, що для доведення істинності AB достатньо з B вивести A, тобто довести істинність протилежного твердження BA. Адже за законом контрапозиції (11) AB  BA

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

Тепер розглянемо поняття логічного висновку. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком.

Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені.

Для цього позначимо висловлення літерами:

A – "податки зростають",

B – "купівельна спроможність грошей падає",

C – "люди незадоволені".

Припущення прикладу висловимо формулою:

(AB)(BC)A.

Доведемо, за істинності такої умови істинним буде висловлення C. Перетворимо (AB)(BC)A до ДНФ:

(AB)(BC)A  (AB)(BC)A  A(AB)(BC) 

 (AA)(AB)(BC)  (AB)(BC) 

 (ABB)(ABC)  ABC.

Отже, маємо, що істинною є формула ABC. Але вона істинна лише тоді, коли кожний співмножник істинний. Звідси висловлення C є істинним.

Таким чином, з істинності формул (AB), (BC) і A випливає істинність C. У такому випадку C називається логічним висновком цих формул.

Означення. Формула Y називається логічним висновком формул X₁, X₂, …, X_n, якщо з істинності X₁X₂…X_n випливає істинність формули Y. Формули X₁, X₂, …, X_n називаються засновками Y.

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

Теорема 1. Формула Y є логічним висновком формул X₁, X₂, …, X_n тоді й тільки тоді, коли формула (X₁X₂…X_n)Y є тавтологією.

Доведення. 1 (Необхідність). Припустимо, що формула Y є логічним висновком формул X₁, X₂, …, X_n. Якщо за деяких значень літер у формулах X₁, X₂, …, X_n хоча б одна з них хибна, то за означенням імплікації (X₁X₂…X_n)Y істинна. Якщо ж за деяких значень літер у формулах X₁, X₂, …, X_n всі вони істинні, X₁X₂…X_n також істинна. Але формула Y є логічним висновком формул X₁, X₂, …, X_n, тому вона також істинна. Тоді істинна і формула (X₁X₂…X_n)Y. Отже, за будь-яких значень літер (X₁X₂…X_n)Y істинна, тобто є тавтологією.

2 (Достатність). Припустимо, що (X₁X₂…X_n)Y є тавтологією. Тоді якщо за якихось значень літер у формулах X₁, X₂, …, X_n всі вони істинні, то Y також істинна, тобто є їх логічним висновком.

Теорема 2. Формула Y є логічним висновком формул X₁, X₂, …, X_n тоді й тільки тоді, коли формула (X₁X₂…X_nY) є суперечністю.

Доведення. За теоремою 1, формула Y є логічним висновком формул X₁, X₂, …, X_n тоді й тільки тоді, коли формула (X₁X₂…X_n)Y є тавтологією. Звідси Y є логічним висновком формул X₁, X₂, …, X_n тоді й тільки тоді, коли заперечення ((X₁X₂…X_n)Y)є суперечністю. Але

((X₁X₂…X_n)Y)  ((X₁X₂…X_n)Y) 

 ((X₁X₂…X_n))Y  X₁X₂…X_nY.

Таким чином, твердження теореми істинне.

Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул AB і A. Перетворимо формулу (AB)AB:

(AB)AB  (AB)AB  (AAB)(BAB)  00  0.

Отже, формула (AB)AB суперечлива, і за теоремою 2 формула B є логічним висновком формул AB і A.

Той факт, що формула B є логічним висновком формул AB і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень AB і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження AB як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.

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

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

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

5. Неформальне знайомство з кванторами

У математиці, як і у повсякденному житті, виникають твердження зі специфічною структурою. Ця структура робить можливими міркування, які не можна відтворити виведенням висловлень. Класичним прикладом таких міркувань є:

Кожна людина смертна.

Сократ – людина.

Звідси випливає, що Сократ смертний.

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

Введемо додаткові позначення. Нехай x позначає деяку змінну, значення якої можуть мати деяку властивість P. Такі змінні називаються предметними. Висловлення "x має властивість P" позначимо P(x). Наприклад, висловлення "Ціле число x є парним" позначимо E(x). Значення такого висловлення залежить від значення цієї змінної. При x=1 висловлення E(x) хибне, при x=2 – істинне. Замість літери x можна записати її значення, наприклад, E(2).

Речення "Кожне значення x має властивість P", або "Всі значення x мають властивість P", або "Всі x мають властивість P", або "При всіх x справджується властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором загальності. Слово "квантор" походить від слова "квантифікація", що означає "кількісне вираження". Продовжуючи приклад про парні числа, зауважимо, що твердження x E(x) є хибним.

Речення "Існує значення x, що має властивість P", або "Деякі значення x мають властивість P", або "При деякому значенні x справджується властивість P", або "Деякі x мають властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором існування. Очевидно, що у прикладі про парні числа твердження x E(x) є істинним.

Очевидно, що

x P(x)  x P(x),

причому твердження x P(x) і x P(x) нерівносильні.

Розглянемо деякі з можливих застосувань пропозиційних зв'язок до виразів із кванторами. Заперечення (x P(x)) читається як "неістинно, що всі значення x мають властивість P", тобто як "існує значення x, що не має властивості P". Таке речення можна позначити як x P(x). Таким чином,

(x P(x))  x P(x).

Аналогічно

(x P(x))  x P(x).

Висловлення x P(x)  x Q(x) читається як "всі значення x мають властивість P і всі значення x мають властивість Q", тобто "всі значення x мають властивість P і властивість Q". Таким чином,

(x P(x))(x Q(x))  x (P(x)Q(x)).

Висловлення x P(x)  x Q(x) читається як "усі значення x мають властивість P або всі значення x мають властивість Q". З цього речення випливає, що "усі значення x мають властивість P або властивість Q", але ці два речення не рівносильні. Таким чином, x(P(x)Q(x)) є логічним висновком висловлення (x P(x))(x Q(x)), тобто

((x P(x))(x Q(x)))  x(P(x)Q(x)),

але вони нерівносильні.

Приклад. Якщо P(x) позначає речення "x – парне число", а Q(x) – "x – непарне число", то висловлення x(P(x)Q(x)) є істинним, а (x P(x))(x Q(x)) – хибним.

Насамкінець, розглянемо речення з двома й більше кванторами. Вони з'являються, коли йдеться про властивості пар, трійок тощо змінних. Наприклад, речення "При будь-якому натуральному значенні x існує значення y, таке, що x є дільником y" можна записати як

x (y D(x, y)),

де D(x, y) позначає речення "x є дільником y".

Речення вигляду "При будь-якому значенні x справджується, що при будь-якому значенні y істинно A(x, y)" можна позначити так:

x (y A(x, y)).

Будемо опускати дужки, записуючи, наприклад, x y D(x, y) або x y A(x, y). Останній вираз можна прочитати також, як "При будь-якому значенні x і при будь-якому значенні y істинно A(x, y)".

Аналогічно речення вигляду " При будь-якому значенні x і при будь-якому значенні y і при будь-якому значенні z істинно A(x, y, z)" можна позначити виразом

x y z A(x, y, z).

І так далі. Розглянемо, наприклад, твердження великої теореми Ферма:

Рівняння zⁿ=xⁿ+yⁿ, де n – ціле число, більше 2, не має розв'язків у цілих додатних числах.

Одним із можливих записів цього твердження є такий:

x y z n ((n>2)  (zⁿxⁿ+yⁿ)).