Курсова робота

Методи перевірки тотожності формул числення висловлювань

Зміст

1. Анотація…………………………………………..1 стр.

2. Вступ………………………………………………2 стр.

3. Теоретична частина:

3.1 Алгебраїчний метод……………………………..3 стр.

3.2 Метод Куайна…………………………………….3 стр.

3.3 Метод редукції……………………………………3 стр.

3.4 Метод Девіса-Патнема…………………………..4 стр.

3.5 Метод резолюцій…………………………………6 стр.

4. Практична частина:

4.1 Додаток 1………………………………………..7 стр.

4.2 Додаток 2………………………………………..8 стр.

4.3 Додаток 3………………………………………..9 стр.

4.4 Висновок……………………………………….10 стр.

4.5 Рекомендована література……………………11 стр.

Анотація.

Головними ідеями дискретної математики є :

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

По-друге – ідея алгоритму очевидності, суть якої полягає у створенні
спеціалізованої програми для автоматизованої обробки математичних
текстів.

По-третє – ідея рекурсивної обчислювальної машини нової формації з
необмеженим нарощуванням пам’яті та швидкодії.

По-четверте – ідея створення штучного інтелекту як окремої системи, що
визначається своїм розумом, який розміщується в базах знань, і системою
перетворень, які динамічно самоорганізуються.

Вступ.

Нехай Al={A, B, C, …, X, Y, A1, …} – алфавіт змінних (скінчений або
зліченний). Кожна із змінних цього алфавіту може приймати одне із двох
значень ТАК (істина — 1) або НІ (хибність — 0), а самі змінні у цьому
випадку називають висловлюваннями. Інакше кажучи, висловлювання – це або
хибне, або істинне висловлювання, але не те і друге разом.

Елементи алфавіту Al, які використовуються для висловлювань, будемо
називати пропозиційними змінними, або атомарними формулами, або просто
атомами.

Із висловлювань можна будувати складені висловлювання, використовуючи
атомарні формули.

Формула А числення висловлювань називається тавтологією (суперечністю),
якщо вона приймає значення 1 (0) незалежно від інтерпретації.

Щоб перевірити формулу числення висловлень на тотожність, тобто чи є
вона тавтологією, чи суперечністю, потрібно знайти її значення при всіх
можливих інтерпретаціях. Будемо називати цей метод тривіальним. Хоча він
досить простий, але його недолік – громіздкість. Існують і більш
досконалі методи. Розглянемо деякі з них.

Алгебраїчний метод.

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

Метод Куайна.

Метод Куайна являє собою безпосереднє узагальнення тривіального
алгоритму.

Нехай {p, q, …, r} – упорядкована множина висловлювань, які
зустрічаються у формулі Р(p, q, …, r). Візьмемо перше з висловлювань – p
і припишемо йому, наприклад, значення 1 (0). Підставимо це значення у
формулу Р і виконаємо обчислення, які можуть виявитися необхідними
внаслідок такої підстановки. Після виконання обчислень одержуємо деяку
формулу P’{p, q, …, r}, до якої застосовується описана процедура, тобто
вибираємо формулу q, приписуємо їй значення 1 (0), виконуємо обчислення
і т.д. Може трапитися так, що на деякому кроці буде одержана формула P”,
яка є тавтологією або суперечністю незалежно від значень висловлювань,
які входять до складу формули P”. Отже, на цьому кроці роботу алгоритму
можна зупинити. Таким чином, метод Куайна в деяких випадках приводить до
розгляду значно меншої кількості інтерпретацій, ніж тривіальний
алгоритм.

Метод редукції.

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

Нехай формула P має вигляд імплікацій, наприклад P = Q ? R. Припустимо,
що в деякій інтерпретації h формула P приймає значення 0. Тоді
відповідно з таблицею істинності для імплікації маємо h(Q) = 1 і h(R)
= 0. Таким чином, перевірка формули P зводиться до перевірки формул Q і
R. Після цього даний процес застосовується до формул Q і R

і т.д.

Метод Девіса-Патнема.

Перш ніж перейти до дослідження методу Девіса-Патнема введемо деякі
означення.

Літерою називається атом або позначення атома. Диз’юнктом називається
диз’юнкція літер. Одиничним диз’юнктом називається одно літерний
диз’юнкт. Якщо диз’юнкт не має жодної літери, то він називається пустим
диз’юнктом і позначається 0. Літери L і ?L називаються контрарними.

Нехай S – множина диз’юнктів. Суть методу Девіса-Патнема полягає в
застосуванні таких чотирьох правил.

Правило тавтології. Викреслити всі тавтологічні диз’юнкти із S. Множина
диз’юнктів S’, що залишилась, суперечна тоді і тільки тоді, коли і S
суперечна.

Правило однолітерних диз’юнктів. Якщо існує однолітерний диз’юнкт L в S,
то S’ одержано з S шляхом викреслення з S диз’юнктів, які містять L.
Якщо S’ пустий, то S – істина. В протилежному випадку будуємо множину S”
шляхом вилучення з S’ усіх входжень ?L. S” суперечна тоді і тільки тоді,
коли і S суперечна. Зауважимо, що, коли ?L – одиночний диз’юнкт, то при
викресленні ?L він перетворюється в пустий диз’юнкт.

Правило чистих літер. Літера L деякого диз’юнкта S називається чистою в
S тоді і тільки тоді, коли літера ?L не з’являється ні в якому
диз’юнкті з S. Якщо літера L чиста в S, то викреслимо всі диз’юнкти, які
містять L. Множина S’, що залишилася, суперечна тоді і тільки тоді, коли
і S суперечна.

Правило розщеплення. Якщо множину S можна подати у вигляді (A1 v L) & …
&( Am v L) & (B1 v ?L) & … & (Bn v ?L) & R, де Ai , Bi і R чисті від
L і ?L, S1 = A1 & … & Am & R і S2 = B1 & … & Bn & R, то S суперечна
тоді і тільки тоді, коли (S1 v S2) суперечна.

Теорема. Метод Девіса-Патнема є коректним.

Д о в е д е н н я.

Правило 1. Оскільки тавтологія виконується при будь-якій інтерпретації,
то S’ – суперечність тоді і тільки тоді, коли і S – суперечність.

Правило 2. Якщо S’ – пуста множина диз’юнктів, то всі диз’юнкти з S
включають L. Значить всяка інтерпретація, яка включає L, може
задовольняти S. Отже, S виконується в цій інтерпретації. Покажемо тепер,
що S” суперечна тоді і тільки тоді, коли S суперечна. Припустимо, що S”
суперечна. Якщо S несуперечна, то існує модель M для S, яка включає
L.Для S” модель M повинна задовольняти всі диз’юнкти, які не включають
L. Тепер оскільки на M літера ?L суперечна, то моделі M повинні
задовольняти всі диз’юнкти, які на початку включали ?L. Отже S”
виконується на моделі M. А це суперечить тому, що S” не має моделі.
Таким чином, S теж повинна бути суперечністю.

Навпаки, нехай S – суперечність. Якщо S” виконується при деякий
інтерпретації, то існує модель M” для S”. Звідси випливає, що всяка
інтерпретація, яка включає модель M” і L, повинна служити моделлю для
S’. А це суперечить тому, що S не має моделі. Отже, S” повинна бути
суперечністю. Значить S суперечна тоді і тільки тоді, коли S”
суперечна.

Правило 3. Припустимо, що S’ – суперечність. Тоді і S буде суперечністю,
оскільки S’ – підмножина множини S. Навпаки, нехай S – суперечність.
Якщо S’ виконується при деякій інтерпретації, то S’ має модель M. Звідси
випливає, що всяка інтерпретація S, яка включає M і L, є моделлю для S.
А це суперечить тому, що S не має моделі. Отже, S повинна бути
суперечністю. Таким чином, S’ – суперечність тоді і тільки тоді, коли S
– суперечність.

