Елементи логіки
СОДЕРЖАНИЕ: Пошукова робота на тему: Елементи логіки 1. Висловлення та формули Одним з основних понять логіки є висловлення – розповідне речення, про яке можна стверджувати, що воно є або істинним, або хибним.Пошукова робота
на тему:
Елементи логіки
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+23 позначає суму 1 і 23, а не добуток 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 ) – закони дистрибутивності конюнкції відносно дизюнкції та дизюнкції відносно конюнкції
(4) A A A , A A A – закони ідемпотентності
(5) A (A B ) A , A (A B ) A
(6) (A B ) A B , (A B ) A B – закони Де Моргана
(7) A A – закон подвійного заперечення
(8) A 0 0, A 1 A , A 0 A , A 1 1 – закони поглинання
(9) A A 1 – закон виключеного третього
(10) A A 0 – закон суперечності
(11) 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 1 A 2 )A 3 )…)An ) має еквівалентний запис A 1 A 2 A 3 …An . Формула в такому записі називається конюнкцією формул A 1 , A 2 , A 3 , …, An .
Означення. Елементарною конюнкцією називається конюнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A 1 A 2 A 3 .
Означення. Дизюнктивною нормальною формою (скорочено ДНФ ) називається дизюнкція елементарних конюнкцій. Наприклад, формула 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 ) (3)
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 (5)
A B C A C B
За законами (2) звязки дизюнкції також асоціативні, звідки формули ((…((A 1 A 2 ) A 3 ) …)An ) і A 1 A 2 A 3 …An також є еквівалентними. Остання з них називається дизюнкцією формул A 1 , A 2 , A 3 , …, An .
Означення. Елементарною дизюнкцією називається дизюнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A 1 A 2 A 3 .
Означення. Конюнктивною нормальною формою (скорочено КНФ ) називається конюнкція елементарних дизюнкцій. Наприклад, формула (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 ) (3)
(A B C )(A B B )(B C A )(B C B ) (3)
(A C )(B C )(A B )(B B )(B A )(C A )
(B B )(C B ) (9)
(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 1 , X 2 , …, Xn , якщо з істинності X 1 X 2 …Xn випливає істинність формули Y . Формули X 1 , X 2 , …, Xn називаються засновками Y .
Перевірити, чи є одна формула логічним висновком інших, можна за допомогою порівняння таблиць істинності цієї формули та конюнкції інших. Але можна діяти зовсім іншим способом на основі двох наступних тверджень.
Теорема 1 . Формула Y є логічним висновком формул X 1 , X 2 , …, Xn тоді й тільки тоді, коли формула (X 1 X 2 …Xn )®Y є тавтологією.
Доведення. 1 (Необхідність). Припустимо, що формула Y є логічним висновком формул X 1 , X 2 , …, Xn . Якщо за деяких значень літер у формулах X 1 , X 2 , …, Xn хоча б одна з них хибна, то за означенням імплікації (X 1 X 2 …Xn )®Y істинна. Якщо ж за деяких значень літер у формулах X 1 , X 2 , …, Xn всі вони істинні, X 1 X 2 …Xn також істинна. Але формула Y є логічним висновком формул X 1 , X 2 , …, Xn , тому вона також істинна. Тоді істинна і формула (X 1 X 2 …Xn )®Y . Отже, за будь-яких значень літер (X 1 X 2 …Xn )®Y істинна, тобто є тавтологією.
2 (Достатність). Припустимо, що (X 1 X 2 …Xn )®Y є тавтологією. Тоді якщо за якихось значень літер у формулах X 1 , X 2 , …, Xn всі вони істинні, то Y також істинна, тобто є їх логічним висновком.
Теорема 2. Формула Y є логічним висновком формул X 1 , X 2 , …, Xn тоді й тільки тоді, коли формула (X 1 X 2 …Xn Y ) є суперечністю.
Доведення. За теоремою 1, формула Y є логічним висновком формул X 1 , X 2 , …, Xn тоді й тільки тоді, коли формула (X 1 X 2 …Xn )®Y є тавтологією. Звідси Y є логічним висновком формул X 1 , X 2 , …, Xn тоді й тільки тоді, коли заперечення ((X 1 X 2 …Xn )®Y )є суперечністю. Але
((X 1 X 2 …Xn )®Y ) ((X 1 X 2 …Xn )Y )
((X 1 X 2 …Xn ))Y X 1 X 2 …Xn Y .
Таким чином, твердження теореми істинне.
Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул A ®B і A . Перетворимо формулу (A ®B )A B :
(A ®B )A B (A B )A B (A A B )(B A B ) 00 0.
Отже, формула (A ®B )A B суперечлива, і за теоремою 2 формула B є логічним висновком формул A ®B і A .
Той факт, що формула B є логічним висновком формул A ®B і A , відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень A ®B і A одержати нове істинне твердження B . Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення , яке має вигляд і назву modus ponens (правило відокремлення ). Воно дозволяє одержати висновок B твердження A ®B як окреме висловлення, тобто відокремити його вид засновку A . У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.
Підібємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних звязок, а також перебудовуємо їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень .
Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами , а висловлення, що виводяться, – теоремами . Прикладом аксіоми може служити висловлення AA, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень .
Підкреслимо ще раз, що в цьому розділі нашою метою є лише знайомство з основними поняттями і мовою позначень логіки, тому ми не торкаємося її суттєвих питань. Вони розкриваються у багатьох джерелах (див. список рекомендованої літератури).
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 ).
І так далі. Розглянемо, наприклад, твердження великої теореми Ферма:
Рівняння zn = xn + yn , де n – ціле число, більше 2, не має розвязків у цілих додатних числах .
Одним із можливих записів цього твердження є такий:
x y z n ((n 2) ® (zn xn +yn )).