TA,TB FA, FB TA,FB FA, TB

⇐ Предыдущая 123 4 5 Следующая ⇒

T`A F`A

FA TA

Риска у висновку правила означає розподіл аналітичної таблиці при його застосуванні на дві підтаблиці (на дві гілки), у кожній із них враховується якась одна із двох можливостей.

В усіх аналітичних правилах наведених вище, замість знаків А, В можна підставити будь-яку формулу логіки висловлювань.

Для того, щоб визначити чи є деяка формула А логічним законом відповідно до методу аналітичних таблиць, спочатку припускають, що ця формула є хибною, тобто ставлять перед нею індекс F. Для її побудови послідовно застосовують аналітичні правила для логічних сполучників.

Спочатку правила застосовуються для логічного сполучника, який є головним знаком формули, потім для логічних сполучників, які є головними знаками підформул. Наприкінці приходять до того, що індекси Т і F стоять перед пропозиційними змінними. Це свідчить про те, що побудова аналітичної таблиці закінчена.

Залежно від того, скільки гілок (підтаблиць) мала ця таблиця, виявляють одну чи декілька кінцевих таблиць.

Кінцева таблиця може бути замкненою або відкритою. Якщо вона замкнена, тоді до її складу повинна входити хоча б одна пропозиційна змінна з індексом Т і F, а якщо – відкрита, тоді до неї повинні входити пропозиційні змінні з якимось одним індексом Т і F.

Лише за умови того, що усі кінцеві таблиці певної формули А будуть замкнені, тоді формулу А можна вважати логічним законом. Побудуємо аналітичну таблицю для формули: (p É q) «(`q É`p).

Припускаємо, що дана формула є хибною і ставимо попереду неї індекс F.

F ( p É q) É (`q É`p).

Головним логічним сполучником цієї формули є імплікація «É», отже перше аналітичне правило, яке необхідно застосувати є F É FA É B

TA, FB

В результаті його застосування отримуємо 2 рядок аналітичної таблиці:

1. F ( p É q)É (`q É`p).

2. T (p É q), F (`q É`p)

Із застосуванням правила F É утворилося дві підформули:

T (p É q), F(`q É`p).

Тепер кожну підформулу розглядаємо окремо.

До першої підформули T (p É q) застосовуємо аналітичне правило,

T É TA É B, а до другої F(`q É`p) – аналітичне правило FÉ FA É B

FA TB TA, FB

І отримуємо 3 рядок аналітичної таблиці:

3. T (p É q), F (`q É`p)

F p T q, T` q, F` p

У 4 рядку застосовуємо два аналітичних правила T`A; F`A і отримуємо:

FA TA

4. Fp ½Tq, Fq, Tp

Аналітична таблиця для досліджуваної формули має такий вигляд:

1. F ( p É q)É (`q É`p).

2. T (p É q), F (`q É`p)

3. T (p É q), F (`q É`p)

Fp Tq, T`q, F`p

Fq, Tp

Ми прийшли до того, що індекси Т і F стоять перед пропозиційними змінними. Це свідчить про те, що побудова аналітичної таблиці закінчена.

Далі виписуємо кінцеві таблиці. Вертикальна риска у кінці аналітичної таблиці означає розподіл на дві підтаблиці (на дві гілки), у кожній із них враховується якась одна із двох можливостей. Якщо ж пропозиційні змінні з індексами стоять через кому, то вони будуть присутні у кожній кінцевій таблиці.

Отже, маємо такі кінцеві таблиці: 1. Fp, Fq, Tp

2. Tq, Fq, Tp.

До складу першої кінцевої таблиці пропозиційна змінна р входить із обома індексами Fp, Fq, Tp, до другої - пропозиційна змінна q також входить із обома індексами Tq, Fq, Tp, отже обидві кінцевітаблиці є замкненими, і це дозволяє нам стверджувати, що досліджувана формула виражає логічний закон.

Лекція№4. Рівносильні формули. Види логічних відношень

між формулами (2 год.)

Поняття про рівносильні формули. Властивості відношення рівносильності: рефлексивність, симетричність, транзитивність.

Основні закони логіки висловлювань. Закон подвійного заперечення. Закон комутативності. Закон асоціативності. Закон дистрибутивності. Закон імемпотентності. Закон виключення тавтології із кон'юнкції. Закон перетворення кон'юнкції в протиріччя. Закон перетворення диз'юнкції в тавтологію. Закон виключення протиріччя із диз'юнкції. Перший закон де Моргана. Другий закон де Моргана. Закон виразу кон'юнкції через диз'юнкцію. Закон виразу диз'юнкції через кон'юнкцію. Закон виключення імплікації. Закон заміни еквіваленції. Закон заміни сильної диз'юнкції. Закони виявлення. Закони поглинання.

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

Види логічних відношень між формулами у системі S¹. Відношення логічної сумісності. Відношення логічної сумісності за істинністю. Відношення логічної сумісності за хибністю.

Відношення логічного слідування. Відношення логічного слідування та правильність міркування. Алгоритм перевірки правильності міркування.

Семінарське заняття № 3 (2 год.)

1. Визначення рівносильної формули. Особливості відношення рівносильності.

2. Загальна характеристика основних законів логіки висловлювань.

3. Види логічних відношень між формулами. Відношення логічної сумісності за істинністю.

4. Відношення логічної сумісності за хибністю.

5. Відношення логічного слідування. Правильність міркування.

Контрольні запитання та вправи.

1. Що таке транзитивність?

2. Як можна визначити чи є сумісними за істинністю деякі формули?

