WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Логічний вивід і проблема розв'язання - Реферат

Логічний вивід і проблема розв'язання - Реферат

змінної.
Елементарна диз'юнкція є "завжди істинною" тоді і лише тоді, коли в ній міститься принаймні одна пара диз'юнктів, з яких один є якоюсь змінною, а другий - її запереченням. У цьому неважко переконатися, побудувавши відповідну таблицю істинності: пара названих диз'юнктів забезпечить наявність "і" (істина) в кожному рядку цієї таблиці, що є достатньою підставою для визнання подібної Диз'юнкції "завжди істинною" формулою, тобто законом логіки.
Формула логіки висловлювань має кон'юнктивну нормальну форму тоді, коли вона має такий вигляд: В,лВгл...лВт, де Вг В2,...Вп_ - елементарні диз'юнкції і
т>1. Так, формула pA(qvr)A(qvp) має кон'юнктивну нормальну форму (кон'юнкт р слід розглядати як вироджену диз'юнкцію з одним диз'юнктом).
Будь-яку формулу логіки висловлювань з допомогою ряду рівносильних замін можна звести до кон'юнктивної нормальної форми. Формулу, що є рівносильною даній і має кон'юнктивну нормальну форму, називають кон'юнктивною нормальною формою даної формули.
Щоб звести формулу до кон'юнктивної нормальної форми, треба насамперед з допомогою відповідної процедури звести її до нормальної форми. А потім кожну підформулу, що має вигляд (pv(qAr)) згідно з рівно-сильністю 6 і кожну підформулу типу ((qA.r)vp) згідно з рівносильністю 6' замінити формулою ((pvq)A A(pvr)). Річ у тім, що формула має кон'юнктивну нормальну форму лише за умови, що вона, по-перше, має нормальну форму, а по-друге, не містить у собі під-формул типу (pv(qAr)) і ((qAr)vp).
Розглянемо зведення формули до кон'юнктивної нормальної форми на такому прикладі: (р-хі)->(р~А~г).
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу (р-щ) будемо розглядати як антецедент (А), а підформулу (рХг) - як консеквент (В) імплікації А->В, одержимо: (p-q)v v(pAq).
2. Застосувавши правило усунення імплікації, яка є в першому диз'юнкті цієї формули (при цьому як антецедент виступає р, а як консеквент - q), одержимо:
(pVq)v(pAT).
3. Вдавшись до рівносильності 11 (другого закону де Моргана) і зробивши відповідну заміну першого диз'юнкта цієї формули, одержимо: (p=Aq~)v(pAr).
4. Застосувавши рівносильність 10 (перший закон де Моргана) до другого диз'юнкта формули, одержимо: (p=Aq~)v(pvr).
5. Звернувшись до першої рівносильності, правила усунення подвійного заперечення, одержимо: (pAq)v(pvr).
6. Остання заміна згідно з рівносильністю 6' ((BAC)VA): (pvpvT)A(qvpvr).
Далеко не всі формули мають лише одну кон'юнктивну нормальну форму.
Формула логіки висловлювань в КНФ є "завжди істинною" тоді, коли кожен її кон'юнкт, тобто кожна елементарна диз'юнкція, містить у собі принаймні одну змінну одночасно зі знаком заперечення і без нього. В тому, що формула, зведена до КНФ, є "завжди істинною", можна переконатися за її зовнішнім виглядом. Так, оскільки кожен кон'юнкт формули (pvqvp)A(pvqvq~)A(pvrvqvr) містить змінну зі знаком заперечення і без нього, то вона є "завжди істинною".
З допомогою КНФ визначають, є дана формула "завжди істинною" чи ні, а також чи є формула В логічним наслідком із формул Ар А2,..Лп.
Щоб перевірити, чи є довільна формула В наслідком із формул А[ГА2, ~Ап, треба приєднати В через імплікацію до формул Аг А2, ~Ап, і одержаний вираз звести до КНФ. Якщо одержана КНФ буде "завжди істинною", то це засвідчить, що В випливає з_А;, А,..., Ап.
Перевіримо, чи випливає В з формул В ->А, А як засновків. Поєднаємо ці засновки кон'юнкцією і приєднаємо до них В з допомогою імплікації: ((В->А)лА)->В.
Одержану формулу зведемо до КНФ:
1. Застосувавши рівносильність 13, одержимо ((B->A)AA)VB.
2. Вдавшись до рівносильності 10, одержимо ((BA)vA)vB.
3. Використавши рівносильність 13, одержимо ((BvA)vA)vB.
4. Застосувавши рівносильність 10, одержимо ((BAA)VA)VB.
5 Вдавшись до рівносильності 6', одержимо ((AVB)A(AVA))VB.
6. Застосувавши першу рівносильність, одержимо ((AVB)A(AVA))VB.
7. Усунувши JCOH'IOHKT, ЯКИЙ містить змінну та її заперечення (AvA), одержимо AvBvB. Оскільки ця формула є елементарною диз'юнкцією, яка містить змінну (В) і її заперечення (В), то це означає, що вихідна формула є "завжди істинною". Тому формула В є наслідком із формул В-*А і А.
Розрізняють ще досконалу кон'юнктивну нормальну форму (ДКНФ) і скорочену кон'юнктивну нормальну форму (СДНФ), з допомогою яких розв'язують задачі на знаходження всіх логічних наслідків з даної формули.
Диз'юнктивна нормальна форма
Диз'юнктивна нормальна форма формул логіки висловлювань є диз'юнкцією елементарних кон'юнкцій.
Елементарною кон'юнкцією є формула, що має такий вигляд: А1лА2л...лА , де п>1, а кожна з формул Ар А2, ..., Ап є змінною, або запереченням змінної. Так, формула (рлс[лглд) є елементарною кон'юнкцією, чого не можна сказати про формулу (дл(дуг)лрлг), оскільки другий її кон'юнкт не є ні змінною, ні запереченням змінної.
Елементарна кон'юнкція є "завжди хибною" тоді й тільки тоді, коли до її складу входить принаймні одна пара кон'юнктів, з яких один є якоюсь змінною, а другий - її запереченням.
Формула логіки висловлювань має диз'юнктивну нормальну форму тоді, коли вона має такий вигляд: В vB2v...vBm, де Вр В2.." Вт є елементарними кон'юнк-щями, а т>1.Наприклад: (pXqAr)vp~v(qAr).
Будь-яку формулу логіки висловлювань з допомогою відповідних рівносильних замін можна звести до диз'юнктивної нормальної форми. Формулу, що є рівносильною даній і має диз'юнктивну нормальну форму, називають диз'юнктивною нормальною формулою даної формули. Щоб звести формулу до ДНФ, необхідно насамперед звести її до нормальної форми, а потім кожну під-формулу типу (AA(BVCJ) згідно з рівносильністю 7 і кожну підформулу типу ((BVC)AA) згідно з рівносильністю Т замінити формулою ((AAB)V(AAC)).
Розглянемо процедуру зведення формули до диз'юнктивної нормальної форми на такому прикладі:
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу р будемо розглядати як антецедент, а підформулу ((p->q)->q) - як кон-секвент), одержимо: pv((p->q)->q).
2. Знову вдавшись до правила усунення імплікації (на цей раз роль антецедента виконує підформула (р-щ), а консеквента - q, одержимо: pv((p->q)vq)-
3. Застосувавши правило усунення імплікації (антецедент - р, а консеквент - q), одержимо: pv((pq)vq).
4. Використавши другий закон де Моргана, одержимо: pv((pAq)vq).
5. Залишається лише усунути подвійне заперечення і зайві дужки: p~v(pAq)vq.
Формула може мати не одну ДНФ.
З допомогою ДНФ з'ясовують, по-перше, є дана формула "завжди хибною" чи ні, а по-друге, чи є та чи інша формула наслідком з відповідних засновків.
Формула, що має ДНФ, є "завжди хибною" тоді й тільки тоді, коли "завжди хибними" є всі її диз'юнкти, тобто коли кожна елементарна кон'юнкція містить у собі принаймні одну пару кон'юнктів, один з яких є якоюсь змінною, а другий - її запереченням. Таким чином, за виглядом елементарної кон'юнкції можна робити висновок, є вона "завжди хибною" чи ні. Так, формула ((pAqAp)v(qAq)v(pAqArAr)) є "завжди хибною", оскільки загалом вона є диз'юнкцією, кожен диз'юнкт якої (елементарна кон'юнкція) є "завжди хибним".
Розрізняють ще досконалу диз'юнктивну нормальну форму (ДДНФ) і скорочену диз'юнктивну нормальну форму (СДНФ), кожна з яких дає змогу розв'язувати відповідні задачі.
Loading...

 
 

Цікаве