Вступ до сучасної логіки
§ 19. Закони логіки висловлень і логіки предикатів
Різноманітність властивостей і відношень охоплює розширена логіка предикатів, тобто логіка предикатів більш високого ступеня. Зокрема, предикати другого ступеня (предикати предикатів) відображають властивості, притаманні властивостям індивідів. Цю ієрархію можна продовжувати скільки завгодно, та логіки зазвичай користуються предикатами першого й другого ступенів.
Взявши до уваги вказані характерні риси логіки предикатів, розглянемо застосування операцій логіки висловлень до предикатів на прикладі найпростішого випадку одномісних предикатів.
Нехай М — певна множина, на якій означено предикати. Назвемо цю множину областю. Кожному одномісному предикатові форми F{x) можна поставити у відповідність множину елементів а з області М, для якої F(a) істинне. Позначимо цю підмножину як Л^ і виконаємо зворотну операцію, а саме: кожній множині, що належить М, можна поставити у відповідність предикат Р(х), що являє собою висловлення, істинне тоді й тільки тоді, коли хє N. Предикат Р(х) набуває значення «істина» на N і значення «ложність» поза N. Отже, N є N. Така відповідність між підмножинами множини М і одномісними предикатами, означеними на множині М, взаємно-однозначна.
Як відомо, теоретико-множинною сумою N{ u N2 двох множин УУ, і N2 називається множина, яка містить усі елементи множини /V, і всі елементи множини N2. Teopeтико-множинним добутком, або перетином, /V, п N2 двох множин /V, і N2 називається множина всіх елементів, які належать і множині N{, і множині N2.
Таким чином, булеві операції ->, &, v над одномісними предикатами відповідають операціям над множинами. Ці операції називаються перетином, об єднанням і доповненням множин.
Якщо закони логіки висловлень застосовуються до виразів, котрі за будь-якого розподілу значень істинності своїх пропозиційних змінних набувають значення «істина», го з деякими поправками аналогічні закони діють і в логіці предикатів. Що стосується поправок, то в даному випадку слід ураховувати таке: якщо перетворення пропозиційної функції форми «х має властивість Р» на істинне висловлення залежить передусім від обраної індивідної області, то закони логіки предикатів треба шукати у виразах, які не залежать від тієї чи іншої області індивідів як значень змінних, але є значущими для будь-яких непорожніх областей. Річ у тім, що логіка предикатів розглядає предикати взагалі, тобто вона цікавиться структурою висловлень, незалежно від їхнього конкретного смислового змісту. Тому закони логіки предикатів заявляють про себе в таких виразах, які не залежать від конкретних значень предикатних змінних і є правильними для будь-яких їхніх значень.
Одним із таких законів є закон виключеного третьог (середнього). У символічному записі цей закон має вигляд:
\x(F(x) v Н F{x)).
Зауважимо, що в логіці є два формулювання одержання правильних умовиводів. Перше постає у вигляд' правил виведення, а друге — у вигляді логічних законів.
Логічні правила — це.своєрідні директивні вказівки, які базуються на логічних законах і дають змогу визнавати правильними висловлення, що утворені в результаті виведення з істинних посилок.
Законами логіки висловлень і предикатів називаються схеми побудови істинних складних висловлень.
Інакше кажучи, закони логіки висловлень і предикатів — це такі вирази, яким за будь-яких підстановок значень замість змінних завжди відповідає істинне висловлення. До цих законів, які ще називають теоремами, належать:
1. Закон виключеного третього
2. Закон несуперечності
3. Закон подвійного заперечення:
4. Закон контрапозиції:
5. Закони, що характеризують кон'юнкцію:
6. Закони імплікативних силогізмів.
7. Закони, що характеризують диз'юнкцію.
8. Закони, що характеризують еквіваленцію (еквівалентність
9. Закони де Моргана.
Деякі вчені (Л. Е. Я. Брауер, Г. Вейль, А. Гейтінг) не визнають універсальними законами логіки закон виключеного третього та закон подвійного заперечення.
Традиційний для класичної логіки закон несупереч-ності мало кого цікавить сьогодні, бо з нього випливає досить незначна кількість нетривіальних теорем. Іноді закон несуперечності формулюють так: два суперечні одне одному висловлення не можуть бути одночасно істинними.
Одним із цікавих законів логіки є закон контрапозиції. Розглянемо його на такому прикладі.
Припустімо, Остап Бендер обіцяв Лоханкіну, що якщо буде час, то сплатить за кімнату. Якщо Бендер тримає своє слово, але не сплачує Лоханкіну, то висновок такий: у Бендера не було часу відвідати Лоханкіна. Шляхом таких міркувань визнаємо істинним таке умовне висловлення:
Якщо вірно, що (якщо (у Бендера буде час), то (Бендер відвідає Лоханкіна)), то (якщо (Бендер не відвідав Лоханкіна), то це означає, що (у Бендера не було часу)).
Це речення містить звороти «вірно, що» і «це означає, що», форма яких у даному випадку не має принципового значення. До речі, підстановка в логічні схеми (формули) конкретних значень із буденної мови часто звучить штучно, навіть ріже слух, та логіки на це не зважають, тим більше, що з такими підстановками вони майже не мають справи.
Можна вважати, що зворот «вірно, що якщо р, то q» означає те саме, що «якщо р, то q». З цього випливає, що в наведеному прикладі легко можна позбутися громіздких граматичних конструкцій. У результаті матимемо:
Якщо (якщо (у Бендера буде час),
то (Бендер відвідає Лоханкіна)),
то (якщо (Бендер не відвідав Лоханкіна),
то (у Бендера не було часу)).
Заперечення всього висловлення можна розглядати як заперечення всередині висловлення. Наприклад, висловлення «Невірно, що Бендер відвідає Лоханкіна» означає те саме, що й «Бендер не відвідає Лоханкіна».
На законі контрапозиції ґрунтується так зване непряме доведення, або reductio ad absurdum (лат. — зведення до\ нісенітності). Тобто замість того, щоб доводити р -> q, можна довести -і q -> -> p.
Слід мати на увазі, що кон'юнкція є переставною, або комутативною (лат. commutatio — зміна), оскільки її члени \ можна міняти місцями. При цьому приймається така ло-гічна теорема:
Якщо (р і q), то (((/= х).
3. Транзитивність: якщо х еквівалентний у, а у еквіва- І
; лентний z, то х еквівалентний z, тобто ((х= у) & (у= z)) —> |\
Відношення еквівалентності можна виразити формулами логіки предикатів. Для цього записують у вигляді аксіом рефлексивність, симетричність і транзитивність. Готові результати будуть такими:
Згідно з цим правилом, якщо певний індивід множини має якусь властивість, то можна зробити висновок, що існує хоча б один індивід, якому ця властивість притаманна.
На відміну від логічних законів, які імперативно вимагають, щоб висновок був завжди істинним, логічні правила менш жорсткі. Вони надають можливість визнавати за істинні нові висловлення залежно від того, який вигляд мають висловлення-посилки, вже визнані за істинні.
Одним з основних правил умовиводу є вже знайоме правило відокремлення («modus ponens»), яке говорить, що умовивід є правильним, якщо з двох істинних посилок маємо істинний висновок. Більш строго це правило читається так: якщо істинна якась імплікація й істинна її умова, то має бути істинним і її висновок. Розглянемо приклад.
Вище наведено схему правильного умовиводу в тому Розумінні, що, підставляючи замість літер р і q конкретні висловлення, матимемо в результаті правильний умовивід, тобто правильність умовиводу з логічних міркувань полягає в тому, що до уваги береться тільки форма наявних у ньому посилок, абстрагуючись від їх змісту.
Повертаючись до питання про загальнозначущість еквіваленції, зазначимо, що еквіваленція в логіці предикатів так само, як і в логіці висловлень, тільки тоді буде загальнозначущою, коли значення істинності її членів за однакових значень їхніх змінних збігаються:
Зауважимо, що в логіці предикатів не існує такого простого способу розв'язування умовиводів, як таблиці істинності в логіці висловлень. Більше того, взагалі немає способу, який можна було б сміливо використовувати для розв'язання будь-яких виразів логіки предикатів. Зазвичай розв'язуваний вираз намагаються звести до виразу логіки висловлень.
Однією з цікавих проблем логіки предикатів є проблема аксіоматизації, що упирається у проблему вирішення. Як відомо, проблема вирішення полягає у пошуку способу, за допомогою якого скінченним числом кроків можна вирішити, яким є логічний вираз — загальнозна-чущим, виконуваним чи суперечним. Одним із видів процедури вирішення у логіці висловлень є таблиці істинності.
Якщо для якоїсь області логічних побудов не існує процедури вирішення, то зазвичай намагаються з'ясувати, чи є дані вирази загальнозначущими. При цьому враховують, що кожний Вираз, виведений із загальнозначущого виразу, сам є загальнозначущим. Таким чином, якщо із загальнозначущих виразів удається вивести за допомогою відповідних перетворень, додержуючись правил виводу, розв'язний вираз, то можна з повним правом вважати, що знайдено індивідуальне доведення для даного виразу. Проте на практиці знайти таке доведення для будь-якого виразу часто буває дуже й дуже важко, оскільки тут багато що залежить від професійного досвіду, інтуїції, а також від дотримання певних загальних положень.
Взявши до уваги вказані характерні риси логіки предикатів, розглянемо застосування операцій логіки висловлень до предикатів на прикладі найпростішого випадку одномісних предикатів.
Нехай М — певна множина, на якій означено предикати. Назвемо цю множину областю. Кожному одномісному предикатові форми F{x) можна поставити у відповідність множину елементів а з області М, для якої F(a) істинне. Позначимо цю підмножину як Л^ і виконаємо зворотну операцію, а саме: кожній множині, що належить М, можна поставити у відповідність предикат Р(х), що являє собою висловлення, істинне тоді й тільки тоді, коли хє N. Предикат Р(х) набуває значення «істина» на N і значення «ложність» поза N. Отже, N є N. Така відповідність між підмножинами множини М і одномісними предикатами, означеними на множині М, взаємно-однозначна.
Як відомо, теоретико-множинною сумою N{ u N2 двох множин УУ, і N2 називається множина, яка містить усі елементи множини /V, і всі елементи множини N2. Teopeтико-множинним добутком, або перетином, /V, п N2 двох множин /V, і N2 називається множина всіх елементів, які належать і множині N{, і множині N2.
Таким чином, булеві операції ->, &, v над одномісними предикатами відповідають операціям над множинами. Ці операції називаються перетином, об єднанням і доповненням множин.
Якщо закони логіки висловлень застосовуються до виразів, котрі за будь-якого розподілу значень істинності своїх пропозиційних змінних набувають значення «істина», го з деякими поправками аналогічні закони діють і в логіці предикатів. Що стосується поправок, то в даному випадку слід ураховувати таке: якщо перетворення пропозиційної функції форми «х має властивість Р» на істинне висловлення залежить передусім від обраної індивідної області, то закони логіки предикатів треба шукати у виразах, які не залежать від тієї чи іншої області індивідів як значень змінних, але є значущими для будь-яких непорожніх областей. Річ у тім, що логіка предикатів розглядає предикати взагалі, тобто вона цікавиться структурою висловлень, незалежно від їхнього конкретного смислового змісту. Тому закони логіки предикатів заявляють про себе в таких виразах, які не залежать від конкретних значень предикатних змінних і є правильними для будь-яких їхніх значень.
Одним із таких законів є закон виключеного третьог (середнього). У символічному записі цей закон має вигляд:
\x(F(x) v Н F{x)).
Зауважимо, що в логіці є два формулювання одержання правильних умовиводів. Перше постає у вигляд' правил виведення, а друге — у вигляді логічних законів.
Логічні правила — це.своєрідні директивні вказівки, які базуються на логічних законах і дають змогу визнавати правильними висловлення, що утворені в результаті виведення з істинних посилок.
Інакше кажучи, закони логіки висловлень і предикатів — це такі вирази, яким за будь-яких підстановок значень замість змінних завжди відповідає істинне висловлення. До цих законів, які ще називають теоремами, належать:
1. Закон виключеного третього
2. Закон несуперечності
3. Закон подвійного заперечення:
4. Закон контрапозиції:
5. Закони, що характеризують кон'юнкцію:
6. Закони імплікативних силогізмів.
7. Закони, що характеризують диз'юнкцію.
8. Закони, що характеризують еквіваленцію (еквівалентність
9. Закони де Моргана.
Деякі вчені (Л. Е. Я. Брауер, Г. Вейль, А. Гейтінг) не визнають універсальними законами логіки закон виключеного третього та закон подвійного заперечення.
Традиційний для класичної логіки закон несупереч-ності мало кого цікавить сьогодні, бо з нього випливає досить незначна кількість нетривіальних теорем. Іноді закон несуперечності формулюють так: два суперечні одне одному висловлення не можуть бути одночасно істинними.
Одним із цікавих законів логіки є закон контрапозиції. Розглянемо його на такому прикладі.
Припустімо, Остап Бендер обіцяв Лоханкіну, що якщо буде час, то сплатить за кімнату. Якщо Бендер тримає своє слово, але не сплачує Лоханкіну, то висновок такий: у Бендера не було часу відвідати Лоханкіна. Шляхом таких міркувань визнаємо істинним таке умовне висловлення:
Це речення містить звороти «вірно, що» і «це означає, що», форма яких у даному випадку не має принципового значення. До речі, підстановка в логічні схеми (формули) конкретних значень із буденної мови часто звучить штучно, навіть ріже слух, та логіки на це не зважають, тим більше, що з такими підстановками вони майже не мають справи.
Можна вважати, що зворот «вірно, що якщо р, то q» означає те саме, що «якщо р, то q». З цього випливає, що в наведеному прикладі легко можна позбутися громіздких граматичних конструкцій. У результаті матимемо:
Якщо (якщо (у Бендера буде час),
то (Бендер відвідає Лоханкіна)),
то (якщо (Бендер не відвідав Лоханкіна),
то (у Бендера не було часу)).
Заперечення всього висловлення можна розглядати як заперечення всередині висловлення. Наприклад, висловлення «Невірно, що Бендер відвідає Лоханкіна» означає те саме, що й «Бендер не відвідає Лоханкіна».
На законі контрапозиції ґрунтується так зване непряме доведення, або reductio ad absurdum (лат. — зведення до\ нісенітності). Тобто замість того, щоб доводити р -> q, можна довести -і q -> -> p.
Слід мати на увазі, що кон'юнкція є переставною, або комутативною (лат. commutatio — зміна), оскільки її члени \ можна міняти місцями. При цьому приймається така ло-гічна теорема:
Якщо (р і q), то (((/= х).
3. Транзитивність: якщо х еквівалентний у, а у еквіва- І
; лентний z, то х еквівалентний z, тобто ((х= у) & (у= z)) —> |\
Відношення еквівалентності можна виразити формулами логіки предикатів. Для цього записують у вигляді аксіом рефлексивність, симетричність і транзитивність. Готові результати будуть такими:
Згідно з цим правилом, якщо певний індивід множини має якусь властивість, то можна зробити висновок, що існує хоча б один індивід, якому ця властивість притаманна.
На відміну від логічних законів, які імперативно вимагають, щоб висновок був завжди істинним, логічні правила менш жорсткі. Вони надають можливість визнавати за істинні нові висловлення залежно від того, який вигляд мають висловлення-посилки, вже визнані за істинні.
Одним з основних правил умовиводу є вже знайоме правило відокремлення («modus ponens»), яке говорить, що умовивід є правильним, якщо з двох істинних посилок маємо істинний висновок. Більш строго це правило читається так: якщо істинна якась імплікація й істинна її умова, то має бути істинним і її висновок. Розглянемо приклад.
Вище наведено схему правильного умовиводу в тому Розумінні, що, підставляючи замість літер р і q конкретні висловлення, матимемо в результаті правильний умовивід, тобто правильність умовиводу з логічних міркувань полягає в тому, що до уваги береться тільки форма наявних у ньому посилок, абстрагуючись від їх змісту.
Повертаючись до питання про загальнозначущість еквіваленції, зазначимо, що еквіваленція в логіці предикатів так само, як і в логіці висловлень, тільки тоді буде загальнозначущою, коли значення істинності її членів за однакових значень їхніх змінних збігаються:
Зауважимо, що в логіці предикатів не існує такого простого способу розв'язування умовиводів, як таблиці істинності в логіці висловлень. Більше того, взагалі немає способу, який можна було б сміливо використовувати для розв'язання будь-яких виразів логіки предикатів. Зазвичай розв'язуваний вираз намагаються звести до виразу логіки висловлень.
Якщо для якоїсь області логічних побудов не існує процедури вирішення, то зазвичай намагаються з'ясувати, чи є дані вирази загальнозначущими. При цьому враховують, що кожний Вираз, виведений із загальнозначущого виразу, сам є загальнозначущим. Таким чином, якщо із загальнозначущих виразів удається вивести за допомогою відповідних перетворень, додержуючись правил виводу, розв'язний вираз, то можна з повним правом вважати, що знайдено індивідуальне доведення для даного виразу. Проте на практиці знайти таке доведення для будь-якого виразу часто буває дуже й дуже важко, оскільки тут багато що залежить від професійного досвіду, інтуїції, а також від дотримання певних загальних положень.