Правило 4. припустимо, що S – суперечність. Якщо S1 v S2 виконується
при деякій інтерпретації, то або S1, або S2 має модель. Коли S1(S2)
має модель M, то всяка інтерпретація S, яка включає ?L(L), є моделлю
для S. А це суперечить припущенню. Значить S1 v S2 — суперечність.
Припустимо тепер, що S1 v S2 – суперечність. Якщо S виконується при
деякій інтерпретації, то S має модель M. Коли M включає ?L(L), то M
може задовольняти S1(S2), а це суперечить тому, що S1 v S2 не має
моделі. Отже, S повинна бути суперечністю. Таким чином, S суперечна тоді
і тільки тоді, коли S1 v S2 суперечна.

Теорема доведена.

Метод резолюцій.

Метод резолюцій – це, по суті узагальнення правила одно літерних
диз’юнктів Девіса- Патнема.

Розглянемо диз’юнкти виду

C: P,

C’: ?P v Q.

Користуючись правилом одно літерних диз’юнктів, із C і C’ можна одержати
диз’юнкт C’’: Q.

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

Правило резолюцій.

Для будь-яких диз’юнктів C і C’, якщо існує літера L в C, контрарна
літері L’ в C’, то, викресливши L і L’ із C і C’ відповідно, побудуємо
диз’юнкцію членів, що залишилися. Побудований диз’юнкт називається
резольвентою C і C’.

Важливу властивість резольвенти двох диз’юнктів – C1 і C2 – виявляє
таке твердження.

Теорема.

Нехай дано два диз’юнкти: C1 і C2. Тоді резольвента C диз’юнктів C1 і
C2 – логічний наслідок C1 і C2.

Д о в е д е н н я.

Нехай C1 = L v C1’, C2 = ?L v C2’, C = C1’ v C2’, де C1’,C2’ –
диз’юнкції літер. Припустимо, що C1 і C2 виконуються при інтерпретації
h. Нехай L хибна в h. Тоді C1 не може бути одиничним диз’юнктом,
оскільки C1 була б хибною в h. Отже, C1’ повинна виконуватись в h, а
тоді і C = C1’ v C2’ виконується в h. Таким чином, C1’ v C2’ повинна
виконуватись при інтерпретації h. Теорема доведена.

Означення:

Нехай S – множина диз’юнктів. Резолютивним виведенням диз’юнкта C із S
називається така скінченна послідовність C1, C2, … , Ck диз’юнктів, в
якій кожний із Ci або належить S, або є резольвентою диз’юнктів, що
передують Ci, і C = Ck.

Виведення пустого диз’юнкта 0 із S називається доведенням суперечності
S, або спростуванням S.

Говорять, що диз’юнкт C може бути виведений або одержаний із S, якщо
існує резолютивне виведення C із S.Правило резолюцій – досить потужне
правило виведення. Множина диз’юнктів S суперечна тоді і тільки тоді,
коли існує резолютивне виведення пустого диз’юнкта 0 із S.

Додаток 1.

Приклад до методу Куайна.

Довести, що формула

P= (((p & q) ? r) & (p ? q)) ? (p ? r) є теоремою числення висловлювань.

Р о з в ’ я з о к :

Множина висловлювань формули P є {p, q, …, r}. Вибираємо висловлювання
p. При цьому може бути два випадки.

1. p=1. Тоді

P= (((1 & q) ? r) & (1 ? q)) ? (1 ? r) = ((q ? r) & q) ? r = P’.

Вибираємо тепер q і розглядаємо знову можливі випадки:

a1) q=1, тоді P’= ((1 & r) & 1) ? r = r ? r – тавтологія;

a2) q=0, тоді P’= ((0 ? r) & 0) ? r = 0 ? r = 1.

2. p=0. Тоді

P= (((0 & q) ? r) & (0 ? q)) ? (0 ? r) = ((0 ? r) & 1) ? 1 = 1 ? 1 = 1.

Отже, дана формула є тавтологією, а значить, і теоремою числення
висловлювань. Крім того, можливі інтерпретації формули r в даній формулі
P не відіграють ніякої ролі.

Приклад до методу редукції.

Чи є формула

P = ((p & q) ? r) & (p ? (q ? r)) тавтологією?

Р о з в ’ я з о к :

Нехай для деякої інтерпретації h маємо h(P) = 0.

Тоді h(p ? (q ? r)) = 0 і h((p & q) ? r) = 1.

Застосуємо цю ж процедуру до першої з формул.

Одержимо h(p) = 1 і h(q ? r) = 0.

Звідси знаходимо, що h(p) = 1, h(q) = 1 і h(r) = 0, але отримані
значення суперечать тому, що h((p & q) ? r) = 1. Одержана суперечність
показує, що формула P – тавтологія.

Додаток 2 .

Приклади до методу Девіса-Патнема.

Приклад 1.

Довести, що S = (P v Q v ?R) & (P v ?Q) & ?P & R & U суперечна.

Р о з в ’ я з о к :

(P v Q v ?R) & (P v ?Q) & ?P & R & U

(Q v ?R) & (?Q) & R & U — правило 2 з ?P

?R & R & U — правило 2 з ?Q

0 & U — правило 2 з ?R

Оскільки останній диз’юнкт включає пустий диз’юнкт 0, то формула S
суперечна.

Приклад 2.

Показати, що S=(P v Q) & ?Q &( ?P v Q v R) несуперечна.

Р о з в ’ я з о к :

(P v Q) & ?Q &( ?P v Q v R),

P & (?P v ?R) — правило 2 з ?Q

?R — правило 2 з P

0 — правило 2 з ?R

Остання множина являє собою пустий диз’юнкт. Отже, S несуперечна .

Приклад до методу резолюцій.

Приклад 1 .

Перевірити суперечність множини диз’юнктів S = { P, ?P v Q v R, ?Q v
C, ?R v C, ?C }.

Розв’язок

Застосовуючи правило резолюції (ПР) до S, маємо:

P — диз’юнкт 1,

?P v Q v R — диз’юнкт 2,

?Q v C — диз’юнкт 3,

?R v C — диз’юнкт 4,

?C — диз’юнкт 5,

Q v R за ПР із (1), (2),

?R за ПР із (4), (5),

(8)апі?Q за ПР із (3), (5),

Q за ПР із (6), (7),

(10) 0 за ПР із (8), (9).

Отже, задана множина диз’юнктів суперечна, оскільки з неї виводиться
пустий диз’юнкт.

Додаток 3 .

Приклад до методу резолюцій.

Приклад 2 .

Перевірити суперечність множини диз’юнктів S = { P v Q, P v R, ?Q v
?R, ?P }.

Розв‘язок

Застосовуючи ПР до S, маємо:

P v Q — диз’юнкт 1,

P v R — диз’юнкт 2,

?Q v ?R — диз’юнкт 3,

?P — диз’юнкт 4,

P v ?R за ПР із (1), (2),

Q за ПР із (1), (4),

P v ?Q за ПР із (2), (3),

R за ПР із (2), (4),

P за ПР із (2), (5),

(10) ?R за ПР із (3), (6),

(11) ?Q за ПР із (3), (8),

(12) ?R за ПР із (4), (5),

(13) ?Q за ПР із (4), (7),

(14) 0 за ПР із (4), (9).

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

(5) Q за ПР із (1), (4),

(6) R за ПР із (2), (4),

(7) ?Q за ПР із (3), (6),

(8) 0 за ПР із (5), (7).

Висновок:

Дана курсова робота дає можливість краще зрозуміти і вникнути в суть
ідей дискретної математики.

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

Рекомендована література:

Мендельсон Е. Введення в математичну логіку. – М.: Мир, 1988. – 320 с.;

Новиков П. С. Елементи математичної логіки. – М.: Наука, 1973 – 399 с.;

Капітонова Ю. В., Кривий С. Л., Летичевський О. А., Луцький Г. М.,
Печорін М. К. Основи дискретної математики. – К.: Наукова думка, 2002. –
580 с.

PAGE

PAGE 12

Похожие записи