3. Що таке відношення логічного слідування?

4. Як можна перевірити чи є конкретне міркування правильним?

5. Чи можуть бути дві довільні формули одночасно сумісні за істинністю і сумісні за хибністю?

6. Використовуючи таблиці істинності доведіть, що наведені формули є рівносильними.

(p Ù q) É r;

(p Ù`r) É`q;

(q Ù r) É`p.

7. За допомогою таблиць істинності знайдіть серед наведених формул рівносильні пари формул.

· p É (q É r); · (p É r) Ú (q É r);

· (p É q) Ù (p É r); · p É (q Ù r);

· (p Ù q) É r; · (q Ù r) É`p.

8. Доведіть такі рівносильності:

· (p Ù q) Ú (p Ù q) рівносильно (p Ù q);

· (p Ú q Ú r) Ù (p Ú q Ú r) рівносильно І (“істина”);

· p Ù p Ù p Ù q Ù q рівносильно (p Ù q);

· (p Ù q Ù r Ù s) рівносильно (`p Ú`q Ú`r Ú`s);

· (p Ú q Ú r) рівносильно (`p Ù`q Ù`r);

· (((p Ú`q) Ù r) Ú`p) рівносильно (((`p Ù q) Ú`r) Ù p).

9. За допомогою таблиць істинності обгрунтуйте такі рівносильності:

· А Ú (В Ù С) рівносильно (А Ú В) Ù (А Ú С) - дистрибутивність диз’юнкції відносно кон’юнкції;

· А Ù (В Ú С) рівносильно (А Ù В) Ú (А Ù С) – дистрибутивність кон’юнкції відносно диз’юнкції;

· А Ú (А Ù В) рівносильно А – закон поглинання;

· А Ù (А Ú В) рівносильно А – закон поглинання;

· (А Ú В) рівносильно ` А Ù`В – закон де Моргана;

· (А Ù В) рівносильно ` А Ú`В – закон де Моргана;

· А É В рівносильно ` А Ú В;

· (А É В) рівносильно А Ù`В;

· А É В рівносильно ` В É`А – закон контрапозиції;

· А É (В É С) рівносильно В É (А É С) – правило перестановки засновків.

10. Не складаючи таблиць істинності, встановіть відношення між чотирма кон’юнкціями:

· А Ù В; · `А Ù В;

· А Ù`В; ·`А Ù`В.

11. Визначте яким відношенням пов’язані між собою висловлювання:

· А É (А Ù`В Ù`С) і ` А Ú (`В Ù`С).

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

· А «В; · (А Ù В) Ú (`А Ù`В);

· А É В; · `В;

· `А Ù`В; · А Ù`В.

13. Серед наведених прикладів знайдіть пари сумісних за істинністю висловлювань:

· `А; · А Ù`В; · В É А;

· `В; ·А «В.

14. Визначте відношення між такими висловлюваннями:

· А Ú (`В Ù`С) і (А Ù В Ù С).

15. За допомогою таблиць істинності визначте чи існує відношення логічного слідування у наведених прикладах:

· (А É В) Ù В |= А; · (А Ú В) Ù (А É В) |= В;

· (`А É`С) Ù (`В Ú С) |= А É В; · (А Ú В Ú С) Ù (`А Ù`В) |= С;

