Xreferat.com » Рефераты по математике » Алгоритмічні проблеми

Алгоритмічні проблеми

height="71" align="LEFT" />0, якщо х О Wx

f (x, y)=

не визначена, якщо x П Wx

Цю функцію ми ввели для того, щоб далі скористатися s-m-n-теоремою. Тим самим ми розглядаємо х як параметр, і нас цікавлять функції gx, такі, що gx(y)@ f (x, у). При цьому ми вибрали f так, що gx=0Ых О Wx.

Теза Черча (чи підстановка з використанням 0 і yu) показує, що функція f обчислювана. Тому існує тотальна обчислювана функція k(x), що дається s-m-n-теоремо., така, що f (x, у)@fk(x); тобто fk(x)=gx. Таким чином, по визначенню


(*) х О WxЫ fk(x)= 0


Отже, питання про те, чи вірно, що х О Wx, можна вирішити, відповівши спочатку на питання: чи вірно, що fk(x)=0? Тим самим ми звели загальну проблему «х О Wx» до загальної проблеми «фx=0»; оскільки перша з них нерозв'язна, те нерозв'язна і друга, що і було потрібно довести.

У зв'язку з тим що це перший приклад подібного роду, що зустрівся нам, розглянемо останню частину нашого міркування більш докладно. Нехай g-характеристична функція проблеми «фx=0», тобто


Алгоритмічні проблеми1, якщо фx=0

g(x)=

0, якщо фx№0


Припустимо, що функція g обчислювана. Тоді обчислюваною буде і функція h (х) = g (k (х)). У той же час співвідношення (*) дає


Алгоритмічні проблеми1, якщо фk(x)=0, тобто xО Wx,

h(x)=

0, якщо фk(x)№0, тобто xП Wx.

Тим самим у силу теореми 1.1 функція h не є обчислюваною. Стало бути, і функція g не є обчислюваною, так що проблема «фx=0» нерозв'язна. я

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

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

1.5. Наслідок. Проблема «фx=фy» нерозв'язна.

Доведення. Легко переконатися в тому, що ця проблема складніша проблеми «фx=0». Нехай с – таке число, що фс=0. Якщо f (x, y) – характеристична функція проблеми фx = фу, то функція g (x)=f (х, с) є характеристична функція проблеми «фx=0». По теоремі 1.4 функція g необчислювана, так що необчислювана і функція f. Отже, проблема «фx=фy» нерозв'язна.

У наступних результатах ми знову скористаємося s-m-n-теоремою для зведення проблеми «х О Wx».

1.6. Теорема. Нехай c – довільне число. Наступні проблеми нерозв'язні.

(а) (Проблема входу) «c О Wx» (чи в еквівалентному формулюванні «Рx (с)Ї», чи «c О Dom (фx)»);

(b) (Проблема виходу) «c О Ex» (чи в еквівалентному формулюванні «с О Ran (фx)»).

Доведення. Ми можемо звести проблему «х О Wx» до обох цих проблем одночасно. Розглянемо функцію f (х, у), визначену в такий спосіб:


y, якщо х О Wx

Алгоритмічні проблемиf (x, y)=


не визначена в протилежному випадку


(Маючи на увазі використовувати s-m-n-теорему, ми будемо розглядати функції gx, для яких gx(y)@ f (x, у). Функцію f ми вибрали таким чином, що c О Dom (gx)Ы х О Wx Ыc О Ran(gx).) У силу тези Черча функція f обчислювана, так що s-m-n-теорема дає тотальну обчислювану функцію k, таку, що f (х, у)@ фk(x)(y). З визначення f ми бачимо, що


x О WxЮWk(x)=Ek(x)=N

так що c О Wk(x) і c О Ek(x),і

x П WxЮWk(x)=Ek(x)=Ж


так що c П Wk(x) і c П Ek(x). Тим самим ми звели проблему «x О Wx» до кожної з проблем «c О Wx » і «c О Ex «.

Завершуючи Доведення пункту (а) більш докладно, ми бачимо, що якщо g-характеристична функція проблеми «c О Wx », то


Алгоритмічні проблеми1, якщо x О Wx,

g (k(x))=

0, якщо x П Wx


Ця функція не є обчислюваною (теорема 1.1), так що функція g теж не може бути обчислюваною. Отже, проблема «c О Wx » нерозв'язна.

