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

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

ГоловнаМатематика, Геометрія, Статистика → Методи перевірки тотожності формул числення висловлювань - Курсова робота

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


Курсова робота
Методи перевірки тотожності формул числення висловлювань
Зміст
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) незалежно від інтерпретації.
Щоб перевірити формулу числення висловлень на тотожність, тобто чи є вона тавтологією, чи суперечністю, потрібно знайти її значення при всіх можливих інтерпретаціях. Будемо називати цей метод тривіальним. Хоча він досить простий, але його недолік - громіздкість. Існують і більш досконалі методи. Розглянемо деякі з них.
Алгебраїчний метод.
Алгебраїчний метод ґрунтується на застосуванні законів булевої алгебри для спрощення формул логіки числення висловлювань. Оскільки різні формули можуть набувати одних і тих самих значень, тобто можуть бути логічно еквівалентними, то краще вибрати для відповідної перевірки ту з формул, яка простіша. Прикладами такого роду перетворень можуть служити алгоритми побудови ДНФ і КНФ. Крім того, якщо Р - деяка скінченна множина формул, яка складається із n формул, то, користуючись формулами з Р, можна побудувати нескінченну множину формул, серед яких існує лише 2 логічно різних формул. Алгебраїчний метод дає можливість виділяти цю множину формул, тобто замінити розгляд нескінченної множини формул скінченною множиною.
Метод Куайна.
Метод Куайна являє собою безпосереднє узагальнення тривіального алгоритму.
Нехай {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
Loading...

 
 

Цікаве