· (А Ú В Ú С) Ù А |=`В Ù`С; · (А É В) Ù (С É`В) |=`С.

16. Побудуйте таблиці істинності наведених формул і розташуйте їх у такому порядку щоб із кожної попередньої формули слідували усі, які стоять після неї:

· `А «В; ·`А É В;

· А É (`А É В);

· А Ù`В; · А Ù (`В Ú А).

17. Встановіть в яких випадках із першої формули слідує друга:

· p Ù q, p; · p É q, q É p;

· p, p Ù q; · p É q, `p É`q;

· q, p Ú q; · (p É q) Ù p, q;

· p Ùq, p Ú q; · (p É q) Ù q, p.

· p Ù q, p É q;

18. Перевірте правильність таких виводів:

· А É В;`А É В · А É В;`А É С

В В É С

· А É В;`ВÉ`С · А É В; С É`В

С É А А É`С

· А É С; В É С

В É А.

19. Перевірте чи є сумісними за істинністю наведені висловлювання:

• Цей студент був на лекції, але не читав підручник.

• Цей студент був на лекції або не читав підручник.

• Невірно, що цей студент не був на лекції або читав підручник.

• Цей студент був на лекції і читав підручник або не був на лекції і не читав підручник.

• Якщо цей студент читав підручник, тоді він був на лекції.

• Тоді і тільки тоді цей студент читав підручник, коли він був на лекції.

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 1: с. 54-56, 58-59; 2: с. 95-97, 108-111; 4: с. 327-329; 6: с. 84-96; 23: с. 15-16, 26-32; 26: с. 79.-101;]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(6 год.)

Визначте яким відношенням пов’язані між собою висловлювання:

· А É (А Ù`В Ù`С) і ` А Ú (`В Ù`С).

Методичні вказівки

Засвоюючи цю тему студентам необхідно пам’ятати, що висловлювання вважаються рівносильними тільки у тому випадку, коли вони істинні і хибні при однакових наборах значень пропозиційних змінних, що входять до їх складу. Іншими словами, останні стовпчики таблиць істинності (які фіксують логічні значення усього висловлювання) таких висловлювань повинні співпадати.

Наприклад, перевіримо чи є рівносильними такі висловлювання:

p É q i ` p Ú q

Для цього побудуємо для них таблицю істинності.

№ p q `p p É q `p Ú q

1. і і х і і

2. і х х х х

3. х і і і і

4. х х і і і

Із цієї таблиці істинності очевидно, що логічні значення цих висловлювань повністю співпадають, отже висловлювання є рівносильними.

Якщо між рівносильними висловлюваннями поставити логічний сполучник “ « ” (еквіваленція), то створена формула виражатиме логічний закон. Щоб переконатися у цьому поєднаємо досліджувані висловлювання логічним сполучником «еквіваленція»:

(p É q)« (` p Ú q)

Перевіримо статус утвореної формули за допомогою таблиць істинності:

№ p q `p p É q `p Ú q (pÉ q)«(`p Ú q)

1. і і х і і і

2. і х х х х і

3. х і і і і і

4. х х і і і і

У останньому стовпчику таблиці істинності формула набуває лише логічного значення “ істина ”, отже, вона виражає логічний закон.

Рівносильність двох формул логіки висловлювань позначають символом “º”. Вираз “А º В ” читається так: “формула А рівносильна формулі В”.

Відношення рівносильності має такі особливості:

1) рефлексивністьА º А (будь-яка формула є рівносильною стосовно самої себе);

2) симетричність: якщо А º В, то В º А (якщо перша формула є рівносильною другій, то друга формула буде рівносильна першій);

3) транзитивність: якщо А º В і В º С, то А º С (якщо перша формула є рівносильною другій, а друга – третій, то перша формула буде рівносильною третій).

Усі рівносильності логіки висловлювань є її законами. У цьому можна легко переконатися за допомогою таблиць істинності. Але, іноді, побудова таблиць істинності є досить громіздкою справою для визначення завжди істинних формул. І тому, розв’язання цієї задачі відбувається шляхом еквівалентних перетворень вихідних формул за допомогою законів логіки висловлювань. Розглянемо ці закони:

· ` А º А - закон подвійного заперечення;

· А Ù В º В Ù А - закон комутативності для кон’юнкції;

· А Ú В º В Ú А - закон комутативності для диз’юнкції;

· (А Ù В) Ù С º А Ù (В Ù С) - закон асоціативності для кон’юнкції;

· (А Ú В) ÚС º А Ú (В Ú С) - закон асоціативності для диз’юнкції;

· А Ù (В Ú С) º (А Ù В) Ú (А Ù С) – закон дистрибутивності кон’юнкції відносно диз’юнкції;

· А Ú (В Ù С) º (А Ú В) Ù (А ÚС) – закон дистрибутивності диз’юнкції відносно кон’юнкції;

· А Ù А º А - закон ідемпотентності для кон’юнкції;

· А Ú А º А - закон ідемпотентності для диз’юнкції;

· А Ù⊤ º А - закон виключення тавтології (⊤) із кон’юнкції;

· А Ù ⊥ º ⊥ - закон перетворення кон’юнкції у протиріччя (⊥ - завжди хибна формула);

· А Ú⊤ º ⊤ - закон перетворення диз’юнкції у тавтологію;

· А Ú⊥º А - закон виключення протиріччя із диз’юнкції;

· А Ù В º`А Ú`В - перший закон де Моргана;

· А Ú В º`А Ù`В - другий закон де Моргана;

· А Ù В º (`А Ú`В) - закон вираження кон’юнкції через диз’юнкцію;

· А Ú В º (`А Ù`В) - закон вираження диз’юнкції через кон’юнкцію;

· А É В º`А Ú В - закон виключення імплікації;

· А «В º (А É В) Ù (В É А) – закон заміни еквіваленції;

· А Ú В º (А Ú В) Ù (`А Ú`В) - закон заміни сильної диз’юнкції;

· ` А Ù (В Ú А) º`А Ù (В Ú А) Ù В

· ` А Ú (В Ù А) º`А Ú (В Ù А) Ú В закони

· (А Ú В) Ù (`А Ú С) º (А Ú В) Ù (`А Ú С) Ù (В Ú С) виявлення;

· (А Ù В) Ú (`А Ù С) º (А Ù В) Ú (`А Ù С) Ú (В Ù С)

·

· (А Ú В) Ù (`А Ú В) º В закони

· (А Ú В) Ù А º А поглинання.

· (А Ù В) Ú А º А

За допомогою цих законів (рівносильностей) можна одні формули перетворювати на інші. Такі перетворення здійснюються з метою спрощення формул. Наприклад, візьмемо формулу

(А Ú В) É С

Відповідно до другого закону де Моргана (А Ú В º`А Ù`В) замінимо у досліджуваній формулі антецедент імплікації і отримаємо

(`А Ù`В) É С

Ця формула є рівносильною вихідній. Тепер застосуємо закон виключення імплікації (А É В º`А Ú В) і замінимо цю формулу на рівносильну їй:

(`А Ù`В) Ú С

Відповідно до першого закону де Моргана (А Ù В º`А Ú`В) здійснимо заміну підформули (`А Ù`В) на рівносильну їй:

` А Ú`В Ú С

Застосувавши закон подвідного заперечення (`А º А) отримаємо спрощену формулу, яка є рівносильною всім попереднім формулам:

А Ú В Ú С.

Студенту необхідно знати, що поряд із виділенням логічних законів у системі S¹ розв’язується ще одна задача, яка встановлює логічні відношення між формулами. Зокрема, такі:

- відношення логічної сумісності за істинністю;

- відношення логічної сумісності за хибністю;

- відношення логічного слідування.

Відношення логічної сумісності між декількома формулами визначається за допомогою методу таблиць істинності. Для цього необхідно побудувати спільну таблицю істинності для цих формул.

Якщо у побудованій таблиці істинності знайдеться хоча б один рядок, де кожна із досліджуваних формуло дночасно набуває логічного значення “істина”, тоді такі формули сумісні за істинністю.

Якщо рядок, де формули є одночасно істинними відсутній, тоді формули є несумісними за істинністю. Переконаємося у цьому на прикладі.

Візьмемо формули: p Ú q; q É r; p Ú r

№ p q r p Ú q q É r p Ú r

1. і і і і і і

2. і і х і х і

3. і х і і і і

4. і х х і і і

5. х і і і і і

6. х і х і х х

7. х х і х і і

8. х х х х і х

Із цієї таблиці істинності очевидно, що досліджувані формули є сумісними за істинністю, оскільки у 1, 3, 4, 5 рядках усі формули набувають логічного значення “ істина ”.

Якщо ж у побудованій таблиці істинності для декількох формул знайдеться хоча б один рядок, де кожна із досліджуваних формул набуває логічного значення “хиба”, тоді такі формули сумісні за хибністю.

Якщо рядок, де формули є одночасно хибними відсутній, тоді вони є несумісними за хибністю.

Розглянемо приклад. Візьмо формули p Ú q; q Ù`r; `p Ù q.

Побудуємо для них спільну таблицю істинності.

№ p q r `p `r p Ú q q Ù`r ` p Ù q

1. і і і х х і х х

2. і і х х і і і х

3. і х і х х і х х

4. і х х х і і х х

5. х і і і х і х і

6. х і х і і і і і

7. х х і і х х х х

8. х х х і і х х х

У останньому 7 і 8 рядку таблиці істинності усі формули набувають логічного значення “ хиба ”, а отже вони є сумісними за хибністю.

І нарешті, відношення логічного слідування визначається так : логічне слідування – це відношення, яке існує між засновками і висновком міркування.

Якщо засновки міркування представити у вигляді формули А, а його висновок - у вигляді формули В, тоді можна стверджувати, що із формули А логічно випливає формула В, коли імплікація А É В є законом логіки.

Для позначення логічного слідування у логіці застосовують знак “ |= ”. Вираз “ А |= В ” читається так: “із А логічно слідує В ”.

На підставі встановлення відношення логічного слідування між засновками і висновком міркування стає можливим встановити його правильність чи неправильність.

Міркування буде правильним, якщо із кон’юнкції його засновків логічно випливає висновок. Тобто, якщо між засновками міркування і його висновком встановлено відношення логічного слідування, то таке міркування буде правильним. Інакше, його необхідно оцінити як неправильне.

Щоб встановити правильність міркування необхідно виконати такі дії:

1) формалізувати всі засновки міркування і його висновок;

2) поєднати засновки міркування за допомогою логічного сполучника “Ù” (кон¢юнкція), а висновок приєднати за допомогою - “É” (імплікації).

