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

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

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

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

електропровідний" і "Цей предмет не є металевим або він електропровідний".
Приклад рівносильності 14- (АлВ) = (AvB ):"Рошб
має рівні і попарно паралельні сторони" і "Хибно, що
в ромба сторони не є рівними або не попарно паралель
ними". _ _
Приклад рівносильності 15 - (AvB) = (АлВ): "Цей кут є прямим або тупим" і "Хибно, що цей кут не є ні прямим, ні тупим".
Рівносильність 18 - (AvB)л(AvB) = В - називається законом виключення; рівносильності 19 і 20 - Ал(АВ) = А; Av(AлB) =А - законами поглинання; рівносильності 21 і 22_- (А?)л(В?)=_(А?)л(В? v(AvB); (AAC)V (ВЛС) = (АлС (BлC)v(AлB) - законами виявлення.
Рівносильності 23-27 є похідними від перерахованих рівносильностей 1-22.
Вдаючись до рівносильностей 1-27 і правил заміни, виводять рівносильності 28-34.
Особливе місце належить у системі виводу рівносильним формулам, до складу яких входять "завжди істинні" або "завжди хибні" підформули. Зрозуміло, що всі "завжди істинні" формули рівносильні одна одній. Це стосується і "завжди хибних" формул: вони теж рівносильні між собою. Згідно з таблицею істинності заперечення, заперечення "завжди істинної" формули є "завжди хибною" формулою, і навпаки. Так, оскільки формула А /ІГ" завжди істинна", то формула AvA є "завжди хибною" (або: оскільки формула АлА "завжди хибна", то її заперечення АлА є "завжди істинною" формулою).
Позначивши буквою "і" "завжди істинну" формулу, а буквою "х" "завжди хибну", одержують рівно-сильності 43-50'.
Логічний вивід будується на таких засадах. На будь-якому кроці побудови виводу можна дописати до послідовності формул:
1) будь-яку частину наявної формули (підформулу) або її заперечення як припущення;
2) формулу, що випливає із записаних вище формул послідовності за одним із правил логічного виводу або рівносильну якійсь із записаних вище;
3) раніше доведену формулу.
Якщо засновки є повними, тобто достатніми для одержання однозначного висновку, і несу переч ливими, то одне із суперечних припущень призведе до суперечності (що дає підставу вважати його неспроможним), а друге - до несуперечливого шуканого висновку. Якщо ж засновки суперечливі, то в обох випадках ми прийдемо до суперечності, що буде достатньою підставою для того, щоб вважати хибними принаймні деякі засновки. І, нарешті, коли засновки є несуперечливи-ми, але неповними, то з обох суперечних припущень будуть випливати різні висновки, які разом з тим не ведуть до суперечливості сам вивід.
Розглянемо названі ситуації на прикладах.
Дано чотири засновки, з яких потрібно вивести висновок:
1. А-В.
2V C->A.
3. АуС.
4. АВ.
Перший хід міркування:
5. А (припущення).
6. В (усунення імплікації: 1; 5).
7. С (усунення строгої диз'юнкції: 3; 5).
8. В (усунення еквіваленції: 4; 5) - суперечність: 6; 8.
9. А (усунення імплікації 1; 8) - суперечність: 5; 9. 10. АлВлСлВлА (введення кон'юнкції: 5; 6; 7; 8; 9).
Другий хід міркування:
5. А (припущення).
6. С (усунення імплікації: 2; 5).
7. С (усунення строгої диз'юнкції: 3; 5) - супереч-ність: 6; 7.
8. Б (усунення еквіваленції: 4; 5).
9. АлСлСлВ (введення кон'юнкції: 5; 6; 7; 8).
Як бачимо, з обох суперечних припущень одержані суперечливі наслідки, що свідчить про суперечність засновків.
Розглянемо іншу ситуацію. Дано чотири засновки, з яких потрібно зробити висновок:
1. А-С.
2. AvB.
3. С-В.
4. CvA.
Перший хід міркування:
5. А (припущення).
6. С (усунення імплікації: 1; 5).
7. В (усунення строгої диз'юнкції: 2; 5).
8. С (усунення імплікації: 3; 7).
9. А (усунення нестрогої диз'юнкції: 4; 8).
10. АлСлВлСлА (введення кон'юнкції: 5; 6; 7; 8; 9). Другий хід міркування:
5. А (припущення).
6. В (усунення строгої диз'юнкції: 2; 5).
7. С (усунення нестрогої диз'юнкції: 4; 5).
8. А (усунення імплікації: 1; 7).
9. В (усунення імплікації: 3; 7).
Ю. АлВлСлАлВ (введення кон'юнкції).
Оскільки жодне із суперечних припущень не призвело до суперечності міркування, то звідси випливає висновок: засновки потребують доповнення.
До припущень вдаються не завжди, а лише тоді, коли без них не можна зробити черговий крок логічного виводу (іноді припущення дає можливість скоротити шлях розв'язання задачі). Якщо нам дано засновки:
1. А->В.
2. CvA.
3. B->D.
4. CAD,
то немає потреби вдаватися до припущення, оскільки четвертий засновок містить пряму інформацію про С і D.
5. Q (усунення кон'юнкції: 4);
6. j=) (усунення кон'юнкції: 4);
7. А (усунення нестрогої диз'юнкції: 2; 5);
8. В (усунення імплікації: 3; 6);
9. В (усунення імплікації: 1; 7);
10. CADAAABAB (введення кон'юнкції: 5; 6; 7; 8; 9).
11. CADAAABAB (усунення подвійного заперечен
ня - УПЗ).
12. CADAAAB (згідно із законом ідемпотентності).
А якщо без припущення не можна обійтися, то яку
ж змінну треба вибирати як припущення? Ту, з якої можна вивести якомога більше наслідків. Так, маючи засновки
1. С-*А.
2. В->С-
3. AvB,
з яких потрібно зробити висновки, ми змушені брати за припущення С, оскільки саме воно дає можливість вивести найбільше висновків. Інші припущення тут неефективні: припущення В дає можливість одержати лише один висновок -С , а припущення А - жодного:
4. С (припущення).
5. А (усунення імплікації: 1; 5).
6. S (усунення імплікації: 2; 5).
7. А (усунення нестрогої диз'юнкції: 3; 6).
Щоб застосувати теорію логічного виводу у розв'язанні практичних задач, потрібно послідовно здійснити кілька операцій. Наприклад, у нас є такі дані:
Коло підозрюваних у скоєнні злочину обмежується чотирма особами: Івановим, Петровим, Сидоровим, Федотовим.
1. Іванов міг брати участь у скоєнні злочину тоді і тільки тоді, коли до цього злочину причетний і Петров.
2. Якщо до цього злочину не причетний Сидоров, то в ньому брав участь Федотов.
3. Відомо, що один і тільки один із підозрюваних Іванов або Сидоров - причетні до цього злочину.
4. Федотов довів своє алібі.
Насамперед потрібно виділити прості судження з цього тексту і позначити їх пропозиційними змінними. Ось ці судження:
1. Іванов брав участь у скоєнні злочину (А).
2. Петров брав участь у скоєнні злочину (В).
3. Сидоров брав участь у скоєнні злочину (С).
4. Федотов брав участь у скоєнні злочину (?>). Після цього слід виділити логічні зв'язки, які є в
цьому тексті (і відповідно їх розставити): , у.
Поєднавши пропозиційні змінні (А, В, С, D) відповідними логічними термінами (зв'язками), одержимо такі висловлювання:
1. АВ.
2. С->?".
3. АуС;
4. D
Оскільки в нас є пряма інформація про алібі Федотова - D, то немає потреби вдаватися до припущення. Далі вивід будуємо так:
5. С (усунення імплікації: 2; 4).
6. А (усунення строгої диз'юнкції: 3; 5).
7. В (усунення еквіваленції: 1; 6).
8. БлСлАлВ (введення кон'юнкції: 4; 5; 6; 7). Залишається лише зробити переклад одержаного
висновку на природну мову: "Ні Федотов, ні Іванов, ні Петров не причетні до скоєння злочину. Злочин скоїв Сидоров".
Проблема розв'язання і розв'язуючі процедури
Оскільки висновок виводу (останнє у відповідній послідовності, вивідне висловлювання) не завжди з необхідністю випливає із засновків, то доводиться вдаватися до різних процедур, щоб довести, що
Loading...

 
 

Цікаве