Докладне доведення пункту (Ь) проводиться аналогічно. я

Ми закінчимо цей параграф одним дуже загальним результатом про нерозв'язність, з якого негайно випливають теореми 1.4 і 1.6. При цьому ми знову скористаємося для зведення проблеми «х О Wx »

s-m-n-теоремою.

1.7. Теорема (теорема Райса). Нехай ВН b1 і B№ Ж, b1. Тоді проблема «фx О B» нерозв'язна.

Доведення. Співвідношення для розв'язних множин (теорема 2–4.7) показують, що проблема «фx О B» розв'язна тоді і тільки тоді, коли розв'язна проблема «фx О b1 B». Тому без втрати загальності ми можемо вважати, що ніде не визначена функція fЖ не належить B (якщо це не так, то твердження можна довести для b1 B).

Виберемо деяку функцію g О B. Розглянемо функцію f (x, у), що задається так:


Алгоритмічні проблемиg(y), якщо x О Wx,

f (x, y)@

не визначена, якщо x П Wx.


Користаючись s-m-n-теоремою, ми одержуємо тотальну обчислювану функцію k (x), таку, що f (x, у) @ фk(x) (y),). Таким чином, ми бачимо, що


x О Wx Ю фk(x) =g, тобто фk(x) О B

x П Wx Ю фk(x) =fЖ, тобто фk(x) П B


Це значить, що за допомогою обчислюваної функції k ми звели проблему «х О Wx » до проблеми

«фх О В». Тепер уже стандартним чином можна покласти, що проблема «фх О В» нерозв'язна.

Теорема 1.4, наприклад, негайно випливає з теореми Райса, якщо взяти В ={0}, а теорема 1.6 (а) – якщо взяти В={g О b1:c О Dom(g)}. Аналогічно можна скористатися теоремою Райса і у наступних вправах.

1.8. Вправи.

1. Покажіть, що наступні проблеми нерозв'язні.

«х О Ех «. (Указівка. Скористайтеся діагональним методом чи зведіть до цієї проблеми проблему

«x О Wx» за допомогою s – m- n – теореми.)

(b) «Wx=Wy «. (Указівка. Зведіть до цієї проблеми проблему «функція фx тотальна».)


(c) «фx(х)=0».

(d) «фx(y)=0».

(e) «х О Еу «.


(f) «функція фx тотальна і постійна».


(g) «Wx=Ж».


(h) «множина Еx нескінченна».

(i) «фх=g», де g є будь-яка фіксована обчислювана функція.

2. Покажіть, що не існує тотальної обчислюваної функції f (x, у), що володіє наступними властивістями: якщо програма Рх(у) зупиняється, те це відбувається за f (x, у) чи менше кроків (Указівка. Покажіть, що якби така функція існувала, те проблема зупинки була б розв'язна.)

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

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


6. Дані і знання. Логіка висловлень (ЛВ) в представленні знань


1. Логіка висловлень (пропозиційна логіка) [1] – одна з базових теорій математичної логіки, на якій базуються більш складні формальні логіки.

Алфавіт логіки висловлень (ЛВ) складається зі зчисленної множини елементарних висловлень, які позначуються літерами (можливо, з індексами) і 5 логічних операцій: заперечення (^), кон’юнкції (/, або &), диз’юнкції (/), імплікації (->) і тотожності, еквівалетності (<->), які задаються скінченими таблицями істинності.

Як відомо, кожне висловлення може мати значення істинно (позначається Т, 1), або хибно (позначається F, 0).

Алфавіт висловлень дає змогу будувати складні висловлення (формулу) із простіших за допомогою логічних операцій [1] по наступній рекурсивній схемі, а саме, формулами ЛВ є тільки наступні конструкції:

– кожне висловлення є формулою;

– якщо А і В є формули, то ^A, (A/B), (A/B), (A -> B) i (Aя2=я0B) – є формулами.

Формули задають синтаксис мови ЛВ. А який сенс, семантика цієї мови?

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

Літера, або літерал – це елементарне висловлення р або його заперечення ^p. Літери р і ^р є протилежні.

Формула ЛВ називається виконуваною, якщо вона допускає деяку модель, тобто її можна інтерпретувати із значенням Т.

Формула ЛВ А називається суперечністю (не виконуваною), якщо А = F для всіх моделей А (наприклад, (р/^p).

Формула ЛВ називається тавтологією, якщо вона істина при всіх інтерпретаціях (на всіх моделях). Відмітимо, що заперечення тавтології є суперечність.

2. Нехай, Е – множина формул ЛВ. Формула А є наслідком (логічним) з Е (позначення, Е (= А), якщо на всіх моделях, на яких істині всі формули з Е, істина також формула А. Ясно, що тавтологія є наслідком із пустої множини формул ЛВ.

Легко довести [1], що мають місце:

Твердження 1. Нехай, Е = {H1, H2,… Hn} є множиною формул ЛВ.

Формула А є наслідком (логічним) з Е (E (= A) тоді і тільки тоді, коли імплікація:


(H1/H2/…/Hn) -> A


є тавтологією. Прямим наслідком із твердження 1 є

Твердження 2. Нехай, Е = {H1, H2..Hn} є множиною формул ЛВ.

Формула А є наслідком (логічним) з Е тоді і тільки тоді, коли формула


(H1/H2/…/Hn/^A)


є суперечністю.

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

(L1/L2/../Lm).


Її часто записують у «скороченому» вигляді як послідовність літералів: {L1., Lm}.Пустий диз’юнкт – єдиний диз’юнкт, що не виконується, і його позначають через Л.

Кон’юктивною нормальною формою (КНФ) називається кон’юнкція скінченої кількості диз’юнктів.

Теорема 1. Довільна формула ЛВ має логічно еквівалентну їй КНФ.

Наступний алгоритм нормалізації формул ЛВ дає доведення теореми 1.

Етап 1. Спочатку замінюємо (А<->В) на ((А->B)/(B->A)), а потім заміняємо (U->V) на (^U/V). Це робиться для виключення операцій <-> і ->.

Етап 2. Необхідну кількість раз застосовуються перетворення на основі законів де Моргана:


^(X/Y) ==> (^X/^Y), ^(X/Y) ==> (^X/^Y).


Символ ==> означає «замінити на». В цій заміні подвійні заперечення елімінуються, тобто


^^X ==> X.


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

Етап 3. необхідну кількість разів застосовуються правила перетворень, що виведені із законів дистрибутивності:


X / (Y / Z) ==> (X / Y) / (X / Z)

(X / Y) / Z ==> (X / Z) / (Y / Z).

Етап 4. Диз’юнкти, що містять протилежні літерали (тобто висловлення і його заперечення), є тавтологіями і можуть бути еліміновані. Також елімінуються повторення літералів у межах одного ж і того диз’юнкта.

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

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

Єдиним не виконуваним диз’юнктом є пустий диз’юнкт Л.

3. Не існує загального ефективного критерію для перевірки виконуваності КНФ. Але існує зручний метод для виявлення не виконуваності множини диз’юнктів. Дійсно, множина диз’юнктів є не виконувані тоді і тілки тоді, коли пустий диз’юнкт Л є логічним наслідком із неї. Таким чином, не виконуваність множини S можна перевірити, породжуючи логічні наслідки з S, поки не отримаємо пустий диз’юнкт. Для цього використовується наступна схема міркувань.

Припустимо, що дві формули (A / X) i (B / ^X) – істині. Якщо Х також істина, то звідси випливає, що B істина. Навпаки, якщо Х хибна, то А істина, тобто отримується правило


{(A / X), (B / ^X)} [= A / B,


яке можна записати у вигляді


{^X -> A, X -> B} [= A / B. Зокрема, якщо Х – висловлення, а A i B – диз’юнкти, то правило називається правилом резолюції.

Твердження 3. Нехай s1 i s2 – диз’юнкти КНФ S. Якщо літерал р входить у s1 і ^p – у s2, то диз’юнкт


r = (s1{p}) / (s2{^p})

є логічним наслідком КНФ S.

Тут через si{L} позначається диз’юнкт, що отримується з si вилученням літералу L. Диз’юнкт r називається резольвентою диз’юнктів s1 i s2.

Твердження 4. Нормальні форми S i (S / r) еквівалентні.

Доведення невиконувансті формул дуже важливо для роботи із знаннями. Воно широко використовується в логічному програмуванні. З твердження 3 і 4 випливає наступний алгоритм – метод резолюцій для доведення того, що КНФ S є суперечністю.

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

Крок 1. Якщо Л належить S, то КНФ S є суперечністю, і алгоритм зупиняється.

Крок 2. Вибираються довільні L, s1, s2 такі, що літерал L входить в диз’юнкт s1, а ^L входить у s2.

Крок 3. Обчислюється резольвента r.

Крок 4. КНФ S замінюється на КНФ S' = S / r, і повертаються на крок 1. Вибираються довільні L, s1, s2 такі, що літерал L входить в диз’юнкт s1, а ^L входить у s2.

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

1. Необхідно побудувати кон’юктивну нормальну форму для формули А логіки висловлень, де


A = (p -> (q -> r)) -> ((p / s) -> r).


Використаємо алгоритм із розділу 1.2. Кожна з нижченаведених формул еквівалентна А.

Етап 1 (виключення імплікацій).

(p -> (q -> r)) -> ((p / s) -> r),

^ (p -> (q -> r)) / ((p / s) -> r),

^ (^p / (q -> r)) / (^(p / s) / r),

^ (^p / (^q /r)) / (^(p / s) / r),


Етап 2.


(^ ^p / ^ (^q /r)) / ((^p / ^s) / r),

(^ ^p / (^ ^q / ^r)) / ((^p / ^s) / r),

(p / (q / ^r)) / ((^p / ^s) / r).


Етап 3.


a) (p / ((^p / ^s) / r)) / ((q / ^r) / / ((^p / ^s)

/ r))

b) (p / (^p / ^s) / r)) / / (q / (^p / ^s) / r) /

(^r / (^p / ^s) /r);

c) (p / ^p / ^s / r) / / (q / ^p / ^s / r) / (^r

/ ^p / ^s / r);

d) T / (q / ^p / ^s / r) / T;

e) (q / ^p / ^s / r).


