Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Запитання для самоконтролю 1. Що називається бінарною резольвентою двох диз’юнктів у логіці предикатів? 2. Який процес називається методом резолюцій? 3. Що таке порожній диз’юнкт? 4. В чому суть процедури уніфікації формул логіки предикатів? 5. Яка множина літералів {L 1 , L 2 ,...L n } називається уніф ікованою? 6. Що таке множина неузгодженості літералів? Наведіть приклад. 7. Що таке найзагальніший уніфікатор? 8. Яка процедура називається склейкою? 9. Яка множина диз’юнктів називається невиконуваною? 10. В чому суть теореми про повноту резолюцій? 11. За якими кроками виконують перевірку на загальнозначущість 86 (тавтологію) формули логіки предикатів методом резолюцій? 12. Як перевірити логічність міркувань за допомогою методу резолюцій? ВПРАВИ 3.26. Знайти найзагальніший уніфікатор, якщо множина літералів уніфікується: а) ) ( ( ), ( b f P a P ; b) )) ( ( ), ( x f P x P ; c) ) , ( )), ( , ( z a P x f y P ; d) )) ( ), ( , ( ))), ( ( , , ( u f z f z P y g f x a P ; e) ) , ( )), ( ), ( ( y y Q x g a f Q . 3.27.Перевірити за допомогою методу резолюцій, чи правильні наступні схеми логічних слідувань: a) ) ) ( ) ( ( x P x M x , )) ( ) ( ( x M x S x ⊨ ) ) ( ) ( ( x P x S x ; b) )), ( ) ( ( x S x P x ) ) ( ) ( ( x P x Q x ⊨ ) ) ( ) ( ( x S x Q x ; c) )), ( ) ( ( x P x M x )) ( ) ( ( x S x M x ⊨ )) ( ) ( ( x P x S x ; d) )) ( ) ( ( ), ) ( ) ( ( x M x S x x M x P x ⊨ ); ) ( ) ( ( x P x S x e) )) ( ) ( ) ( ( )), ( ) ( ( x T x R x P x x Q x P x ⊨ )); ( ) ( ( x T x Q x f) )) ) , ( ) ( ( ) ( ( ))), , ( ) ( ( ) ( ( y x R y S y x P x y x R x Q y x P x ⊨ ); ) ( ) ( ( x S x Q x g) )) ( ) ( ( y C y S y ⊨ )). , ( ) ( ( )) , ( ) ( ( z x V z C z y x V y yS x 3.28.Довести правильність силогізмів Арістотеля. Навести приклад міркувань за кожною схемою: a) )) ( ) ( ( )), ( ) ( ( x M x S x x P x M x ⊨ )) ( ) ( ( x P x S x -фігура І, Darii; b) )) ( ) ( ( ), ) ( ) ( ( x M x S x x P x M x ⊨ ) ) ( ) ( ( x P x S x -фігура І, Ferio; c) )) ( ) ( ( )), ( ) ( ( x M x S x x P x M x ⊨ ) ) ( ) ( ( x P x S x -фігура ІІ, Baroko; d) )) ( ) ( ( ), ) ( ) ( ( x S x M x x P x M x ⊨ ) ) ( ) ( ( x P x S x -фігура ІІІ, Ferison; e) )) ( ) ( ( )), ( ) ( ( x S x M x x M x P x ⊨ )) ( ) ( ( x P x S x -фігура IV, Dimaris. 3.29. Перевірити, чи правильні міркування на базі логіки предикатів: a) всі цілі числа – раціональні. Деякі дійсні числа – цілі. Отже, деякі дійсні числа – раціональні; b) деякі парні функції періодичні. Жодна монотонна функція не є парною. Отже, жодна монотонна функція не періодична; 87 с) всі студенти КДПУ живуть у Кіровоградській області. Деякі жителі Кіровоградської області – пенсіонери. Отже, деякі студенти КДПУ – пенсіонери; d) всі вчителі – педагоги. Деякі педагоги нагороджені орденом. Отже, деякі вчителі нагороджені орденом; е) кожний атлет сильний. Кожний, хто сильний і розумний, доб’ється успіху. Петро атлет і розумний. Отже, він доб’ється успіху; f) всі боксери – спортсмени. Жоден спортсмен не курить. Отже, жоден курець не боксер; g) декому подобається співати. Дехто не любить нікого з тих, хто любить співати. Отже, декого люблять не всі; h) деякі студенти старанні. Жоден студент не позбавлений здібностей. Отже, деякі студенти, позбавлені здібностей, не старанні; і) дурень був би здатен на таке. Я не здатен. Отже, я не дурень; j) кожний, хто може розв’язати цю задачу – математик. Жоден математик не може її розв’язати. Отже, задача не має розв’язку; k) кожний радикал є прибічником прогресу. Деякі консерватори недолюблюють всіх прибічників прогресу. Отже, деякі консерватори недолюблюють всіх радикалів; l) формула логіки висловлень є тавтологією, якщо всі її диз’юнктивні одночлени містять контрарні пари літералів. Задана формула не тавтологія. Отже, принаймні один її диз’юнктивний одночлен не містить контрарної пари літералів; m) Деякі змії ядовиті. Ужі – змії. Отже, ужі ядовиті. 3.30.Перевірити за допомогою методу резолюцій, чи є наступні формули загальнозначущими (тавтологіями логіки предикатів): a) ) ( ) ( x P x x xP ; b) ) , ( ) , ( y x xR y y x yR x ; c) ))) ( ) , ( ( ) ( ( ) , ( x R x x xP x x R x x P x ; d) )) ( ) , ( ( )) ( ) , ( ( x R y x yP x x R y x P y x 3.5. ЗАСТОСУВАННЯ ЛОГІКИ ПРЕДИКАТІВ 3.5.1 Застосування символіки логіки предикатів в математичних формулюваннях 88 Під час вивчення математичних дисциплін різного спрямування доволі широко використовують символіку математичної логіки для скорочення запису того чи іншого математичного твердження. Особливо це стосується символіки логіки предикатів. Досить часто в математичних формулюваннях предметні змінні під знаком кванторів пробігають певну підмножину множини задання предикатів. Для прикладу розглянемо наступну формулу ) ), ( ( 1 1 2 1 y x f yP x Множиною інтерпретації оберемо множину дійсних чисел, функціональному символу ) ( 1 1 x f поставимо у відповідність операцію відшукання квадратного кореня, а предикатному символ ) , ( 2 1 y x P – предикат « y x ». Відмітимо, що наш предикат заданий на множині 2 R , але формула y x y x істинна лише для невід’ємних значень x та y. Тому, зі змістовної математичної точки зору це запишеться так ) ( x y R y R x Також, при вивченні математичних дисциплін дуже часто зустрічаються вирази «існує натуральне число», «для будь –якого дійсного числа», «існує єдиний елемент х» і т. д. . Тому в математиці використовуються так звані обмежені квантори. Це по суті скорочені записи тих чи інших формул логіки предикатів, а точніше – їх інтерпретацій. Наприклад, формули )) ( ( x P M x x і )) ( ( x P M x x з використанням обмежених кванторів загальності та існування запишуться наступним чином: )) ( ( x P x M x і )) ( ( x P x M x В подальшому будемо використовувати дещо зручнішу форму запису, а саме: )) ( ( x P M x і )) ( ( x P M x Тобто, для формули з нашого прикладу в тій інтерпретації ми мали б записати наступний вираз без використання обмежених кванторів: ) ( ) ( ) ( x y R y y R x x Також, при записі математичних понять використовують так званий квантор існування та єдиності x ! , який читається: «існує єдиний елемент х, такий, що…». Наприклад, запис ) ( ! x xP в розгорнутому вигляді є формулою y x y P x P y x x xP ) ( ) ( ) ( 3.5.2 Використання елементів математичної логіки для аналізу структури математичних теорем 89 Логіка предикатів дозволяє проаналізувати будову математичних теорем. В математичній науці найчастіше зустрічаються теореми 4 типів, які називають категоричними судженнями і які ми розглядали у пункті 3.1. Їх класифікація має наступний вигляд: A: «Всі S суть P» – загальностверджувальне судження; E: «Будь-яке S не є P» – загальнозаперечувальне судження; I: «Деякі S суть P» – частковостверджувальне судження; O: «Деякі S не є P» – частковозаперечувальне судження. В термінах логіки предикатів судження відповідних типів записуються наступним чином. A: ) ( ) ( x P x S x . Тобто судження типу А розуміють так: для будь-якого елемента х , якщо він має властивість S(x), то він має і властивість P(x). Прикладом такого судження може бути наступне: якщо функція диференційована, то вона неперервна. E: ) ( ) ( x P x S x . На мові логіки предикатів це означає наступне: для будь- якого елемента х , якщо він має властивість S(x), то він не має властивості P(x). Прикладом може бути судження: Якщо многокутник є трикутником, то він не може бути ромбом. I: ) ( ) ( x P x S x . В межах логіки предикатів судження типу І потрібно розуміти так: існує елемент х, який має властивість S(x) і одночасно має властивість P(x). Приклад: існують такі функції є неперервними і не диференційованими одночасно. O: ) ( ) ( x P x S x . З позиції логіки предикатів це судження потрібно розуміти так: існує елемент х, який має властивість S(x) і одночасно не має властивості P(x). Як приклад можна взяти наступне судження: існують такі многокутники, які є опуклими і не є чотирикутниками. В математичній теорії особливий інтерес становлять судження типу А, які можна записати наступним чином, використовуючи обмежені квантори: ) ( ) ( x P x S M x , де S(x) і P(x) – деякі предикати, задані на множині М, які описують ті чи інші властивості елементів цієї множини. Така конструкція теореми відповідає в математиці конструкції «якщо…, то…» або «нехай…, тоді…». В наведеному формулюванні чітко виділяють умову теореми S(x) та висновок теореми P(x). 90 Теорема вважається вірною, якщо множина істинності S M предиката S(x) непорожня і є підмножиною множини істинності предиката P(x). При цьому S(x) називають достатньою умовою для P(x), а P(x) – необхідною умовою для S(x). Також, як відомо ще з курсу шкільної математики, часто виділяють обернену та протилежну теореми. Так за наявності теореми ) ( ) ( x P x S M x твердження ) ( ) ( x S x P M x називається оберненим для даної теореми, твердження ) ( ) ( x P x S M x протилежною теоремою до теореми ) ( ) ( x P x S M x , а твердження ) ( ) ( x S x P M x протилежним до оберненої теореми ) ( ) ( x S x P M x Розглянемо спочатку поняття оберненої теореми. Отже теорема ) ( ) ( x P x S M x – пряма, а теорема ) ( ) ( x S x P M x – обернена до неї. Тоді для них можуть бути справедливими чотири випадки. 1) Обидві теореми вірні. Прикладом може бути твердження «Якщо у чотирикутника протилежні сторони взаємно паралельні, то такий чотирикутник паралелограм», і обернена їй «Якщо чотирикутник є паралелограмом, то його протилежні сторони – паралельні». 2) Пряма теорема вірна, а обернена – ні. Це можна побачити на такому прикладі: пряма теорема «Якщо функція інтегрована за Ріманом, то вона інтегрована і за Лебегом» є вірною, а обернена – «Якщо функція інтегрована за Лебегом, то вона інтегрована і за Ріманом» – невірна. 3) Пряма теорема невірна, а обернена вірна. Для цього випадку можна взяти в попередньому прикладі обернену теорему за пряму, а пряму – за обернену. 4) Обидві теореми невірні. Як приклад розглянемо твердження «Якщо число ділиться на 2, то воно ділиться і на 3» – пряма теорема, яка є не вірною, і обернена – «Якщо число ділиться на 3, то воно ділиться і на 2» – також є невірною. Розглянемо окремо випадок, коли обидві теореми, і пряма, і обернена, є вірними. Тоді кожне з них є одночасно і необхідною, і достатньою умовою для іншої. В такому випадку, для запису теорем використовують одну формулу 91 ) ( ) ( x P x S x , і формулювання обох теорем читають «для кожного елемента ) (x S M x має місце тоді і тільки тоді, коли має місце P(x)». Прикладом такого твердження може бути наступне: натуральне число ділиться на 6 тоді і тільки тоді, коли воно одночасно ділиться і на 2, і на 3. Далі розглянемо теорему ) ( ) ( x P x S M x , яка є протилежною до теореми ) ( ) ( x P x S M x . Такі теореми називаються взаємно протилежними. Також взаємно протилежними є теореми ) ( ) ( x S x P M x і ) ( ) ( x S x P M x . Між цими теоремами існує досить тісний зв’язок, а саме: ) ( ) ( ) ( ) ( x S x P M x x P x S M x , ) ( ) ( ) ( ) ( x P x S M x x S x P M x Ці рівносильності використовуються в математиці при так званому непрямому доведенні або доведенні від супротивного, коли, наприклад, замість теореми ) ( ) ( x P x S M x легше довести теорему ) ( ) ( x S x P M x |