|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Частина 2. Елементи математичної логікиСтр 1 из 12Следующая ⇒
Дискретний аналіз
Частина 2. Елементи математичної логіки
Курс лекцій для студентів спеціальностей, Пов ’ язаних з інформаційними технологіями та Захистом інформації
Рекомендовано Методичною радою НТУУ «КПІ»
Київ НТУУ «КПІ» 2010 Дискретний аналіз: Ч.2 Елементи математичної логіки: Курс лекцій для студентів спец., пов’язаних з інформ. технологіями та захистом інформації / Уклад. М.К.Мороховець. – К.: НТУУ «КПІ», 2010. –– 70 с., 8 рис., 4 джерела.
Гриф надано Методичною радою НТУУ «КПІ» (протокол № 5 від 21.01.2010 р.)
Навчальне видання
Дискретний аналіз
Частина 2. Елементи математичної логіки
Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та захистом інформації
ВСТУП Розділ «Елементи математичної логіки» є частиною курсу «Дискретний аналіз», що викладається студентам першого року навчання. Читачеві даного видання пропонується орієнтоване на початківців викладення базового розділу математичної логіки – логіки висловлень. Приділяється увага зв’язку між природною мовою та мовою логіки висловлень, підкреслено роль мови логіки висловлень як засобу подання міркувань. Розглянуто методи перевірки правильності міркувань, що можуть бути записані мовою логіки висловлень. Матеріал даного видання можна умовно поділити на дві частини – «теоретичну» та «практичну». У першій частині викладено основні теоретичні відомості з логіки висловлень, які подаються невеликими за обсягом порціями. Після кожної такої порції наведено контрольні питання й задачі та вправи, з якими студентам рекомендується працювати для кращого засвоєння матеріалу та набування навичок його практичного застосування. У другій, «практичній», частині видання розглянуто типові задачі, для розв’язання яких застосовуються методи математичної логіки, а саме: задача перевірки правильності міркування та задача сумісності (суперечності) сукупності тверджень. Докладно описано, як звести задачу перевірки правильності міркування до задачі перевірки логічного слідування формули логіки висловлень з сукупності формул логіки висловлень, а також як звести задачу перевірки сумісності сукупності тверджень до задачі перевірки тотожної хибності формули логіки висловлень. На простих, але змістовних прикладах проілюстровано, як використовувати методи, викладені у «теоретичній» частині даного видання для розв’язання цих задач. Мова логіки висловлень Висловленням будемо називати стверджувальне речення, яке може бути істинним або хибним, але не тим та іншим разом. Приклади висловлень: «Київ – столиця України»; «Місяць – супутник Землі». «Істина» або «хибність», приписані деякому висловленню, називаються істинносними значеннями цього висловлення і позначаються 1 і 0 відповідно. Будемо використовувати великі літери (можливо, з індексами) або ланцюжки таких літер для позначення висловлень. Наприклад, ми можемо позначити висловлення таким чином: U: Земля обертається навколо Сонця. Q: Троянда є рослиною. P: Мої друзі навчаються в університеті. Символи U, Q, P й т.п., що позначають висловлення, будемо називати атомарними формулами, або атомами. Для побудови складних висловлень у природній мові користуються сполучниками. Наведемо приклади. 1) Зараз іде дощ, й небо захмарене. 2) Якщо мами немає вдома, то ця дівчинка сумує. 3) Якщо літо спекотне або до нас приїжджають родичі з Сибіру, то ми відпочиваємо у горах. 4) Матриця має обернену тоді й тільки тоді, коли її визначник не дорівнює нулю. У логіці висловлень для побудови з атомарних формул складених виразів будемо використовувати логічні зв’язки: Ø – заперечення (аналог частки «не»), Ù – кон’юнкція (аналог сполучника «та», або «й»), Ú – диз’юнкція (аналог сполучника «або»), ® – імплікація (аналог зворотів «якщо …, то», «тільки тоді, коли…»), « – рівносильність, або еквівалентність (аналог звороту «тоді й тільки тоді, коли»). Дамо рекурсивне визначення формули (або правильно побудованого виразу) логіки висловлень. 1. Атом є формулою. 2. Якщо F – формула, то Ø(F) – формула. 3. Якщо F1, F2 – формули, то (F1)Ù(F2), (F1)Ú(F2), (F1)®(F2), (F1)«(F2) – формули. 4. Якщо F – формула, то (F) – формула. 5. Інших формул немає. Мовою логіки висловлень назвемо множину усіх формул (або правильно побудованих виразів) логіки висловлень. Приклади формул: (P)Ú ((Q) ® ((Ø(P)) Ù (R))); ((Q) « ((P) Ú (Ø(R)))); (Ø((Q) Ú (P))); (Ø((Р)Ú(Q)))«((Ø(R))®(Ø(Q))). Вирази PØ, ®PQÚ, PÙÚQ, «R(Ù) не є правильно побудованими. Якщо вважати, що логічним зв’язкам приписано ранг, що зменшується згідно з таким порядком: «, ®, Ú, Ù, Ø, й умовитися, що зв’язка з більшим рангом має більшу область дії, то без деяких дужок у формулах можна обійтися. Крім того, домовимося опускати зовнішні дужки формули та дужки біля атомів. Таким чином, R®PÚQ означає ((R)®((P)Ú(Q))), ØPÚQÙR®ØQÚP означає ((Ø(P))Ú((Q)Ù(R)))®((Ø(Q))Ú(P)), PÙØQ«R означає ((P)Ù(Ø(Q)))«(R). Формули можуть мати імена. На письмі ім’я формули розміщується перед формулою й між ними ставиться знак «=». Наприклад, F=РÚ(Q®R). Подамо у вигляді формул висловлення 1) - 4), наведені вище, або, іншими словами, виконаємо переклад цих висловлень мовою логіки висловлень. Для цього треба здійснити розбір кожного висловлення як речення української мови, виділити у кожному з них прості речення; розглядаючи кожне з простих речень як висловлення, увести для нього позначення (атом); потім з’ясувати, за допомогою яких мовних засобів з простих речень утворене складне речення, знайти у мові логіки висловлень відповідні логічні зв’язки й побудувати формулу з уведених атомів та знайдених логічних зв’язок, зберігаючи структуру даного висловлення. Отже, розглянемо висловлення 1): «Зараз іде дощ, й небо захмарене». Це є складносурядне речення; воно складається з двох простих речень, кожне з яких є простим висловленням («зараз іде дощ» та «небо захмарене»). Позначимо висловлення «зараз іде дощ» символом А, а висловлення «небо захмарене» – символом В (тобто уведемо атоми А та В). Зазначимо, що висловлення 1) утворене з виділених простих висловлень за допомогою сполучника «й», аналогом якого є логічна зв’язка Ù. Отже, висловлення 1) можна подати у вигляді такої формули логіки висловлень: АÙВ. Висловлення 2) складене з простих висловлень «мами немає вдома» (уведемо для його позначення атом С) та «ця дівчинка сумує» (уведемо для його позначення атом D) за допомогою звороту «якщо…, то», аналогом якого є логічна зв’язка ®. Отже, це висловлення можна подати у вигляді формули С®D. Висловлення 3) є складнопідрядним реченням, що складається з двох частин, кожна з яких є висловленням, а саме: «літо спекотне або до нас приїжджають родичі з Сибіру» та «ми відпочиваємо у горах»; ці частини з’єднані у одне речення за допомогою звороту «якщо…, то». Отже, переклад цього висловлення мовою логіки висловлень буде мати форму X®Y. Знайдемо тепер формули, які маємо підставити замість Х та Y. Зрозуміло, що замість Х треба підставити переклад мовою логіки висловлень фрази «літо спекотне або до нас приїжджають родичі з Сибіру», а замість Y – фрази «ми відпочиваємо у горах». Проаналізуємо висловлення «літо спекотне або до нас приїжджають родичі з Сибіру». Це є складне речення, що утворене з двох частин («літо спекотне» та «до нас приїжджають родичі з Сибіру», що з’єднані за допомогою сполучника «або», причому кожна з частин є простим висловленням. Отже, можемо увести атом Е замість висловлення «літо спекотне» та атом G – замість висловлення «до нас приїжджають родичі з Сибіру». Таким чином, перекладом висловлення «літо спекотне або до нас приїжджають родичі з Сибіру» буде формула ЕÚG, отже, ми знайшли вираз Х. Тепер знайдемо вираз Y. Для цього проаналізуємо висловлення «ми відпочиваємо у горах». Це є просте висловлення; уведемо для його позначення атом H. Отже, остаточно висловлення 3) перекладається формулою (ЕÚG)®Н. Висловлення 4) є складним реченням, дві частини якого («матриця має обернену» та «її визначник не дорівнює нулю») є простими висловленнями, що з’єднані (у речення) за допомогою звороту «тоді й тільки тоді, коли» (аналогом якого є логічна зв’язка «). Уводячи атом К замість простого висловлення «матриця має обернену» та атом L – замість простого висловлення «її визначник не дорівнює нулю», маємо для висловлення 4) формулу К«L.
Контрольні питання 1. Що таке висловлення? 2. Що таке атомарна формула? 3. Що таке формула логіки висловлень? 4. Що таке мова логіки висловлень? Задачі та вправи І. Подати висловлення формулами логіки висловлень. 1. Для того, щоб ціле число х було непарним, достатньо, щоб х було простим. 2. Якщо число х додатне, то х3 додатне. 3. Дане відношення є відношенням еквівалентності тоді й тільки тоді, коли воно рефлексивне, симетричне та транзитивне. 4. Для того, щоб число х було додатним, необхідно, щоб додатним було число х+1. 5. Якщо увечері буде дощ, то Петро або залишиться вдома й буде нудьгувати, або поїде на концерт на таксі. 6. Якщо Марійка стомлена чи зголодніла, вона не може працювати. 7. Ні «Зоря», ні «Карпати» не виграли чемпіонат з футболу минулого року. 8. Множини А та В рівні тільки тоді, коли А є підмножиною В. 9. Якщо х – ціле число, то х парне або непарне. 10. Петро любить подорожувати, але намагається не користуватися повітряним транспортом. ІІ. Нехай для позначення висловлень уведені атоми. Записати подані формули українською мовою. 1. P: «Йому потрібен лікар» Q: «Йому потрібен адвокат» R: «З ним трапився нещасний випадок» S: «Він хворий» T: «Він поранений». а) (S®P)Ù(R®Q), б) P®(SÚT), в) (PÙQ)®R, г) (PÙQ)«(SÙT), д) Ø(SÚT)®ØP, є) R®(PÚQ). 2. С: «Сьогодні ясно» R: «Сьогодні дощить» S: «Сьогодні падає сніг» Y: «Вчора було похмуро». а) С®Ø(RÙS), б) Y«C, в) (Y®R)ÚC, г) C«(RÙØS)ÚY, д) (C«R)Ù(ØSÚY), є) YÙ(CÚR).
Задачі та вправи І. Для кожної з поданих формул визначити, чи є вона: а) тотожно істинна, б) тотожно хибна, в) несуперечна. Обчислити кількість моделей для кожної з формул. 1. Ø(ØP)®P 2. P®(PÙQ) 3. Ø(PÚQ)ÚØQ 4. (PÚQ)®P 5. (P®Q)®(ØQ®ØP) 6. (P®Q)®(Q®P) 7. P®ØP 8. ØP®P 9. PÚ(P®Q) 10. (PÙ(Q®P))®P 11. PÚ(Q®ØP) 12. (PÚØQ)Ù(ØPÚQ) 13. ØPÙ(Ø(P®Q)) 14. (P«Q)®(PÙQ) 15. (PÚQ)®(PÙQ) 16. (PÙQ)®(PÚQ) 17. P®(Q®R)«(PÙQ)®R 18. ((PÚQ)Ù(P®R)Ù(Q®R))®R 19. RÙS®(P®ØQÚS) 20. (PÚØQ)ÚR®(SÙØP). ІІ. Нехай при інтерпретації h формула F приймає значення 1. Що можна сказати про істинносне значення формули F1 при інтерпретації h? 1. F = P®Q, F1= ØPÙQ«PÚQ 2. F = P«Q, F1= P«ØQ 3. F = Ø(P«Q), F1= ØP«Q 4. F = PÙQ, F1= (PÚQ)®(ØP®ØQ) 5. F = PÚQ, F1= P«Q. III. Довести твердження. 1. Формула F є тавтологією тоді й тільки тоді, коли формула ØF тотожно хибна. 2. Формула F тотожно хибна тоді й тільки тоді, коли формула ØF є тавтологією. 3. Якщо формула тотожно істинна, то вона несуперечна, але не навпаки. 4. Якщо формула суперечна, то вона не є тавтологією, але не навпаки. IV. Записати детальне доведення твердження 1. V. Нехай формули F1 та F1®F2 є тотожно істинними. Довести, що F2 тотожно істинна. VІ. Нехай формула F є тавтологією, A1, A2,…,An – атоми, що входять у F. Нехай формула F0 утворюється у результаті підстановки у F деяких формул F1,F2,…,Fn замість атомів A1,A2,…,An. Довести, що F0 є тавтологією.
Нормальні форми Формули F1 й F2 називаються еквівалентними, або рівносильними (позначається F1 = F2 ), якщо істинносні значення F1 й F2 збігаються при кожній інтерпретації F1 й F2. Можна показати, що виконуються такі співвідношення (символи 1, 0 означають відповідно тотожно істинну й тотожно хибну формули): 1) F1 « F2 = (F1®F2) Ù (F2®F1); 2) F1® F2 = ØF1 Ú F2; 3) F1 Ú F2 = F2 Ú F1; F1 Ù F2 = F2 Ù F1; (закони комутативності) 4) F1 Ú (F2 Ú F3) = (F1 Ú F2) Ú F3; (закони 5) F1 Ù (F2 Ù F3) = (F1 Ù F2) Ù F3; асоціативності) 6) F1 Ù (F2 Ú F3) = (F1 Ù F2) Ú (F1 Ù F3); (закони 7) F1 Ú (F2 Ù F3) = (F1 Ú F2) Ù (F1 Ú F3); дистрибутивності) 8) F1 Ú F1 = F1; F1 Ù F1 = F1; (закони ідемпотентності) 9) F1 Ú (F1 Ù F2) = F1; F1 Ù (F1 Ú F2) = F1; (закони поглинання) 10) Ø(F1 Ú F2) = ØF1 Ù ØF2; Ø(F1 Ù F2) = ØF1 Ú ØF2; 11) Ø(ØF1) = F1; Ø1=0; Ø0=1; 12) 1ÚF1=1; 1 Ù F1 = F1; 0 Ú F1 =F1; 0ÙF1=0, F1ÙØF1=0, F1ÚØF1=1. Внаслідок законів асоціативності дужки у формулах виду F1 Ú (F2 Ú F3) або (F1 Ú F2) Ú F3, а також у F1 Ù (F2 Ù F3) або (F1 Ù F2) Ù F3 можна опускати й писати F1 Ú F2 Ú F3 та F1 Ù F2 Ù F3. Отже, якщо F1, F2, …, Fn – формули, nÎN+, будемо писати F1Ú F2 Ú…Ú Fn й F1 Ù F2 Ù … Ù Fn замість F1 Ú (F2 Ú (… Ú Fn)…) й F1 Ù (F2 Ù (…Ù Fn)…). Вираз F1 Ú …Ú Fn (F1 Ù … Ù Fn) називається диз’юнкцією (кон’юнкцією) формул F1,…, Fn. Літерою називається формула, що має вигляд A або ØA, де A – атом. Літера, що не містить знак “Ø”, називається позитивною, інакше – негативною. Формула F є у кон’юнктивній нормальній формі (кнф, або КНФ), якщо F=F1Ù…ÙFn, де F1,…,Fn – формули, кожна з яких є літерою або диз’юнкцією літер, nÎN+. Диз’юнкт є диз’юнкція літер або літера. Надалі будемо іноді вважати вирази “множина літер” та “диз’юнкт” синонімами. Наприклад, QÚØPÚR={Q,ØP,R}. Диз’юнкт, що містить r літер, називається r-літерним диз’юнктом. Однолітерний диз’юнкт називається одиничним диз’юнктом. Диз’юнкт, що не містить жодної літери, називається порожнім (пустим) диз’юнктом (позначається c). Оскільки c не містить літер, які могли б бути істинними при якихось інтерпретаціях, то він є тотожно хибним. Нехай A – атом. Будемо називати літери A та ØA контрарними, а множину {A, ØA} – контрарною парою. Зауважимо, що диз’юнкт, який містить контрарну пару, є тавтоло-гією. Будемо називати такий диз’юнкт тавтологічним. Нехай S – множина диз’юнктів. Будемо вважати, що множині S відповідає формула, яка є кон’юнкцією усіх диз’юнктів з S. За кнф виду F1Ù…ÙFn побудуємо множину диз’юнктів {F1,…,Fn}. Отже, кнф будь-якої формули може бути подана у вигляді множини диз’юнктів, й навпаки, за множиною диз’юнктів може бути побудована формула у кон’юнктивній нормальній формі. Непорожню множину диз’юнктів S будемо називати суперечною, якщо формула, що є кон’юнкцією усіх диз’юнктів з S, є суперечною. Порожня множина диз’юнктів несуперечна, оскільки вона не містить диз’юнктів, які б могли приймати значення 0 при якихось інтерпретаціях. Формула F є у диз’юнктивній нормальній формі (днф, або ДНФ), якщо F=F1Ú…ÚFn, де F1,…,Fn – формули, кожна з яких є літерою або кон’юнкцією літер, nÎN+. Кон’юнкт є кон’юнкція літер або літера. Наприклад, нехай P, Q, R – атоми. Тоді (PÙØR)Ú(ØQÙRÙØP) є формула у диз’юнктивній нормальній формі. Для цієї формули F1 = PÙØR, F2 = ØQÙRÙØP; F1 є кон’юнкція літер P й ØR, а F2 є кон’юнкція літер ØQ, R, ØP. (QÚRÚP)Ù(ØRÚQ) – формула у кон’юнктивній нормальній формі. Для цієї формули F1 = QÚRÚP, F2 = ØRÚQ; F1 – диз’юнкція літер Q, R, P, а F2 – диз’юнкція літер ØR та Q. Твердження 2. Будь-яка формула логіки висловлень може бути перетворена у кнф та днф за допомогою співвідношень 1-12. Дійсно, для перетворення формули у кнф або днф слід послідовно та за потребою застосувати: співвідношення 1) F1 « F2 = (F1®F2) Ù (F2®F1) для вилучення зв’язки «, співвідношення 2) F1® F2 = ØF1 Ú F2 для вилучення зв’язки ®, тотожність 11) Ø(ØF1) = F1 для спрощення формули, співвідношення 10) Ø(F1 Ú F2) = ØF1 Ù ØF2; Ø(F1 Ù F2) = ØF1 Ú ØF2 для того, щоб перенести знак заперечення безпосередньо до атомів (зменшити область дії заперечення), закони комутативності, асоціативності та дистрибутивності, щоб побудувати кнф або днф, тотожності 8,9,12, щоб здійснити спрощення формули. Розглянемо приклад. Побудуємо кон’юнктивну нормальну форму для формули Q®(PÙØ(RÚØS)). Використовуючи співвідношення 1-12, маємо: Q®(PÙØ(RÚØS))=ØQÚ(PÙØ(RÚØS))=ØQÚ(PÙ(ØRÙS))=(ØQÚP)Ù(ØQÚ(ØR Ù S))=(ØQÚP)Ù(ØQÚØR)Ù(ØQÚS). Отже, кнф формули Q®(PÙØ(RÚØS)) є формула (ØQÚP)Ù(ØQÚØR)Ù(ØQÚS).
Контрольні питання 1. Які формули називаються рівносильними? 2. Що таке літера? 3. Що таке диз’юнкт? r-літерний диз’юнкт? одиничний диз’юнкт? порожній диз’юнкт? 4. Що таке контрарні літери? 5. Що таке тавтологічний диз’юнкт? 6. Що таке кон’юнкт? 7. Що таке кнф? днф? 8. Які формули логіки висловлень можна подати у кнф? у днф? 9. Які тотожності використовуються при побудові кнф (днф) формули? 10. Що таке суперечна множина диз’юнктів?
Задачі та вправи I. Подати формули у днф та кнф. 1. (ØPÙQ)®R 2. P®((QÙR)®S) 3. Ø(PÚØQ)Ù(S®T) 4. (P®Q)®R 5. Ø(PÙQ)Ù(PÚQ) 6. PÚ(ØPÙQÙR) 7. Ø(P®Q)Ú(PÚQ) 8. Ø(P®Q) 9. (P®Q)®R 10. (ØPÙQ)Ú(PÙØQ) 11. ((P®Q)®P)®P 12. P®(Q®(PÙQ)) 13. (P«Q)«(P«(Q«P)) 14. (P®(Q®S))®((P®Q)®(Q®S)) 15. S«P®(ØPÚS) 16. QÙØS®(P«S) 17. RÙS®(P®ØQÚS) 18. (PÚØQ)ÚR®(SÙØP) 19. (P®Q)«ØPÚQ 20. (P®QÙR)Ú(ØPÙQ®R). II. Довести тотожності 1-12. ІІІ. Перевірити кожну з поданих рівностей шляхом перетворення обох її частин у одну й ту саму нормальну форму. 1. (P®Q)Ù(P®R) = (P®(QÙR)) 2. (P®Q)®(PÙQ) = (ØP®Q)Ù(Q®P) 3. PÙQÙ(ØPÚØQ) = ØPÙØQÙ(PÚQ) 4. PÚ(P®(PÙQ)) = ØPÚØQÚ(PÙQ) 5. (P«Q)«R = P«(Q«R)
ЛОГІЧНЕ СЛІДУВАННЯ Ми бачили, що висловлення можна подавати за допомогою формул логіки висловлень. Часто нас цікавлять не окремі висловлення, а послідовності висловлень, що утворюють міркування, тобто такі послідовності тверджень, у яких останнє твердження є висновком з попередніх тверджень. Наведемо приклад міркування. Якщо йде дощ, то люди користуються парасольками. Іде дощ. Отже, люди користуються парасольками. Сукупність наведених трьох тверджень утворює міркування, у якому перші два твердження являються посилками, а останнє – висновком. Зазвичай твердження-висновок виділяється у міркуванні за допомогою слова «отже» (а також слів «таким чином», «з цього випливає» і т.п.). Щоб утворювати послідовності формул логіки висловлень, що є аналогами міркувань, уведемо поняття логічного слідування формули з сукупності формул. Формула F називається логічним наслідком формул F1,…,Fn (позначається F1,…,Fn╞═F), якщо при кожній інтерпретації, при якій усі формули F1,…,Fn істинні, формула F також істинна. Говорять, що формули F1,…,Fn є посилками F, а формула F випливає з F1,…,Fn, або має місце логічне слідування формули F з формул F1,…, Fn. З попереднього означення випливає, що формула F є логічним наслідком формул F1,…,Fn тоді й тільки тоді, коли кожна модель формул F1,…,Fn є моделлю формули F. Наведемо приклади логічного слідування. 1. Формула PÚQ є логічним наслідком формул P та Q. Дійсно, існує модель {P,Q} формул Р та Q, причому єдина. При інтерпретації {P,Q} формула PÚQ приймає істинносне значення 1. Отже, кожна модель формул P та Q є моделлю формули PÚQ, а це означає, що PÚQ є логічним наслідком P та Q. 2. Формула P®Q не є логічним наслідком формул ØQ та PÚQ, оскільки існує інтерпретація {P, ØQ}, при якій і ØQ, й PÚQ істинні, а P®Q хибна. Ми можемо використовувати логічне слідування для подання міркування. Застосовуючи означення поняття логічного слідування ми також можемо перевіряти правильність міркування. Розглянемо приклад. Чи є логічно правильним таке міркування? Дощ іде або спекотно. Якщо дощ не йде, то спекотно. Якщо дощ іде, то не спекотно. Отже, якщо спекотно, то дощ не йде. Можна сформулювати задачу інакше: чи випливає твердження «Якщо спекотно, то дощ не йде» з тверджень: «Дощ іде або спекотно», «Якщо дощ не йде, то спекотно», «Якщо дощ іде, то не спекотно»? Щоб відповісти на це запитання, спочатку запишемо дані твердження як формули логіки висловлень. Нехай D означає «Дощ іде», а S означає «спекотно». Тоді початкова задача зводиться до перевірки того, чи є формула S®ØD логічним наслідком формул DÚS, ØD®S, D®ØS. Оскільки, як неважко перевірити, формула S®ØD істинна при тих інтерпретаціях, при яких істинні формули DÚS, ØD®S, D®ØS, то S®ØD є логічним наслідком цих формул. Отже, твердження «Якщо спекотно, то дощ не йде» випливає з поданих тверджень. Поняття логічного слідування, суперечності та тавтологічності пов’язані між собою. Цей зв’язок визначає така теорема. Теорема 1. Нехай F1, F2, …, Fn, F – формули. 1) F1,F2…,Fn╞═ F тоді й тільки тоді, коли формула F1ÙF2Ù…ÙFn®F є тотожно істинною (тавтологією). 2) F1,F2,…,Fn╞═ F тоді й тільки тоді, коли формула F1ÙF2Ù…ÙFnÙØF тотожно хибна (суперечна). Доведемо перше з поданих тверджень. Покажемо спочатку, що якщо F1,F2…,Fn╞═ F, то формула F1ÙF2Ù…ÙFn®F є тотожно істинною. Нехай h – деяка інтерпретація формули F1ÙF2Ù…ÙFn®F. Можливі два випадки: 1) h(F1ÙF2Ù…ÙFn)=1, 2) h(F1ÙF2Ù…ÙFn)=0. Розглянемо перший випадок. З того, що h(F1ÙF2Ù…ÙFn)=1, випливає, що h(F1)=h(F2)=…=h(Fn)=1, тобто інтерпретація h є моделлю формул F1,F2,…,Fn. Оскільки виконується F1,F2…,Fn╞═ F, то h є також моделлю формули F, тобто h(F)=1. Тоді h(F1ÙF2Ù…ÙFn®F)=h(F1ÙF2Ù…ÙFn)®h(F) =1®1=1, отже, формула F1ÙF2Ù…ÙFn®F істинна при інтерпретації h. У другому випадку маємо: h(F1ÙF2Ù…ÙFn®F) = h(F1ÙF2Ù…ÙFn)®h(F) = 0®h(F)=1 незалежно від значення виразу h(F), тобто формула F1ÙF2Ù…ÙFn®F приймає значення 1 при інтерпретації h. Таким чином, за умови F1,F2…,Fn╞═ F формула F1ÙF2Ù…ÙFn®F приймає значення 1 при кожній інтерпретації. Тепер покажемо, що якщо формула F1ÙF2Ù…ÙFn®F тотожно істинна, то F1,F2…,Fn╞═ F. Нехай h – модель формул F1,F2…,Fn. Тоді h(F1ÙF2Ù…ÙFn) = 1. Оскільки F1ÙF2Ù…ÙFn®F тотожно істинна, то h(F1ÙF2Ù…ÙFn®F) =1. Але h(F1ÙF2Ù…ÙFn®F) = h(F1ÙF2Ù…ÙFn)®h(F) = 1®h(F) = 1, звідки випливає, що h(F)=1. Отже, кожна модель формул F1,F2…,Fn є моделлю формули F, тобто, F1,F2…,Fn╞═ F. Твердження доведено.
Контрольні питання 1. За якої умови можна стверджувати, що формула F є логічним наслідком формул F1,…,Fn? 2. Сформулюйте достатні умови того, що формула F є логічним наслідком формул F1,…,Fn. 3. Сформулюйте необхідні умови того, що формула F є логічним наслідком формул F1,…,Fn. Задачі та вправи І. Задано сукупність формул. Перевірити, чи є у цій сукупності формула, що являється логічним наслідком інших. 1. P®Q, P®R, Q®R 2. P®(Q®R), P®R, Q 3. P®Q, RÚP®RÚQ 4. P®(Q®R), Q®(P®R) 5. P®(Q®R), P®(P®R), P®Q 6. P®Q, P®R, P®(Q®R) 7. Ø(PÙQ), (Q®ØP) 8. ØP®ØQ, Q®P 9. PÙR®QÙS, P®Q, R®S 10. P®(Q®R), PÙQ®R. ІІ. Довести п.2 теореми 1.
Метод Девіса й Патнема Метод Девіса й Патнема дає можливість перевіряти суперечність множини диз’юнктів. Він базується на чотирьох правилах. 1. Правило тавтології. З множини диз’юнктів S вилучити усі тавтологічні диз’юнкти, якщо такі містяться у S. Позначимо множину диз’юнктів, що утворюється у результаті такого вилучення, через S¢. Якщо S¢=Æ, то дати відповідь «S несуперечна» та завершити роботу, інакше перевірити суперечність S¢. Зазначимо, що множина S суперечна тоді й тільки тоді, коли S¢ суперечна. Отже, однократне застосування правила тавтології до множини диз’юнктів S, що містить тавтологічні диз’юнкти, або дає відповідь на питання про суперечність S (якщо S¢=Æ, то S – несуперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S¢, яка містить менше диз’юнктів, ніж S. 2. Правило однолітерних диз’юнктів. Якщо в S існує одиничний диз’юнкт {L}, то спочатку побудувати множину S¢, вилучаючи з S ті диз’юнкти, що містять літеру L. Якщо S¢=Æ, то дати відповідь «множина S несуперечна» й завершити роботу. Якщо S¢¹Æ, то побудувати множину S², вилучаючи з диз’юнктів множини S¢ усі входження літери ØL. Якщо S² містить порожній диз’юнкт, то дати відповідь «множина S суперечна» та завершити роботу, інакше перевірити суперечність S². Зазначимо, що множина S суперечна тоді й тільки тоді, коли S² суперечна. Таким чином, однократне застосування правила однолітерних диз’юнктів до множини диз’юнктів, що містить одиничний диз’юнкт, або дає відповідь на питання про суперечність S (якщо S¢=Æ, то S – несуперечна, якщо cÎS², то S суперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S², яка містить менше диз’юнктів, ніж S. 3. Правило чистих літер. Назвемо літеру L, що входить у деякий диз’юнкт з S, чистою в S, якщо літера ØL не входить в жоден диз’юнкт з S. Якщо S містить літеру L, чисту в S, вилучити з S усі диз’юнкти, що містять L. Позначимо через S¢ множину диз’юнктів, що залишилися. Якщо S¢=Æ, то дати відповідь «S несуперечна» й завершити роботу, інакше перевірити суперечність S¢. Зазначимо, що S суперечна тоді й тільки тоді, коли S¢ суперечна. Отже, однократне застосування правила чистих літер до множини диз’юнктів S, що містить чисту літеру, або дає відповідь на питання про суперечність S (якщо S¢=Æ, то S несуперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S¢, яка містить менше диз’юнктів, ніж S. 4. Правило розщеплення. Вибрати літеру L, що має входження у який-небудь диз’юнкт з S. Подати множину S у вигляді (A1Ú L)Ù…Ù(AmÚL)Ù(B1ÚØL)Ù…Ù(BnÚØL)ÙR, де m,nÎN+, Ai (iÎ{1,…,m}), Bj Зазначимо, що S суперечна тоді й тільки тоді, коли S1 й S2 суперечні. Застосування правила розщеплення дає можливість звести задачу про суперечність множини диз’юнктів S до сукупності двох задач (про суперечність S1 та про суперечність S2), кожна з яких простіша, ніж задача про суперечність S. Метод Девіса й Патнема перевірки суперечності множини диз’юнктів S полягає у рекурсивному застосуванні до S правил 1-4 у зазначеному порядку. Розглянемо приклад. Перевіримо за допомогою методу Девіса й Патнема суперечність множини S = {ØPÚØQÚR, ØPÚQ, P, ØR, T}. За правилом 2 (з диз’юнктом {P}) маємо множину S1 = {ØQÚR, Q, ØR, T}. За правилом 2 (з диз’юнктом {ØR}) маємо множину S2 = {ØQ, Q, T}. За правилом 2 (з диз’юнктом {ØQ}) маємо множину S3 = {c, T}, яка є суперечною, оскільки містить порожній диз’юнкт. Отже, початкова множина диз’юнктів S суперечна.
Контрольні питання 1. Для розв’язання якої задачі застосовується метод Девіса й Патнема? 2. Яка літера називається чистою у множині диз’юнктів? 3. На яких правилах перетворення множини диз’юнктів ґрунтується метод Девіса й Патнема?
Метод резолюцій Правило резолюції. Нехай С1, С2 – диз’юнкти й С1=D1ÚL, С2=D2ÚØL, де D1, D2 – диз’юнкції літер, можливо, порожні, L, ØL – контрарні літери. Будемо говорити, що диз’юнкт C=D1ÚD2 утворюється за допомогою правила резолюції з диз’юнктів С1 та С2. Диз’юнкт С називається резольвентою диз’юнктів С1 та С2. Розглянемо приклад. Застосуємо правило резолюції до диз’юнктів С1 = RÚØQ та С2 = QÚP й побудуємо їх резольвенту. Оскільки С1 та С2 містять відповідно літери ØQ та Q, що складають контрарну пару літер, до них застосовне правило резолюції. Маємо резольвенту С = RÚP диз’юнктів С1 та С2. Теорема 2. Нехай С1, С2 – диз’юнкти, С – резольвента С1 та С2. Тоді С є логічним наслідком С1 та С2. Будемо говорити, що порожній диз’юнкт c виводиться з множини диз’юнктів S (або існує вивід диз’юнкту c з множини диз’юнктів S) за допомогою правила резолюції, якщо існує така скінченна послідовність диз’юнктів С1,…,Сk, що Сk= c й кожен диз’юнкт Сi даної послідовності (1£i£k) є або диз’юнктом з множини S, або резольвентою таких диз’юнктів Cn, Cm даної послідовності, що n<і та m<i. Послідовність С1,…,Сk, що задовольняє наведені умови, назвемо виводом порожнього диз’юнктуз множини диз ’ юнктів S за допомогою правила резолюції. За допомогою правила резолюції можна доводити суперечність формул логіки висловлень. Основою для цього є така теорема. Теорема 3 (про повноту). Множина диз’юнктів S суперечна тоді й тільки тоді, коли існує вивід порожнього диз’юнкту c з S за допомогою правила резолюції. Розглянемо приклад. Доведемо суперечність множини диз’юнктів S = {ØPÚQ, ØPÚØQÚR, P, ØR, T}, побудувавши вивід c з S за допомогою правила резолюції. 1. ØPÚØQÚR диз’юнкт в S 2. ØPÚQ диз’юнкт в S 3. P диз’юнкт в S 4. ØR диз’юнкт в S 5. T диз’юнкт в S 6. ØPÚR резольвента 1 та 2 7. R резольвента 3 та 6 8. c резольвента 4 та 7. Отже, маємо вивід ØPÚØQÚR, ØPÚQ, P, ØR, ØPÚR, R, c порожнього диз’юнкту з S за допомогою правила резолюції, а це означає, що множина S суперечна. Засоби обмеження перебору при застосуванні правила резолюції . Для доведення суперечності множини диз’юнктів S за допомогою правила резолюції достатньо знайти вивід порожнього диз’юнкту з S. Для доведення несуперечності множини диз’юнктів S за допомогою правила резолюції треба переконатися, що не існує виводу порожнього диз’юнкту з множини S. Перевірка суперечності множини диз’юнктів S методом резолюцій, тобто пошук виведення з S порожнього диз’юнкту за допомогою правила резолюції, може бути організована за таким планом. Спочатку будуємо усі резольвенти усіх пар диз’юнктів з S, поповнюємо множину диз’юнктів, включаючи у неї побудовані резольвенти, знову будуємо резольвенти й повторюємо описаний процес доти, поки не буде побудовано порожній диз’юнкт або виникають нові резольвенти (тобто такі, що не збігаються з побудованими раніше). Це означає, що послідовно породжуються множини S0, S1, S2,…, де S0=S, Sn={R: R є резольвента C1 та C2, C1Î(S0È…ÈSn-1), C2ÎSn-1}, n=1,2,…,. Необмежене використання правила резолюції при виведенні може призвести до породження великої кількості надлишкових (зайвих) резольвент, тобто таких диз’юнктів, що, наприклад, не входять до виводу c. Розглянемо деякі шляхи вирішення проблеми надлишкових резольвент при застосуванні метода резолюцій. Стратегія викреслювання. Ця стратегія виникла як узагальнення правила тавтології Девіса й Патнема. Визначимо деякі допоміжні поняття. Диз’юнкт С називається пiддиз’юнктом D (або таким, що поглинає D), якщо CÍD (нагадаємо, що вирази “множина літер” та “диз’юнкт” вважаються синонімами). Диз’юнкт D називається наддиз’юнктом С. Зазначимо, що коли D збігається з С, то D є наддиз’юнктом С. Нехай, наприклад, C=QÚØR, D=QÚPÚØR (тобто C={Q,ØR}, D={Q,P,ØR}). Оскільки {Q,ØR}Í{Q,P,ØR}, тобто СÍD, то C є піддиз’юнктом D, або С поглинає D, а D є наддиз’юнктом С. Стратегія викреслювання полягає у вилученні з множини диз’юнктів усіх тавтологій та диз’юнктів, що є наддиз’юнктами інших диз’юнктів. Розглянемо один з різновидів стратегії викреслювання, який є повним у тому розумінні, що при його застосуванні до множини диз’юнктів S вивід порожнього диз’юнкту існує тоді й тільки тоді, коли множина S суперечна. Нехай побудована множина (S0È…ÈSn-1). Обчислюємо резольвенти, вибираючи по порядку диз’юнкт C1 з множини (S0È…ÈSn-1) й диз’юнкт C2 з множини Sn-1. Якщо С1,С2ÎSn-1, то С1 має передувати С2. Якщо резольвента R диз’юнктів С1 та С2 існує, то вона включається у множину Sn у тому випадку, коли R не є тавтологією й не поглинається деяким раніше побудованим диз’юнктом. Стратегія вхідної резолюції. Дана стратегія базується на обмеженні використання правила резолюції: хоча б одна з двох посилок правила при побудові резольвенти має бути диз’юнктом з висхідної множини диз’юнктів. Назвемо таке правило виводу вхідною резолюцією, а виведення, у якому будь-яке застосування правила резолюції є вхідною резолюцією, – вхідним виведенням. Розглянемо приклад, який показує, що стратегія вхідної резолюції не є повною. Нехай S={PÚQ,PÚØQ,ØPÚQ,ØPÚØQ}. Множина S є суперечною, оскільки методом резолюцій можна побудувати вивід c з S. Дійсно: (1) PÚQ (2) PÚØQ (3) ØPÚQ (4) ØPÚØQ (5) Р резольвента (1) та (2) (6) ØP резольвента (3) та (4) (7) c резольвента (5) та (6) Застосуємо до S стратегію вхідної резолюції. Резольвенти, що є тавтологіями та наддиз’юнктами, викреслюються й у виведенні не показані. Праворуч від резольвент вказані номери диз’юнктів-посилок. (1) PÚQ (2) PÚØQ (3) ØPÚQ (4) ØPÚØQ (5) Р (1), (2) (6) Q (1), (3) (7) ØQ (2), (4) (8) ØР (3), (4) Диз’юнкти (5)–(8) – це диз’юнкти множини S1. Неважко бачити, що продовжуючи пошук вхідною резолюцією, можна побудувати лише тавтології та наддиз’юнкти тих резольвент, які одержані раніше. Отже, вхідного виведення c з S не існує. Стратегія одиничної резолюції. Дана стратегія базується на такому обмеженні використання правила резолюції: хоча б одна з двох посилок правила при побудові резольвенти має бути одиничним диз’юнктом. Назвемо таке правило виводу одиничною резолюцією, а виведення, у якому будь-яке застосування правила резолюції є одиничною резолюцією, – одиничним виведенням. Зв’язок між стратегіями одиничної та вхідної резолюції зрозумілий з такої теореми. Теорема 4. Для даної множини диз’юнктів S одиничне виведення c існує тоді й тільки тоді, коли існує вхідне виведення c. Як показано вище, стратегія вхідної резолюції не є повною, отже, згідно з наведеною теоремою, стратегія одиничної резолюції теж не є повною. Контрольні питання 1. Що таке резольвента двох диз’юнктів? 2. Що таке вивід порожнього диз’юнкту з множини диз’юнктів? 3. Що таке піддиз’юнкт (наддиз’юнкт) диз’юнкту? 4. Які існують засоби обмеження перебору при перевірці суперечності множини диз’юнктів методом резолюцій?
Задачі та вправи І. Перевірити суперечність поданих формул: а) шляхом побудови днф, 1. (ØPÚQ)ÙØQÙP 2. (PÚQ)Ù(ØPÚQ)Ù(ØRÚØQ)Ù(RÚØQ) 3. (PÚQ)ÙØQÙ(ØPÚQÚØR) 4. (PÚQÚØR)Ù(PÚØQ)ÙØPÙRÙT 5. PÙQÙRÙSÙ(ØPÚØQÚØRÚØS) 6. (PÚØQ)Ù(ØPÚQ)Ù(QÚØR)Ù(ØQÚØR) 7. (PÚQ)Ù(RÚQ)ÙØRÙØQ 8. (PÚQ)Ù(PÚØQ)Ù(RÚQ)Ù(RÚØQ) 9. (AÚB®CÙD)Ù(DÚE®G)Ù(AÚØG) 10. (PÚQ)Ù(QÚR)Ù(RÚS)Ù(ØRÚØP)Ù(ØSÚØQ)Ù(ØQÚØR) 11. (A®Ø(BÙC))Ù(DÚE®G)Ù(G®Ø(HÚI))Ù(ØCÙEÙH) 12. (A®B)Ù(C®D)Ù(B®D)Ù(ØC®A)Ù(E®G)Ù(G®ØD)Ù(ØE®E) 13. (A®BÙC)Ù(D®BÙE)Ù((G®ØA)ÙH®I)Ù((H®I)®GÙD)ÙØ(ØC®E). ІІ. Побудувати приклади суперечних множин диз’юнктів, для яких не існує вхідних виведень порожнього диз’юнкту. IIІ. Знайти усі моделі формули F шляхом побудови: а) днф, б) ПУДДР. 1. (СÙ(ØАÚ(В®С)))®(ВÙС) 2. (A®(ØBÚC))Ù(C®A) 3. Ø(ØА«(ВÙС)ÚВ) 4. (АÚØ(ВÚ(С«ØА))) 5. СÙ(Ø((ØАÚВ)®С)) 6. АÙØ(С®Ø(ВÚА)) 7. (СÚ(ØА«(ВÙС)))®А 8. Ø(АÚ(В«С))®(АÙС) 9. Ø(АÚВ)Ù((С«А)ÚВ) 10. (ВÙ(А®Ø(СÚА)))«А. IV. Нехай F – формула логіки висловлень. Як, використавши метод Девіса й Патнема, дізнатися, чи є F тавтологією? Чи можна встановити тавтологічниість формули F за допомогою методу резолюцій? V. Чи однаковими є ПУДДР, побудовані за формулою (А1«В1)Ù(А2«В2) з використанням різних лінійних порядків на множині атомів (A1<B1<A2<B2 та А1<А2<В1<В2 відповідно)? VI. Нехай S – множина диз’юнктів, до якої застосовне правило тавтології методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна Û S1 суперечна. VII. Нехай S – множина диз’юнктів, до якої застосовне правило розщеплення методу Девіса й Патнема, й S1 та S2 – результат застосування цього правила до S. Довести, що S суперечна Û S1 та S2 суперечні. VIII. Нехай S – множина диз’юнктів, до якої застосовне правило чистих літер методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна Û S1 суперечна. IX. Нехай S – множина диз’юнктів, до якої застосовне правило однолітер-них диз’юнктів методу Девіса й Патнема, й S1 – результат застосування цього правила до S. Довести, що S суперечна Û S1 суперечна. Х. Нехай існує доведення несуперечності формули F методом Девіса й Патнема. Сформулюйте правило побудови моделі F за цим доведенням.
ПРЕДМЕТНИЙ ПОКАЖЧИК
ЗМІСТ Вступ.....................................................................................................................3 Мова логіки висловлень......................................................................................4 Контрольні питання..................................................................................7 Задачі та вправи.........................................................................................8 Інтерпретації формул логіки висловлень..........................................................9 Контрольні питання................................................................................11 Задачі та вправи.......................................................................................12 Еквівалентні формули логіки висловлень. Нормальні форми......................13 Контрольні питання................................................................................16 Задачі та вправи.......................................................................................17 Логічне слідування............................................................................................17 Контрольні питання................................................................................20 Задачі та вправи.......................................................................................21 Методи перевірки тотожної хибності й тотожної істинності формул Метод перевірки суперечності й тавтологічності формул шляхом зведення до диз’юнктивної та кон’юнктивної нормальної форми.....22 Контрольні питання......................................................................22 Метод Девіса й Патнема.........................................................................23 Контрольні питання......................................................................25 Метод резолюцій.....................................................................................25 Контрольні питання......................................................................30 Метод двійкових діаграм рішень...........................................................30 Контрольні питання......................................................................35 Задачі та вправи.......................................................................................36 Приклади перевірки логічної правильності міркування...............................37 Перевірка правильності міркування за допомогою таблиць істинності...................................................................................40 Перевірка правильності міркування шляхом побудови диз’юнктивної нормальної форми або кон’юнктивної нормальної Перевірка правильності міркування методом Девіса й Патнема.......46 Перевірка правильності міркування методом резолюцій....................48 Перевірка правильності міркування шляхом побудови двійкової діаграми рішень.......................................................................................50 Контрольні питання................................................................................53 Приклади перевірки сумісності сукупності тверджень.................................54 Перевірка сумісності сукупності тверджень за допомогою таблиць істинності.................................................................................................55 Перевірка сумісності сукупності тверджень шляхом побудови диз’юнктивної нормальної форми.........................................................56 Перевірка сумісності сукупності тверджень методом Девіса й Патнема....................................................................................................59 Перевірка сумісності сукупності тверджень методом резолюцій......60 Перевірка сумісності сукупності тверджень шляхом побудови двійкової діаграми рішень......................................................................62 Контрольні питання................................................................................63 Список використаної та рекомендованої літератури.....................................64 Скорочення, символи та позначення...............................................................65 Предметний покажчик......................................................................................66 Слова іншомовного походження.....................................................................68
Дискретний аналіз
Частина 2. Елементи математичної логіки
Курс лекцій для студентів спеціальностей, |
Последнее изменение этой страницы: 2019-04-10; Просмотров: 360; Нарушение авторского права страницы