3) створену формулу перевірити за допомогою таблиць істинності, чи логічно слідує ізкон’юнкції засновків міркування висловлювання, яке відповідає висновку міркування.

Якщо у останньому стовпчику таблиці істинності утворена формула набуває логічного значення “ істина ”, тобто виражає логічний закон, тоді можна стверджувати, що із кон’юнкції засновків міркування логічно слідує його висновок, отже, міркування оцінюється як правильне. Якщо ж – ні, тоді – як неправильне.

Наприклад. Перевіримо чи є дане міркування правильним, тобто з’ясуємо чи логічно слідує висновок міркування із його засновків.

“Якщо предмет є цікавим, тоді він - корисний. Предмет є цікавим. Отже, він є корисним”.

Формалізуємо це міркування.

Перший засновок - “ Якщо предмет є цікавим, тоді він - корисний” відповідає такій формулі - p É q,

Другий засновок – “ Предмет є цікавим” відповідає формулі – p.

Висновок - “ Отже, він є корисним ” відповідає формулі - q.

Тепер створимо формулу цього міркування, тобто поєднаємо засновки міркування через “ Ù ” (кон’юнкцію) і приєднаємо до утвореного виразу висновок міркування через “É” імплікацію.

((p É q) Ù p) É q.

Скористаємося таблицею істинності для перевірки правильності цього міркування.

№ p q p É q (p É q) Ù p ((p É q) Ù p) É q

1. і і і і і

2. і х х х і

3. х і і х і

4. х х і х і

Останній стовпчик таблиці істинності має лише логічні значення «істина», отже, досліджувана формула є логічним законом, а це свідчить про те, що між засновками і висновком даного міркування існує відношення логічного слідування, тобто воно є правильним.

Розглянемо інший приклад.

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

А É С; В É С

В É А.

Насамперед, поєднаємо засновки цього виводу за допомогою логічного сполучника «кон’юнкція»,

(А É С) Ù (В É С),

а його висновок приєднаємо до утвореного виразу за допомогою логічного сполучника «імплікація» і отримаємо вираз:

((А É С) Ù (В É С)) É (В É А)

Тепер, знову звернемося до таблиці істинності.

№ А В С А É С В É С В É А (А É С) Ù (В É С) ((А É С)Ù(В É С))É (В É А)

1. і і і і і і і і

2. і і х х х і х і

3. і х і і і і і і

4. і х х х і і х і

5. х і і і і х і х

6. х і х і х х х і

7. х х і і і і і і

8. х х х і і і і і

Отже, у таблиці істинності для цього виводу є один рядок (5) у якому формула набуває логічного значення “ хиба ”, а це означає, що між засновками і висновком досліджуваного виводу не існує відношення логічного слідування. Тому він оцінюється як неправильний.