Ми отримали, що КНФ В = (q / ^p / ^s / r) формули А складається з одного диз’юнкта.

Приклад

2. Необхідно перевірити за допомогою метода резолюцій, чи є КНФ S суперечністю, де


S = {p /q, p / r, ^q / ^r, ^p}.

Диз’юнкти зручно перенумерувати. Отримаємо список:


1. p /q

2. p / r

3. ^q / ^r

4. ^p


Далі обчислюються резольвенти і додаються до S. У нижченаведеному списку кожний диз’юнкт – резольвента деяких попередніх диз’юнктів. Номера їх наводяться з права від відповідної резольвенти


5. p / ^r 1,3

6. q 1,4

7. p / ^q 2,3

8. r 2,4

9. p 2,5

10. ^r 3,6

11. ^q 3,8

12. ^r 4,5

13. ^q 4,7

14. Л 4,9


Отримали, що із КНФ S виводиться пустий диз’юнкт Л, тобто S є суперечністю (не виконуваною формулою).


7. Логіка предикатів (ЛП) в представленні знань


(Теорема про нерозв'язність числення предикатів)

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

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

Мається точне поняття доведення твердження числення предикатів, причому твердження доводиться тоді і тільки тоді, коли воно істинно. У 1936 році Черч показав, що доведеність (і, отже, істинність) у численні предикатів нерозв'язна на відміну від більш простого пропозиціонального числення. (Гільберт вважав цей результат самим фундаментальної результатом, що стосується нерозв'язності, у всій математиці.)

Просте доведення нерозв'язності проблеми істинності можна дати з використанням МНР, хоча це вимагає деякого знайомства з численням предикатів. Читачу, що не знайомий з початками логіки предикатів, ми радимо пропустити приведений нижче зразок доведення.

5.1. Теорема. Проблема істинності числення предикатів першого порядку нерозв'язна.

Доведення. (Тим, хто не знайомий з численням предикатів, рекомендується пропустити.)

Нехай Р – деяка програма в стандартному виді, що містить команди I1,…, Is, і нехай u=r(P) (визначення див. § 2 р. 2). Ми будемо використовувати наступні позначення символів числення предикатів:

O – індивідний символ,

' – символ одномісної функції (значення якої на х дорівнює х'),

R-символ (u+1) – місного відношення,

x1, x2,…, xa, у – символи індивідних змінних.

Далі, для будь-якої команди Ii, можна записати твердження числення предикатів ti, що описує результат виконання команди Ii. При цьому ми використовуємо символ Щ для позначення зв'язки «і» і символ ® для позначення імплікації. Твердження ti, визначається в такий спосіб:


якщо Ii=Z(n), тo ti, є твердження

"x1 … "xu: R (x1, …, xn, …, xu, i)®R (x1, …, O, …, xu, i ў)

якщо Ii=S(n), то ti, є твердження

"x1 … "xu: R (x1, …, xn, …, xu, i)®R (x1, …, xnў, …, xu, i ў)

(c) якщо Ii=T (m, n), тo ti, є твердження

"x1 … "xu: R (x1, …, xn, …, xu, i)®R (x1, …, xm, …, xu, iў)

(d) якщо Ii=J (m, n, q), тo ti, є твердження

"x1 … "xu: R (x1, …, xu, i)®((xm = xn ®R(x1, …, xu, q))Щ(xm № xn ®R(x1, …, xu, iў)))


Нехай тепер для будь-якого а О N символ Алгоритмічні проблемиsa позначає твердження.


(t0Щt1Щ…ЩtsЩ R (a, O,… O, 1))®$x1 … $xu R(x1, …, xu, s+1)


де t0 є твердження "x"y((х'=у® x=y) Щ xў№O). (Це гарантує нам, що при будь-якій інтерпретації з т, n

О N і m=n випливає, що т=п.)

Твердження R (a, O,…, О, 1) відповідає вихідному стану

а 0 0 …; наступна команда Ii

а будь-яке твердження R(x1,…, хu, s +1) відповідає зупинці (оскільки немає команди Is+1). Ми покажемо, що


(*) Р (а)ЇЫsa істинно.


Припустимо спочатку, що Р(а)Ї і що мається структура, у якій твердження t0,…, ts, і R (a, O,…, O, 1) виконуються. За допомогою тверджень t0,…, ts, ми одержуємо, що кожне з тверджень R(r1,…. ru, k),

що відповідають послідовним станам обчислення, також виконується. Зрештою ми приходимо до того, що для деяких b1,…, bu О N виконується твердження про зупинку R(b1,…, bu, s+1) і, отже, виконується твердження $x1 …$xu R(x1,…, xu, s+1). Таким чином, твердження sa істинно.

Знову, якщо твердження sa істинно, то воно виконується, зокрема, у структурі N, причому предикатний символ R інтерпретується як предикат Ra, для якого

Ra(a1,…, аu, k)єНа деякому етапі обчислення Р (а) у регістрах містяться числа а1, a2,…, au, 0, 0,…, а наступна команда є Ik.

Тоді твердження t0,…, ts, і R (a, O,…, O, 1) також виконуються в цій структурі, а отже, і твердження $x1 …$xu R(x1,…, xu, s+1). Звідси Р(а)Ї.

Якщо в якості Р узяти програму, що обчислює функцію yu (x, х), то співвідношення еквівалентності (*) зводить проблему «x О Wx» до проблеми «s істинно». Звідси випливає, що остання проблема нерозв'язна. я

Математична логіка буяє результатами, що стосуються можливості розв'язання і нерозв'язності. Звичайно мова йде про задачі, у яких необхідно установити, чи буде деяке твердження істинним у всіх математичних структурах визначеного типу. Наприклад, було показано, що проблема «s є твердження, істинне для всіх груп» є нерозв'язною (s тут є твердження мовою числення предикатів першого порядку, що відповідає теорії груп), тоді як проблема «s є твердження, істинне для всіх абелевих груп» розв'язна. (При цьому прийнято говорити, що теорія груп першого порядку нерозв'язна, у той час як теорія абелевых груп першого порядку розв'язна.) Як було показано Тарським [1951], проблема «твердження s істинне в полі дійсних чисел» є розв'язної. З іншого боку, як ми побачимо в р. 8, багато проблем, зв'язаних з формалізацією арифметики натуральних чисел, нерозв'язні.

З іншими прикладами, а також з доведеннями багатьох результатів, що стосуються можливості розв'язання і нерозв'язності в математичній логіці, читач може ознайомитися в книгах Тарського, Мостовського і Робінсона [1953] чи Булоса і Джефрі [1974], а також Єршова [1981]*.

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: