1. ПРЕДМЕТ І ЗНАЧЕННЯ ЛОтКИ


Назва1. ПРЕДМЕТ І ЗНАЧЕННЯ ЛОтКИ
Сторінка6/15
Дата15.03.2013
Розмір1.48 Mb.
ТипДокументи
bibl.com.ua > Фізика > Документи
1   2   3   4   5   6   7   8   9   ...   15

Кон'юнктивна нормальна форма

Кон'юнктивна нормальна форма формул логіки висловлювань є кон'юнкцією елементарних диз'юнкцій.

Елементарною диз'юнкцією є формула, що має такий вигляд: A1vA2v...vAn, де п>1, а кожна з формул Ар А2, ..А є змінною або запереченням змінної. Так, формула (pvqvrvs) є елементарною диз'юнкцією, чого не можна сказати про формулу (pvqv(pAr)vs), оскільки третій її диз'юнкт (рлг) не є ні змінною, ні запереченням змінної.

Елементарна диз'юнкція є «завжди істинною» тоді і лише тоді, коли в ній міститься принаймні одна пара диз'юнктів, з яких один є якоюсь змінною, а другий — її запереченням. У цьому неважко переконатися, побудувавши відповідну таблицю істинності: пара названих диз'юнктів забезпечить наявність «і» (істина) в кожному рядку цієї таблиці, що є достатньою підставою для визнання подібної Диз'юнкції «завжди істинною» формулою, тобто законом логіки.

Формула логіки висловлювань має кон'юнктивну нормальну форму тоді, коли вона має такий вигляд: В,лВгл...лВт, де Вг В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)) є «завжди хибною», оскільки загалом вона є диз'юнкцією, кожен диз'юнкт якої (елементарна кон'юнкція) є «завжди хибним».

Розрізняють ще досконалу диз'юнктивну нормальну форму (ДДНФ) і скорочену диз'юнктивну нормальну форму (СДНФ), кожна з яких дає змогу розв'язувати відповідні задачі.

Логіка - Тофтул:6.1. Безпосередні умовиводиБезпосередній умовивід — умовивід, до складу якого входить лише один засновок (і, звичайно ж, — висновок).

Оскільки його засновок виражається судженням, то цей вид умовиводу здійснюється у формі перебудови судження. За способом перебудови судження-зас-новку розрізняють такі види безпосередніх умовиводів: перетворення, обернення, протиставлення предикатові, протиставлення суб'єктові.

Перетворення — перебудова судження, внаслідок якої з вихідного утворюють нове рівнозначне судження, але протилежної якості: стверджувальне судження перетворюється на заперечне, а заперечне — на стверджувальне.

Підставою для одержання висновку за схемою перетворення виступає закономірність відношення обсягів двох суперечних понять, які є предикатами стосовно одного й того ж суб'єкта, будь-які два видових суперечних поняття завжди вичерпують обсяг відповідного родового поняття. Якщо обсяг суб'єкта входить до обсягу предиката Р, то звідси випливає, що він не входить до обсягу предиката не-Р, і навпаки. Так, виходячи з того, що ссавці належать до хребетних, з необхідністю доходимо висновку, згідно з яким ссавці не належать до нехребетних (безхребетних).

У кожному стверджувальному судженні («S є Р») безпосередньо виражається тотожність предметів класу S з множиною інших предметів в ознаках, характерних для предметів класу Р. Та разом з названою тотожністю в цьому судженні неявно стверджується і відмінність від усіх предметів, які не належать до класу Р. А в заперечному судженні («S не є Р») безпосередньо виражається відмінність предметів класу S від усіх предметів класу Р, а тим самим опосередковано визнається тотожність предметів S з усіма предметами ue-Pv Тобто завдяки перетворенню у стверджувальному судженні виявляється відношення відмінності, а в заперечному — відношення тотожності, які неявно мис-ляться в названих типах суджень.

Не випадково, що одна і та сама схема (див. схему 18) одночасно ілюструє і судження «Всі ссавці — хребетні», і судження «Жоден (всі) ссавець не є нехребетним».

Перше ілюструється сумісністю понять «ссавці» і «хребетні», а друге — несумісністю понять «ссавці» і «нехребетні (безхребетні)».

Перетворення суджень типу А, Е, І, О відбувається за такими схемами:

А. Всі S є Р. Отже, жодне S не є не-Р. Всі метали — електропровідні.

Отже, жоден метал не є неелектропровідним.

Е. Жодне S не є Р. Отже, всі S є не-Р. Жоден патріот не є зрадником.

Отже, кожен патріот є незрадником.

І. Деякі S є Р. Отже, деякі S не є не-Р. Деякі числа — прості.

Отже, деякі числа не є непрості.

О. Деякі S не є Р. Отже, деякі S є не-Р. Деякі числа не є прості.

Отже, деякі числа є непрості.

Здійснюючи перетворення судження, необхідно змінити його якість, залишивши без змін кількість. Замінивши зв'язку «є» на «не є», домагаємося перетворення стверджувального судження на заперечне. Але одержане судження виявляється нерівнозначним вихідному. Щоб нейтралізувати вказаний вплив частки «не», треба ввести ще одну аналогічну частку, приєднавши її до імені, яким позначається предикат висновку. Внаслідок такої процедури предикатом висновку стає поняття, суперечне предикатові засновку. А замінивши зв'язку «не є» заперечного судження-засновку на «є», домагаємося перетворення заперечного судження на стверджувальне. Але при цьому знову змінюється зміст вихідного судження. Вихід тут один: до імені, яким позначається предикат висновку, слід додати частку «не», тобто знову-таки предикат засновку замінюється у висновку на суперечне йому поняття.

Під збереженням кількості судження мають на увазі, що загальностверджувальне судження перетворюється на загальнозаперечне (і навпаки), а частково-стверджувальне — на частковозаперечне (і навпаки). Безпосередньо ж це виявляється в збереженні тих самих кванторів (чи відповідних кванторних слів).

Результат перетворення можна знову перетворити на вихідне судження. Ця закономірність виражається таким правилом: подвійне заперечення будь-чого рівносильне ствердженню того ж самого.

Наприклад:

Київ — столиця України.

Отже, Київ не є нестолицею України.

Отже, Київ є не нестолицею України (що рівнозначно судженню: «Київ — столиця України»).

Обернення — перебудова судження, внаслідок якої суб'єкт і предикат міняються місцями. При цьому якість судження зберігається, а кількість може змінюватися.

Основою для обернення є, зокрема, та обставина, що в судженні містяться знання про предмети, які мисляться як у суб'єкті, так і в предикаті. Внаслідок обернення змінюється предмет думки.

Наприклад:

Всі метали — електропровідні.

Отже, деякі електропровідні — метали.

Предметом думки в засновку були метали, а у висновку — електропровідні (схема 19).

В-обох судженнях мислиться тільки те, що передається на схемі заштрихованою її частиною. У першому судженні обсяг поняття «метали» (менший круг на схемі) ототожнюється з частиною обсягу поняття «електропровідні» (на схемі — та частина більшого круга, яка закрита меншим). А в другому судженні (висновку) — навпаки.

Здійснюючи обернення, необхідно дотримуватися вимоги рівності обсягів термінів: обсяги термінів висновку повинні дорівнювати обсягам відповідних термінів засновку. Правда, сама структура судження не завжди чітко виражає характер обсягу термінів. Це стосується передусім предикатів стверджувальних суджень.

Традиційно розрізняють два види обернення: просте, або чисте, і обернення з обмеженням. Проте такий поділ має штучний характер.

Розглянемо, як здійснюється обернення суджень, різних за кількістю і якістю (А, Е, І, О).

1. Загальностверджувальне судження (А) перебудовується при оберненні, як правило, на частково-стверджувальне.

Наприклад:

Всі метали — електропровідні (А).

Отже, деякі електропровідні — метали (/).

Деякі загальностверджувальні судження перебудовуються при оберненні на загальностверджувальні. Це стосується виділяючих суджень.

Наприклад:

Всі люди, і тільки люди, — мислячі істоти (А).

Отже, всі мислячі істоти — люди (А).

Хоч названі приклади обернень і не суперечать вимогам логіки, проте їх не можна вважати зразковими, оскільки в їх висновках втрачається частина знань, які мали місце в засновках. Щоб не зазнати цієї втрати, обернення слід здійснювати так: «Всі метали електропровідні. Отже, деякі електропровідні, і лише вони, — метали». Це стосується і другого прикладу.

2. Загальнозаперечне судження (Е) обертається на загальнозаперечне.

Наприклад:

Жоден патріот не відмовляється від культури сво-

го народу ().

Отже, жоден з тих, хто відмовляється від культури свого народу, не є патріотом (Е).

3. Частковостверджувальне судження (І) при оберненні, як правило, перебудовується на частковоствер-джувальне.

Наприклад:

Деякі вчені — митці (/).

Отже, деякі митці — вчені (І).

Зрідка частковостверджувальні судження перебудовуються при оберненні на загальностверджувальні. Це стосується виділяючих суджень.

Наприклад:

Деякі люди, і тільки люди, мають високу мораль.

Отже, всі, хто має високу мораль, — люди.

4. Обернення частковозаперечного судження дає бідні, невизначені знання, тому до обернення суджень цього виду практично не вдаються.

Наприклад:

Деякі птахи не хижаки (О).

Отже, жоден хижак не належить до птахів-нехи-жаків (Е).

Протиставлення — перебудова судження, в ході якої одночасно здійснюються і перетворення, і обернення в тій чи іншій послідовності.

Якщо судження спочатку перетворюється, а потім обертається, то такий умовивід називається протиставленням предикатові. А якщо судження спочатку обертається, а потім перетворюється, то тоді ми маємо справу з протиставленням суб'єктові.

При протиставленні предикатові суб'єкт вихідного судження стає предикатом висновку, а суб'єктом висновку виступає поняття, суперечне предикатові вихідного судження (засновку).
1   2   3   4   5   6   7   8   9   ...   15

Схожі:

ПЕРЕЛІК ОРІЄНТОВНИХ ПИТАНЬ ДЛЯ ПІДГОТОВКИ ДО СЕМЕСТРОВОГО ЕКЗАМЕНУ З ПСИХОЛОГІЇ
Загальне поняття про психологію, її предмет та завдання психологія як наука і навчальний предмет, її значення
Астрономії. Її розвиток та значення в житті суспільства КОНСПЕКТ...
КОНСПЕКТ УРОКУ Предмет астрономії. Ії розвиток та значення в житті суспільства. Методи та засоби астрономічних спостережень
Календарне планування
...
ПЕРЕЛІК КОНТРОЛЬНИХ ТЕМ І ПИТАНЬ
Предмет, принципи, джерела й значення вивчення курсу «Історія України в контексті всесвітньої історії»
Предмет, завдання і методи патологічної фізіології. Значення експериментального...
Дати студентам уявлення про патофізіологічний експеримент, ознайомити їх з основними видами експерименту і технікою фік­сації лабораторних...
ТЕМА ЗМІСТ НАВЧАЛЬНОГО МАТЕРІАЛУ
ПРЕДМЕТ АСТРО­НОМІЇ, її РОЗВИТОК І ЗНАЧЕННЯ В ЖИТТІ СУ­СПІЛЬСТВА. КОРОТКИЙ ОГЛЯД ОБ'ЄКТІВ ДОСЛІДЖЕННЯ В АСТРОНОМІЇ
МІЖНАРОДНИЙ НАУКОВО-ТЕХНІЧНИЙ УНІВЕРСИТЕТ
Поняття кримінально-процесуального доказування та його значення. Предмет доказування
План Вступ Поняття кримінально-процесуального доказування та його...
Судочинства суд, суддя, прокурор, слідчий, особа, яка провадить дізнання, зобов'язані встановити: чи був вчинений злочин, який саме,...
ЗАТВЕРДЖУЮ
Предмет і задачі курсу «Бюджетна система». Місце дисципліні в підготовці бакалаврів-фінансистів. Історія виникнення, значення бюджетної...
Програма курсу Професійна педагогіка наука і навчальний предмет
Профпедагогіка як галузь педагогічної науки, її методологія. Предмет профпедагогіки та предмет навчального курсу. Основні категорії...
Додайте кнопку на своєму сайті:
Портал навчання


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
Головна сторінка