Лекція №5. Нормальні форми логіки висловлювань (2 год.).

Поняття "Проблема розв'язання" у логіці. Кон'юнктивна нормальна форма. Досконала кон'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує. Скорочена кон'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує.

Диз'юнктивна нормальна форма. Досконала диз'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує. Скорочена диз'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує.

Семінарське заняття № 4-5 (4 год.)

1. Кон'юнктивна нормальна форма. Процедура зведення конкретної формули до КНФ.

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

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

4. Диз'юнктивна нормальна форма. Процедура зведення конкретної формули до ДНФ.

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

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

Контрольні запитання та вправи.

1. Що означає поняття "проблема розв'язання" у алгебраїчній системі логіки висловлювань?

2. Що таке кон'юнктивна нормальна форма?

3. Які задачі вирішуються за допомогою КНФ?

4. Які ознаки має досконала кон'юнктивна нормальна форма?

5. Який алгоритм зведення конкретної формули до ДКНФ?

6. Які ознаки має скорочена кон'юнктивна нормальна форма?

7. Який алгоритм зведення конкретної формули до СКНФ?

8. Що таке диз'юнктивна нормальна форма?

9. Які задачі вирішуються за допомогою ДНФ?

10. Які ознаки має досконала диз'юнктивна нормальна форма?

11. Який алгоритм зведення конкретної формули до ДДНФ?

12. Які ознаки має скорочена диз'юнктивна нормальна форма?

13. Який алгоритм зведення конкретної формули до СДНФ?

14. Приведіть до КНФ такі формули і перевірте чи є вони тотожно-істинними чи ні:

· (А É В) Ú (`А Ù С); · (А É В) É (`А Ú В);

· (А É (В Ù`А)); · ((А Ù В) É С) É ((А Ù`С) É`В));

· ((А É`В) Ù С) Ú (`А É С); · (А É В) Ú ((`А Ù С) É В);

· (А Ú В Ú`А); · ((A É B) Ù (B É C) Ù (A Ú`B)) É C;

· (А Ù С) É (А Ú С);

· (А É В) É (`В É`А); · ((A É B) É ((A Ù C) Ú`B));

· (С Ù D) É (В Ù С); · (`A Ú ((B É B) É A));

· (С Ù В) É (`A Ú D);

· ((`A Ù B) Ú (C Ù A) Ú (`C Ù B) Ú (A Ù B Ù C)).

15. Приведіть до ДКНФ такі формули:

· А «(В Ù`А); · A Ú (B Ù`B);

· (А É В) Ú (`А Ù С); · (A Ù B) Ú (`A Ù`B);

· B Ù (`C Ú D); · (A Ù B Ù C) Ú (`A Ù`B ÙC);

· C É (D Ú B); · (A Ù (`A Ú`B));

· D É (A É B); · (A Ù B Ù`C) Ú (`A Ù`B);

· C «(A É D); · (A «B) Ù (A Ù C).

16. Знайдіть всі логічні наслідки із даних формул:

· А É В, `А É С, В É С; · (А «В), (В «С);

· А É (В É С), А É В; · ((А Ù В) É`С), В, С;

· А É В, `В; · А, (А Ú В) Ú (В É`А), С;

· А É В, В Ú С, ((А Ù В) «С); · А É (В É С), А É А, В.

17. Приведіть формулу до СКНФ:

· А, (А Ù В) É (А Ú С);

· `А É С, `С É В, (`А É`С);

· (А Ú В) É С, (С Ù В) «D.

18. Приведіть до ДНФ такі формули:

(А É В) Ú (`А Ù С); · (`В É`А) Ù (А É В);

· ((А É В) Ù (А É С)) É (А É (В Ù С));

· А Ù (`А Ú`В); · (А Ù (А É В));

· `С Ù (С Ù С); · ((А Ú В) É (А Ù В));

· В É (В Ú С); · ((А Ú`В Ú С) É (А Ù В Ù`С));

· (((А É В) É (В É С)) Ù (`С Ú А).

19. Формула приведена до ДНФ. Отримайте для неї КНФ:

· (А Ù В Ù С) Ú (`А Ù`В) Ú (В Ù С);

· (`А Ù В Ù С) Ú (А Ù`В Ù С) Ú (А Ù`С).

20. Приведіть до ДНФ і КНФ такі формули:

· (А É В) Ù (А É С);

· ((А É`В) É (А É С)) É (А É В);

· ((((А É В) É`А) É`В) É`С) É С;

· ((`А É В) Ù С) Ú (`А «С);

· (А É (В É С)) É ((А É`С) É (А É`В));

· ((А É В) É (С É`А)) É ((`В É`С).

21. Приведіть до ДДНФ такі формули:

А «(В Ù`А); · ((`А Ú`В) Ú (А Ù`В));

· (А É В) Ú (`А Ù С); · (А Ù В Ù С) Ú (А Ù`В);

· В Ù (`С Ú D); · А Ù (`В Ú С);

· С É (D Ú B); · (А Ú В Ú С) Ù (`А Ú В Ú`С);

· D É (A É B); · (А É С) Ù А Ù В;

· C «(A É D);

· (А É В) É (В Ù (С É`А)); · (((А Ú В) Ù С) Ú (С É В));

· (А Ú В) Ù (А Ú`В); · (((А Ù В) Ú (`В ÙС)) Ù`В).

22. Знайдіть усі гіпотези для таких формул:

· ((А É В) É С) É ((С É В) É А);

· (А Ú (В Ù С)) É (`В Ú (В Ù`А Ù С)).

23. Привести до ДКНФ і ДДНФ такі формули:

(А É В) Ú (`А ÙС); · (С É А) É ((В Ú С) É А);

· (А É`В) É (С É В);

· (А É`С) É (`А É В); · ((А Ú С)) Ù (А É В).

24. Знайдіть усі прості гіпотези із таких формул:

(((А Ù В) Ú (C Ù D)) É (A Ù`B Ù C));

· ((A Ù B) Ú ((A É C) É`B)).

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 1: с. 54-56, 58-59; 2: с. 95-97, 108-111; 4: с. 329 - 340; 23: с. 35-42.; 26: с.177 - 193; 29: с. 41-56.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(6 год.)

Приведіть до ДКНФ і ДДНФ такі формули:

(А É В) Ú (`А Ù С); (С É А) É ((В Ú С) É А);

Методичні вказівки

Вивчаючи цю тему студентам необхідно засвоїти, що у сучасній логіці існує таке поняття як “проблема розв’язання”.

В алгебраїчній системі логіки висловлювань воно визначається так: “ Проблема розв’язання – це встановлення ефективної процедури, яка кінцевим числом кроків, дозволяє встановити чи є певна формула тотожно-істинною, або тотожно-хибною, або ж виконуваною ”.

У S¹ такими процедурами є:

1) побудова таблиць істинності;

2) зведення формули до КНФ і ДНФ.

Кон’юнктивна нормальна форма це кон’юнкція елементарних диз’юнкцій.

Наприклад, (А Ú В) Ù (`А Ú С), (А Ú В) Ù С тощо.

Для того щоб привести певну формулу до КНФ необхідно виконати такі дії:

1) За допомогою відповідних законів потрібно звільнитися від сильної диз’юнкції “Ú”, еквіваленції “«” та імплікації “É”, якщо вони наявні у вихідній формулі;

2) Звільнитися від загального заперечення та подвійного заперечення відповідно до конкретних законів;

3) До отриманої формули застосувати закон дистрибутивності диз’юнкції по відношенню до кон’юнкції.

За допомогою КНФ розв’язують такі задачі:

· визначення чи є дана формула тотожно-істинною чи ні; та

· встановлення чи є формула С наслідком із формул А₁, А₂, … А_n.

Вихідна формула вважається тотожно-істинною або тавтологією, якщо кожна елементарна диз’юнкція, що входить до КНФ має у своєму складі одначасно пропозиційну змінну і її заперечення.

Наприклад,

визначимо чи є формула (`В Ù (А É В)) É`А тотожно-істинною, тобто приведемо її до КНФ.

Спочатку за допомогою закону «виключення імплікації» (А É В º`А Ú В) звільняємося від логічного сполучника «імплікація», який є головним знаком формули:

(`В Ù (А É В)) Ú`А;

Далі, за тим самим законом, «виключення імплікації» звільняємося від імплікації, що знаходиться у дужках:

(`В Ù (`А Ú В)) Ú`А;

Наступним нашим кроком буде застосування «першого закону де Моргана»

(А Ù В º`А Ú`В) для того, щоб позбутися загального заперечення:

(`В Ú (`А Ú В)) Ú`А;

Використовуючи «другий закон де Моргана» (А Ú В º`А Ù`В) позбуваємося від заперечення підпормули (`А Ú В):

(`В Ú (`А Ù`В)) Ú`А;

Застосовуючи «закон подвійного заперечення» (` А º А) звільняємося від подвійних заперечень, які знаходяться над змінними і отримуємо формулу:

(В Ú (А Ù`В)) Ú`А;

І, нарешті, до отриманої формули застосовуємо «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції»: А Ú (В Ù С) º (А Ú В) Ù (А Ú С):

((В Ú А) Ù (В Ú`В)) Ú`А;

Використовуємо цей самий закон ще раз і отримуємо таку формулу:

(В Ú А Ú`А) Ù (В Ú`В Ú`А).

Отже, кожна елементарна диз’юнкція має у своєму складі змінну одночасно із її запереченням (А Ú`А) і (В Ú`В), а це означає, що вихідна формула є тотожно-істинною або тавтологією.

Що стосовно другої зачачі, яку розв’язує КНФ то, щоб перевірити чи є формула С наслідком із формул А₁, А₂, … А_n необхідно за допомогою кон’юнкції поєднати формули А₁, А₂, … А_n., а потім приєднати до них за допомогою імплікації формулу С, і отриманий вираз привести до КНФ.

Якщо отримана КНФ буде тотожно-істинною формулою (тавтологією), тоді можна стверджувати, що формула С наслідком із формул А₁, А₂, … А_n.

Переконаємося у цьому на прикладі.

Визначимо чи є формула С наслідком із формул А Ú В, А É С, В É С.

Для цього спочатку поєднаємо дані формули за допомогою логічного сполучника «кон’юнкція»:

(А Ú В) Ù (А É С) Ù (В É С);

Потім за допомогою логічного сполучника «імплікація» приєднаємо до отриманого виразу наслідок С:

((А Ú В) Ù (А É С) Ù (В É С)) É С;

Приведемо отриманий вираз до КНФ:

((А Ú В) Ù (А É С) Ù (В É С)) Ú С

((А Ú В) Ù (`А Ú С) Ù (`В Ú С)) Ú С

((А Ú В) Ú (`А Ú С) Ú (`В Ú С)) Ú С

((`А Ù`В) Ú (`А Ù`С) Ú (`В Ú`С)) Ú С

1 2 3

((`А Ù`В) Ú (А Ù`С) Ú (В Ù`С)) Ú С

Наступним нашим кроком буде застосовання «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції» А Ú (В Ù С) º (А Ú В) Ù (А Ú С):

(((`А Ú А) Ù (`А Ú`С) Ù (`В Ú А) Ù (`В Ú`С)) Ú (В Ù`С)) Ú С

Потім знову використовуємо «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції» А Ú (В Ù С) º (А Ú В) Ù (А Ú С) і отримуємо:

((`А Ú АÚ В) Ù (`А Ú АÚ`С) Ù (`А Ú`С Ú В) Ù (`А Ú`С Ú`С) Ù

Ù (`В Ú А Ú В) Ù (`В Ú А Ú`С) Ù (`В Ú`С Ú В) Ù (`В Ú`С Ú`С)) Ú С;

І ще раз застосовуємо цей самий закон і отримуємо КНФ:

(`А Ú АÚ ВÚ С) Ù (`А Ú АÚ`С Ú С) Ù (`А Ú`С Ú ВÚ С) Ù

Ù (`А Ú`С Ú`СÚ С) Ù (`В Ú А Ú ВÚ С) Ù (`В Ú А Ú`СÚ С) Ù

Ù (`В Ú`С Ú ВÚ С) Ù (`В Ú`С Ú`СÚ С).

Кожна елементарна диз’юнкція, що входить до складу отриманої КНФ має змінну одночасно із її запереченням, а це означає, що вихідна формула є тотожно-істинною тому, можна стверджувати, що формула С є наслідком із формул А Ú В, А É С, В É С.

Досконалою кон'юнктивною нормальною формою (ДКНФ) деякої формули називається така її КНФ, яка задовольняє таким умовам:

1) у ній немає двох однакових кон'юнктів;

2) жоден кон'юнкт немає двох однакових диз’юнктів (А Ú В Ú А);

3) жоден кон'юнкт немає змінної і її заперечення (А Ú В Ú`А);

4) у кожному кон'юнкті наявні всі змінні, що входять до складу вихідної формули.

Щоб привести формулу до ДКНФ неохідно виконати такі дії:

а) звести вихідну формулу до КНФ;

б) співставити отриману КНФ із перерахованими ознаками ДКНФ;

в) якщо в якомусь із кон'юнктів відсутняпропозиційна змінна, яка наявна у вихідній формулі, то необхідно за допомогою диз'юнкції приєднати до цього кон'юнкта протиріччя цієї змінної (Х Ù`Х), а потім застосувати закон дистрибутивності диз'юнкції по відношенню до кон'юнкції.

За допомогою ДКНФ розв'язують задачу знаходження всіх логічних наслідків із даних формул.

Розглянемо приклади.

Візьмемо формули ` В і А É В ізнайдемо з них всі логічні наслідки.

Для цього спочатку за допомогою кон'юнкції поєднуємо ці формули:

` B Ù (A É B)

Далі, отримуємо з неї КНФ:

` B Ù (`A Ú B)

Отримали КНФ. Тепер співставимо отриманий вираз із ознаками ДКНФ.

Виявляється, що в першому кон'юнкті відсутня пропозиційна змінна А, яка є у вихідній формулі. Тому, нам необхідно приєднати за допомогою диз'юнкції до першого кон'юнкта протиріччя (А Ù`А):

(`B Ú (A Ù`A)) Ù (`A Ú B)

Знову застосовуємо «закон дистрибутивності диз'юнкції по відношенню до кон'юнкції» і отримуємо вираз:

(`B Ú A) Ù (`B Ú`A) Ù (`A Ú B)

Отже, ми отримали ДКНФ, яка дає можливість оглянути всі логічні наслідки із даних формул.

Цими наслідками є:

1. (`В Ú А);

2. (`В Ú`А);

3. (`А Ú В);

4. (`В Ú А) Ù (`B Ú`A);

5. (`B Ú A) Ù (`A Ú B);

6. (`B Ú`A) Ù (`A Ú B);

7. (`B Ú A) Ù (`B Ú`A) Ù (`A Ú B).

Знайдемо всі наслідки із таких формул: В Ú С, В É`А, В É С.

Поєднаємо ці формули за допомогою кон’юнкції:

(B Ú C) Ù (B É`A) Ù (B É C)

Приведемо триманий вираз до КНФ:

(B Ú C) Ù (`B Ú`A) Ù (`B Ú C)

Співставимо отриману КНФ із ознаками ДКНФ, очевидно, що у першому кон’юнкті не вистачає про змінної А, яка наявна у вихідній формулі; у другому – про змінної С; у третьому – про змінної А.

Отже, необхідно приєднати за допомогою диз'юнкції до першого кон'юнкта протиріччя (А Ù`А), до другого – (С Ù`С), до третього – (А Ù`А):

[(B Ú C) Ú (A Ù`A)] Ù [(`B Ú`A) Ú (C Ù`C)] Ù [(`B Ú C) Ú (`A Ù A)]

Застосуємо закон «дистрибутивності диз'юнкції по відношенню до кон'юнкції»:

4. (B Ú C Ú A) Ù (B Ú C Ú`A) Ù (`B Ú`A Ú C) Ù (`B Ú`A Ú`C) Ù

Ù (`B Ú C Ú A) Ù (`B Ú C Ú`A).

Отримана ДКНФ представляє всі можливі наслідки із даних формул. Які групуються так: спочатку по одному наслідку, потім по два, по три, по чотири, по п’ять, і нарешті вся отримана ДКНФ.

Скороченою кон'юнктивною нормальною формою(СКНФ) даної формули називається така її КНФ, яка задовольняє таким умовам:

1) Жоден кон'юнкт не має двох однакових диз’юнктів (А Ú В Ú А);

2) У ній відсутні два однакових кон'юнкти;

3) У ній відсутні кон'юнкти до складу яких входить змінна і її заперечення.

Щоб привести формулу до СКНФ необхідно виконати такі дії:

1) отримати із вихідної формули КНФ;

2) співставити отриману КНФ із ознаками СКНФ;

3) до отриманого виразу послідовно застосовувати «закони виявлення» і «закони поглинання».

Завдяки СКНФ розв'язують задачузнаходження всіх простих наслідків із кон'юнкції заданих формул.

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

А É`В, А Ú С, B Ù C

Для цього, спочатку поєднаємо наведені формули за допомогою кон’юнкції і отримаємо вираз:

(A É`B) Ù (A Ú C) Ù (B Ù C)

Отриманий вираз приведемо до КНФ:

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C)

Отриману КНФ співставляємо із ознаками СКНФ.

Потім до отриманої КНФ послідовно застосуємо спочатку «закон виявлення»

(А Ú В) Ù (`А Ú С) º (А Ú В) Ù (`А Ú С) Ù (В Ú С):

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C) Ù (`В Ú С) Ù (А Ú`В)

А потім «закон поглинання»(А Ú В) Ù (`А Ú В) º В:

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C) Ù (`В Ú С) Ù (А Ú`В)

1 2 3 4 5

У результаті застосування «закону поглинання» ми скоротили 1 і 5 підформули і отримали ` В, 3 і 4 підформули і також отримали ` В. Підформула (А Ú С) залишилася непоглинутою.

Отже, врешті решт, ми отримали таку СКНФ(А Ú С) Ù`В, де кожен із кон’юнктів є простим наслідком:

1. (А Ú С);

2. `В;

3. (А Ú С) Ù`В.

Диз'юнктивною нормальною формою (ДНФ) даної формули називається диз'юнкція елементарних кон'юнкцій: (A Ù B) Ú (`B Ù C) Ú A тощо.

Щоб привести формулу до ДНФ необхідно виконати такі дії:

1) за допомогою відповідних законів послідовно звільнитися від сильної диз’юнкції “Ú”, еквіваленції “«”, імплікації “É”, якщо вони є у вихідній формулі;

2) за допомогою законів де Моргана позбавитися загального заперечення;

3) до отриманої формули застосувати «закон дистрибутивності кон'юнкції по відношенню до диз'юнкції».

ДНФ дозволяє встановити чи є довільна формула тотожно-хибною чи ні.

Наприклад, приведемо до ДНФ таку формулу:

[ (A É B) Ù (C É D) Ù (A Ú C) ] É (B Ú D)

Спочатку звільнимося від імплікації за вже відомим нам «законом виключення імплікації»А É В º`А Ú В:

[ (A É B) Ù (C É D) Ù (A Ú C) ] Ú (B Ú D)

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

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ú (B Ú D)

Наступним кроком буде звільнення від загального заперечення за «другим законом де Моргана»А Ú В º`А Ù`В:

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù (B Ú D)

За «законом подвійного заперечення»`А º А, позбавимося загального заперечення:

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù (B Ú D)

Знову ж таки за «другим законом де Моргана» звільнимося від загального заперечення підформули:

1 2 3

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù`B Ù`D

Для підформул 1 і 2 у квадратних дужках застосовуємо «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»

А Ù (В Ú С) º (А Ù В) Ú (А Ù С):

3

[ ((`А Ù`С) Ú (`А Ù D) Ú (B Ù`C) Ú (B Ù D)) Ù (A Ú C) ] Ù`B Ù`D

Далі до отриманого результату і формули 3 також застосовуємо цей самий закон:

[(`A Ù`C Ù A) Ú (`A Ù D Ù A) Ú (B Ù`C Ù A) Ú (B Ù D Ù A) Ú

Ú (`A Ù`C Ù C) Ú (`A Ù D Ù C) Ú (B Ù`C Ù C) Ú (B Ù D Ù C)] Ù`B Ù`D

І, нарешті, до отриманого результату у квадратних дужках і підформули ` В Ù`D застосовуємо «закон комутативност» і отримуємо:

(`A Ù`C Ù A Ù`B Ù`D) Ú (`A Ù D Ù A Ù`B Ù`D) Ú

(B Ù`C Ù A Ù`B Ù`D) Ú (B Ù D Ù A Ù`B Ù`D) Ú

Ú (`A Ù`C Ù C Ù`B Ù`D) Ú (`A Ù D Ù C Ù`B Ù`D) Ú

Ú (B Ù`C Ù C Ù`B Ù`D) Ú (B Ù D Ù C Ù`B Ù`D)

Отже, ми отримали ДНФ у якій кожен диз'юнкт у своєму складі має змінну одночасно із її запереченням, а це означає, що дана формула є тотожно-хибною.

Досконалою диз'юнктивною нормальною формою (ДДНФ ) деякої формули називається її ДНФ, яка задовольняє такі умови:

1) у ній немає двох однакових диз'юнктів;

2) у жодному диз'юнкті не має змінної і її заперечення;

3) жоден диз'юнкт не має двох однакових змінних;

4) кожен диз'юнкт містить всі змінні, що наявні у вихідній формулі.

Щоб привести формулу до ДДНФ необхідно виконати такі дії:

⇐ Предыдущая 123 4 5 Следующая ⇒

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных