1.Алгоритмічні проблеми
Навчаючиарифметиці в початковій школі, ми познайомилися з додаванням і множенням двохчисел. Нам у явній формі не говорили, що в будь-якої пари чисел існують добутокі сума, а вказали способи і правила їхнього знаходження. Такі способи і правилає прикладами алгоритмів, і обчислювальних (ефективних) процедур.Їхнє застосування не вимагає чи винахідливості чи кмітливості, учню необхіднобуло тільки слідувати інструкціям учителя.
Більшзагально, алгоритм, чи ефективна процедура, – це механічнеправило чи автоматичний метод, чи програма для виконання деяких математичнихоперацій. Приведемо ще кілька прикладів операцій, для яких легко можна вказатиалгоритми:
(1.1)(а) по даному п знайти n-e просте число;
(b)диференціювання полінома;
(c)знаходження найбільшого загального дільника двох натуральних чисел (алгоритмЕвклида);
(d)для двох даних чисел х, у вирішити, чи є х кратним у.
Неформальноі схематично алгоритм представлений на мал. 1а. На вхід подається інформація чиоб'єкт, що підлягає обробці (наприклад, поліном у прикладі (1.1) (b), паринатуральних чисел у прикладах (1.1) (с) і (d)), а виходом є результат обробкиоперації над входом (так, для (1.1) (b) це похідна полінома, а для (1.1) (d) –відповідь «так» чи «ні»). Вихід виробляється автоматично чорним ящиком-якийможе бути комп'ютером або школярем, що діє по інструкції, чи навіть дужерозумним добре тренованим собакою. Алгоритм є процедура (чи спосіб обчислення),здійснювана чорним ящиком для одержання виходу з входу.
Якщоалгоритм, чи ефективна процедура, використовується для обчислення значеньчислової функції, то ця функція називається ефективно вычислимой, чи алгоритмічновычислимой, чи просто вычислимой. Наприклад, функції ху,
Чорний ящик Вхідвихід/> /> /> /> /> /> />
НОД(х, у)= найбільший загальний дільник чисел х и у и f(n)=просте число вираховувані в неформальному змісті, як уже відзначалося вище.
Розглянемо,з іншого боку, наступну функцію:
/>
1,якщо в десятковому розкладанні числа pi знайдеться
g(n)==рівно п підряд йдущих цифр 7;
0 упротивному випадку.
алгоритмпредикативний операторний знання
Більшістьматематиків вважають, що g є цілком «законною» функцією. Але чивираховувана функція g? Існує механічна процедура для послідовного породженняцифр у десятковому розкладанні pi, тому напрошується «процедура» для обчисленняфункції g. «При заданому п почніть обчислювати десятковий розкладpi по одній цифрі за один такт часу і відзначайте появу сімок. Якщо наякому-небудь кроці з'явиться відрізок, що складається рівно з п сімок,зупините процес обчислення і покладете g(n)=0. Якщо такий відрізок небуде обнаружен, то покладете g(n)=0».
Недолікомцієї «процедури» є та обставина, що якщо для деякого п не існує відрізказ п – сімок, тоді ні на якому кроці процесу ми не можемо зупинитись ізробити висновок про те, що цей факт має місце. На кожному даному кроці миможемо очікувати, що така послідовність сімок може зустрітися в щенедослідженній нескінченній частині розкладання pi. Таким чином, ця «процедура»буде продовжуватися нескінченно довго для усякого входу п, такого, щоg(n)=0; тому вона не є ефективною процедурою. (Можливо, що існує ефективнапроцедура для обчислення g, заснована, імовірно, на деяких теоретичнихвластивостях числа pi. В даний час, однак, така процедура невідома.)
Цей приклад виявляє дві характерні риси поняття ефективноїпроцедури, а саме що така процедура відбувається за деяку послідовність кроків(кожен крок виконується за кінцевий час) і що кожен вихід з'являється післякінцевого числа кроків.
Дотеперми неформально описували поняття алгоритму (чи ефективної процедури) ізв'язаного з ним поняття обчислюваної функції. Ці поняття мають потребу вуточненні, перш ніж вони стануть основою для математичної теоріїобчислюваності.
Визначення будутьдані в термінах простого «ідеалізованого комп'ютера», що виконує програми.Ясно, що процедури, що можуть бути пророблені реальним комп'ютером, єприкладами ефективних процедур. Однак кожен окремий реальний комп'ютеробмежений як величиною чисел, що надходять на вхід, так і розміром доступного робочогопростору (для запам'ятовування проміжних результатів); саме в цьому відношеннінаш «комп'ютер» буде ідеалізованим відповідно до неформальної ідеї алгоритму.Програми нашої обчислювальної машини будуть кінцевими, і ми скажимо, щобобчислення, що завершуються, виконувалися за кінцеве число кроків. Входи івиходи ми обмежимо натуральними числами; це не є істотним обмеженням, оскількиоперації, що включають інші види об'єктів, можуть бути закодовані як операціїнад натуральними числами. (Більш докладно ми зупинимося на цьому в § 5.)
2.Необхідні поняття, факти і нотація із інших математичних дисциплін
Тут дано оглядматематичних понять і роз'яснимо позначення і терміни, що будуть використанінадалі.
1.Множини
Дляпозначення множин звичайно будуть використовуватися прописні букви А, В, С….Тут х/>А позначає, що х єелементом множини А чи належить множині А, а х/>А означає, що хне належить множині А. Позначення {х/… х…}, де…х… є деякетвердження, що включає х, означає множину всіх об'єктів х, дляяких…х… вірно. Так, {х/х є парним натуральним числом} є множина {0,2,4,6,…}.
ЯкщоА, В суть множини, то запис A /> Возначає, що А міститься (як частина) в В (чи А є підмножиноюВ); запис А/>В означає, щоА/>В, але А/>В (тобто А є власноюпідмножиною В). Об'єднання множин А, В, є множина {х| х/>А чих/>В (чи відразу двоммножинам А, В)} і позначається А U В; перетин А, В є множина {х/х/>А і х/>В} і позначається черезА/>В. Різниця (чи відноснедоповнення) множин А, В є множина {х / х/>Аі х/>В} і позначається А\В.
Порожня множина позначається через 0. Стандартний символ Nпозначає множину натуральних чисел {0, 1, 2, 3,…}. Якщо А – множина натуральнихчисел (тобто А/>N), то А позначаєдоповнення до А до N, тобто N\А. Через N+ позначається множинадодатніх натуральних чисел {1,2,3,…}, а множина цілих чисел позначається черезZ.
Упорядкована пара елементів х, у позначається (х,у); таким чином, (х, у)/>(у, х).Картезіанським, чи декартовым, добутком множин А и Вназивається множина {(х, у)/х/>А, у/>В}, і позначається воначерез А/>В.
Більшузагальнено, запис (х1…, хn) позначає упорядкований n-набір(п-ку) елементів х1,…, хn; часто цей n-набірпозначається однією жирною буквою х. Якщо А1,…,Аn суть множини, те А1/>…/>Аn позначаємножину n-ок {(х1,…, хn)/х1 />А1 і х2/>А2…хn/>Аn}. ДобутокА/>А/>…/>А (п разів) скороченопозначають як Аn; а А1 означає просто А.
2.Функції
Миприпускаємо, що читач знайом з основним поняттям функції і розходженням міжфункцією f і окремим значенням f(х) на даному х, на якомуфункція визначена. Областю (визначення) функції f називаєтьсямножина {x/f(x) визначена} і позначається Dom(f); мибудемо говорити, що f (х) не визначена, якщо x/>Dom(f). Множина {f(х) | х /> Dom (f)}називається множиноюзначень, чи образом (range), функції fі позначається через Ran (f). Якщо А и В – множиниі,то будемо говорити, що f є функція з A в В, якщо Dom (f)/>A и Ran(f)/>В. Коли Dom(f)=A,буде застосовуватися позначення f: A/>r.
Функціяназивається ін’єктивною, якщо з х, у/> Dom(f) і х/>у випливає f(х)/>f (у). Для ін’єктивноїфункції f через f -1 позначається функція, зворотнядо f, тобто така єдина функція g, що Dom (g)=Ran (f) g(f(x))=x для всіх х/>Dom(f). Функція f з А в В називається сюр’єктивною,якщо Ran(f)=B.
Якщо f:A /> В и функція fин’єктивна (сюр’єктивна), то f називається ін'єкцією (з А в В)(сюр’єкцією (з А в В)). Функція, що є одночасно ін'єкцією ісюръекцией, називається биекцией.
Припустимо,що f є функцією, а Х – множина. Обмеженням f на Хназивається функція з областю визначення Х/>Dom(f),значення якої в кожному х /> Х /> Dom (f) дорівнює f(x).
Обмеженняf на Х позначається через f|X. Ran (f|X) позначаєтьсячерез f(X). Якщо Y – множина, то прообразом Y відносно fназивається множина f-1(Y)={x|f(x)/>Y}.(Помітимо, що прообраз визначений навіть тоді, коли функція не ин’єктивна.)
Якщо f,g-функції, то будемо говорити, що g продовжує f, коли Dom (f)/> Dom (g) і f(х) =g (х) для всіх х /> Dom (f);у коротшому запису: f=g/Dom(f). Це відношення функцій f, gзаписується як f /> g.
Композиція двох функцій fіg є функція з областю визначення {x/x/>Dom(g) і g(x)/>Dom(f)}, значення якої,коли вона визначена, є f (g(x)). Цю функцію позначають через f/>g.
Черезf0 позначаємо ніде не визначену функцію; тобто Dom(f0)=Ran(f0)=0.Очевидно, що f0=g|0 для будь-якої функції g.
Вобчисленнях нам часто будуть зустрічатися функції чи вирази, що включаютьфункції, що не усюди визначені. У таких випадках дуже зручне наступнепозначення. Нехай a(x) і b(х) – вирази, що включають змінні х=(х1,…,хn). Тоді запис а(x) />b(x)означає, що для кожного х вираження а(x) і b(x) або одночасно визначеніі рівні, або обидва не визначені. Так, наприклад, для функцій f і gзапис f(x)/>g(x) означає, що f=g;і для довільного числа y запис f(x) /> yозначає, що f(x) визначена і дорівнює y (оскільки y завждивизначене).
Функціївід натуральних чисел. У більшій частині цієї книги ми будемо матисправу з функціями від натуральних чисел, тобто з функціями з Nn в Nдля різних п, здебільшого для п = 1 чи 2.
Функціяf з Nn в N називається п-місною функцією. Значення fна п-кі (x1,…, хn) />Dom(f) записується як f(x1,…, xn) чи f(x),якщо x представляє (x1,…, xn).У багатьох книгах і статтях термін часткова функція використовується дляпозначення функції з Nn у N, область визначення якої не обов'язковозбігається з Nn. Для нас слово функція означає частковуфункцію. Проте при нагоді ми будемо писати «часткова функция», щоб підкреслитиїї можливу «не усюди визначеність». Тотальною функцією з Nn уN ми називаємо функцію з Nn у N), область визначення якої є всі Nn.l
Мизатушовуємо розходження між функціями і їхнім значеннями в різних крапках,особливо у випадку теоретико-числових функцій у двох досить стандартних інедвозначних ситуаціях. По-перше, ми допускаємо такі фрази як «Нехай f(x1,…,xn) – функція…», що означає, що f є n-місною функцією.По-друге, ми часто описуємо функцію в термінах її значення, що задається деякоюформулою. Наприклад, «функція х2» означає «одноміснафункція f, значення якої в кожному х /> Nє х2»; аналогічно «функція х + у» означає «двоміснафункція», значення якої в кожній парі (х, у) /> N2є х+ у.
Функцію,тотожно рівну 0 на N, ми позначаємо через0, і взагалі для т /> N функцію N/>N, значення якої усюдидорівнює т, ми позначаємо жирним символом т.
3.Відношення і предикати
Якщо А– множина, то властивість М(х1,…, хn), щовиконується на деяких n-ках з Аn і не виконується (чипомилкове) на всіх інших n-ках з An, називається п-міснимвідношенням, чи предикатом на А.
Наприклад,властивість х є двомісне відношення (чи предикат) на N; 2 f з Nn у N приводить до (п+ 1) – місцевого предиката М (х, у), що задається умовою:
М (x1,…,хn, у), якщо і тільки якщо f (x1,…, xn)/> у.
Відношенняеквівалентності і порядку. (Читач, не знайомий з цими поняттями, може прибажанні відкласти читання цього параграфа доти, поки він не буде потрібен в гл. 9.)У гл. 9 ми зустрінемося із двома спеціальними видами відносин на множині А.
(a)Бінарне відношення R на множині А називається відношеннямеквівалентності, якщо для всіх х, у, z/>Авиконуються три наступні властивості:
(i)(рефлективність) R (х, х);
(іі)(симетрія) R (х, y)/> R(у, х);
(iii)(транзитивність) якщо R (x, y) і R (у, z), то R (х, z).Говорячи, що х, y еквівалентні (у деякому спеціальному змісті), мимаємо на увазі відношення R (х, у). Потім ми визначаємо класеквівалентності х як множина {у | R (х, у)}, що складається з всіхелементів, еквівалентних х.
(b)Двомісне відношення R на множині А називається частковимпорядком, якщо для всіх х, у, z /> A.
(i)(іррефлексивность) не R (х, х);
(іі)(транзитивність) якщо R (х, у) і R (y, z), те R (x, z).
Частковийпорядок звичайно позначається символом і ми віддаємо перевагузапису х у запису (х, у). Часто визначаютьчастковий порядок, вводячи спочатку предикат
(i) х/>х;
(ii)якщо x/>y і у/>х, те х=у;
(iii)відношення/> транзитивно,а потім визначаючи х у як х/> уи х />у.
4.Логічні позначення
Мискрізь вживаємо стандартні логічні позначення. Символ /> позначає еквівалентністьпо визначенню, /> означає логічнеслідування, а /> позначає «випливаєз». Символи/>, /> використовуються взначенні «для всіх» і «існує» відповідно.
3. Операторні тапредикатні алгоритми – І
(Рекурсивніфункції на області натуральних чисел N)
Розглянемо математичне визначення [1,2] класів функційта предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму(взагалі кажучи, часткового).
1. Введемо зчисленні множини символів або послідовностейсимволів (слів, ідентифікаторів і т. п.) із довільної конструктивноїмножини:
а) індивідні: x, y, z, x0, y0, z0, x1, y1, z1,… xj, yj,zj,…;
б) функціональні: f, g, h, f0, g0, h0, f1, g1, h1,… fj,gj, hj,…;
в) предикатні: P, Q, R, P0, Q0, R0, P1, Q1, R1,… Pj, Qj,Rj,…;
г) константи: a, b, c, a0, b0, c0, a1, b1, c1,… aj, bj,cj,…;
д) мітки: q, i, j, q0, i0, j0, q1, i1, j1,… qk, ik, jk,…
Кожній функціональному та предикатному символу Uоднозначно ставиться у відповідність натуральне число n, яке називаєтьсяарністю даного символа. Цей символ позначається через U(n), або U (x1, x2., xn)та т. п., і називається n-арним символом. Вважається, що ідеалізованийоб'єкт – 0-арний функціональний символ U(0) співпадає з символом константи.
Схемою оператора присвоюванняназивається вираз виду:
z(i) = f(m) (x(1)., x(m)). (1)
Схемою оператора пересилкиназивається вираз виду:
z(k) = y(j) (2)
Схемою прісвоювання константиназивається вираз виду:
z(k) = a, або z(k) = fj(0) (3)
Схемою умови називається виразвиду:
P(s) (x(1)..x(s)) (4)
Схемою програми(СП)S називатимемо об'єкт виду
q0 Ф[0] (i0, j0)
q1 Ф[1] (i1, j1)
……………. (5)
qs Ф[s] (is, js)
В (1) Qs = Qs1 u Qs2, де Qs1 = q0,q1..qs, і
Qs2=i0, j0., is, js – підмножини множин міток. Якправило, якщо не вказане уточнення, будемо вважати, що qi – qj, якщо i – j, (qi,qj належать Q1). Мітки із Q1 називаються мітками передачі управління, а міткиіз (Qs – Qs1) – кінцевими мітками.
Для всіх k є [0_s], Ф[k] – це одна із схем(1) – (4).
Сукупність всіх індивідних змінних СП (5) називається пам«яттю схемиS. Сукупність константанктних, функціональних,предикатних символів і пам» яті S називається сигнатурою, абобазисом, схемиS.
Конструкція вигляду
qr Ф[r] (ir, jr)
із (5) називається схемою команди.
Схемою операторного алгоритму (СОА), або схемою операторноїпроцедури, називається об"єкт виду:
SA = (x1, x2., xn; S;y), (6)
де x1., xn, y – змінні, S – СП вигляду (5).
Схемою предикатногоо алгоритму (СПА), або схемоюпредикатної процедури, називається об"єкт виду:
SP = (x1, x2., xn; S;q [.t.], q [.f.]), (7)
де x1., xn, – змінні, S – СП вигляду (5), а q[.t.], q [.f.]) – кінцеві мітки СП S.
Зауважимо, що пам «яттю алгоритмів (6), (7)називається об» єднання пам«яттіS і змінних x1., xn, y, і x1.,xn називаються вхідними змінними, а y – вихідною змінною.
Ми визначили СП, СОА і СОП як деякі формальні,синтаксичні конструкції. Яка ж семантика (сенс) цих конструкцій? Як із нихотримати справжні алгоритми (програми)?
Семантика схем задається за допомогоюінтерпретацій.Інтерпретація схеми алгоритму W задається парою (D, I), де D – множинадовільної природи, а I – це певне відображення, яке: а) кожному символу змінноїz із пам»яті W ставить у відповідність елемент I(z) із множини D; б)кожному символу константи b із сигнатури W ставить у відповідність елемент I(b)із D; в) кожному m-арному функціональному f(m) (предикатному P(m)) символуспівставляє, відповідно, всюдиозначені функцію I (f(m)): Dm ->D, абопредикат I (P(m)) ->.t..f.
2. Нижче в данному розділі будемо розглядати тількіпідклас схем алгоритмівKS-1, які містять тількидва функціональні унарні символи f, g, один константний символ b і один унарнийпредикатний символ p. Також обмежимо клас інтерпретацій, поклавши, що в цьомукласі KI-1 D завжди співпадає з множиною натуральних чисел N (D=N), авідображення I задовольняє наступним вимогам:
1) I(b) = 0;
2) I (f(x)) = I(x) + 1;
I(x) – 1, коли x>0
3) I (g(x)) = I(x) -^ 1 =0 , коли x=0 (8)
t., коли I(x) =0;
4) I (p(x)) = P0 (x)) = *
f., коли I(x) > 0.
5) I(xi) єN для всіх вхідних змінних СОА іСПА виду (6), (7), і I(y) = 0 для всіх інших змінних із пам'ятівищезгаданих схем алгоритмів.
Опишемо формально функціонування алгоритму A виду (6).
Нехай M(A) = z1, z2..zn..zm – пам'ять алгоріму A,де zi = xi при 1= i = n, і zm = y. ЧерезQ(A) позначимо всі мітки A. Станом пам'яті A будемо називати послідовність (a1..am)натуральних чисел, тобто елемент Nm. Станом (конфігурацією) алгоритму A будемоназивати елемент із D(A) = Q & Nm.
Стан називається: а) проміжковим,якщо q – мітка передачи управління; б) кінцевим (заключним), якщо q – кінцевамітка алгоритму A.
Визначемо функцію переходів F: D(A) –> D(A) алгоритмуA.
1. Коли – кінцевий стан, то
F () = .
2. Коли – проміжковий стан, то значенняF залежить від виду команди qk Ф[k] (ik, jk) в (5).
Якщо Ф[k] має вигляд:
a) zr = zt + 1, то F () =, де q* = ik, br = at + 1, а bu = auдля всіх таких u, що u не рівне r;
b) zr = zt -^ 1, то F () =, де q* = ik, br = at -^ 1, а bu = auдля всіх таких u, що u не рівне r;
c) zr = 0, то F () =, де q* = ik, br = 0, а bu = au для всіх такихu, що u не рівне r;
d) zr = zt, то F () =, де q* = ik, br = at, а bu = au для всіхтаких u, що u не рівне r;
e) P0 (zr), то F () = , де bu = au для всіх u (1= u = m), аq* = ir, якщо ar = 0, і q* = jr, якщо ar > 0.
Перейдемо до визначення функції f[A]: Nn –> N, яку
обчислює алгоритм A при інтерпретації I.
По означенню інтерпретації маємо, що початковий станпам'яті є I (M(A)) = . Стан c[0] = називається початковим станом алгоритму A при інтерпретаціїI. Скінченна або нескінченна послідовність
T(A) = c[0], c[1]., c[k], c [k+1],… (9)
називається траєкторією (шляхом) алгоритму A приінтерпретації I (на вході ), якщо
F (c[k]) = c [k+1] для всіх k із N.
Зрозуміло, що траєкторія (9) для A будуєтьсяконструктивно по програмі цього алгоритму і початковому значенню вхіднихзмінних, що задає інтерпретація I.
При послідовному обчисленні станів c[k] за допомогоюфункції переходів F можливі два випадки:
1) в траєкторії (9) знайдеться стан с[t] = такий, що c[t] – кінцевий стан, а c[0], c[1]., c [t-1] – проміжковістани;
2) в траєкторії (9) всі стани проміжкові, тобтотраєкторія T(A) є нескінченною послідовністю станів A.
У першому випадку будемо вважати, що A обчислює значенняf[A] ( функції f[A] в точці , i f[A] ()= bm. Нагадаємо, що bm природнім чином можна інтерпретувати як число, щознаходиться в вихідній змінній y в стані c[t] алгоритму A, так як, поприпущенню, zm = y.
Якщо в траєкторії (9) всі стани проміжкові, тобтотраєкторія T(A) є нескінченною послідовністю станів A, будемо вважати, що Aциклює в точці , тому значення f[A] ( функціїf[A] в точці не визначено, тобто f[A] () =@. Іншими словами,
bm, коли T(A) – скінченна f[A] () =*
@, коли T(A) – нескінченна (8)
Аналогічно визначається траєкторія і функція переходівдля предикатного алгорітму Aq, і вважається що Aq реалізує предикат;
/>
і q* = q [.t.]; .t., коли T(A)– скінченна,
P[Aq] () = * .f., коли T(A) – скінченна,i
і q* = q [.f.];
@, коли T(A) – нескінченна.
Замінивши у (5) сімволи f, g, b, і p згідно зінтерпретацією I ми отримаємо програмноподібну структуру, рядки якої будемоназиваті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-1 даліінтерпретуються, як відповідні алгоритми (програми) iз класу прграм KП-1,функціонування яких подібно до функціонування програм, що написані на мовахпрограмування типу Паскаль, Бейсік і т. п.
А саме:
1) символ «=» у схемах (1) – (3) інтерпретуєтьсяяк оператор присвоєння;
2) елементи із Qs інтерпретуються аналогічно міткам вмовах програмування;
3) виконання команди qr x = y + 1 (ir, jr)інтерпретується як послідовність команд qr: x = y+1; go to ir;
4) виконання команди qr x = y -^1 (ir, jr)інтерпретується як послідовність команд qr: x = y-^1; go to ir;
5) виконання команди qr x = y (ir, jr)інтерпретується як послідовність команд qr: x = y; go to ir;
6) виконання команди qr x = 0 (ir, jr)інтерпретується як послідовність команд qr: x = 0; go to ir;
7) виконання команди qr P0 (x) (ir, jr) інтерпретуєтьсяяк умова qr: IF P0 (x) THEN go to ir ELSE go to jr.
Як і у більшості мов програмування, оператор «go to ir» прифункціонуванні програми передає управління на команду з міткою ir, а оператор «IFP0 (x) THEN go to ir ELSE go to jr» передає управлыння
на команду з міткою ir, якщо предикат P0 (x) =.t.(x = 0), і передає управління на команду з міткою jr, якщо предикат P0 (x)=.f. (x > 0).
В теорії алгоритмів вважається, що операторні SAта предикатні SP алгоритми із KS-1 виконуються на вхідних даних із Nабстрактними автоматамиом – багаторегістровими обчислювальними машинами (N-БРМ).Для кожного алгоритму А ця машіна Ба складається з блоку управління і mрегістрів, де кожний регістр (комірка) Rk може зберігати довілне натуральнечисло. Блок управління містить програму Па і забезпечує її виконання повищенаведеній схемі. Система команд N-БРМ складається з множини 0, x+1, x-^1,P0 (0), які можуть виконуватися над вмістом кожного Rk, а також командприсвоювання, безумовного і умовного переходу, пересилки і запису в регістр.
Часткові або всюдиозначенні k-арні функцію g: Nk –>N, яка задана на натуральних числах, або предикат P: E* –> T, F, будемоназивати рекурсивною функцією (предикатом), або R-функцією (R-предикатом), якщоіснує програма із класу КП-1 П1g, що обчислює g (P).
Приклади доведення по побудові рекурсивності функційнаведені у розділі VI данної інструкції.
Як відомо [1,2], згідно до тези Тюрінга-Черча, клас всіхR-функцій вважаються точним аналогом інтуїтивного поняття алгоритму (взагалікажучи, часткового).
3. Аналгічно до класів KS-1 схем алгоритміві¶нтерпретацій KI-1 введемо, відпвидно, класи KS-2 і KI-2.
Нехай E = a1., an – деякий алфавит. Через E*позначимо множину всіх слів в алфавібі E, включаючи однолітерні слова виду 'ai'і пусте слово e =''.
Введемо на E* деякі стандартні функції і предикати. Якщоw = x1x2..xm і v = y1y2..yk – слова iз E*, то
а) con (w, v) = wv = x1x2..xmy1y2..yk, con(e, v) =con (v, e) = v;
б) del(w) = d(w) = x2x3..xm, del(e) =e;
в) для всіх літер ai із E предикат hai(w) = T(істино), коли x1 = ai, і hai(w) = F (хибно), коли перша літераx1 у слові w не дорівнює ai (1 = i = m), причому для всіхi
hai(e) = F.
Якщо а – довільна літера із E*, то через (a^n)позначається слово, що склдається із n літер a.
Клас схем програм KS-2 містить (n + 1) унарнихфункціональних символів fa1, fa2., fan, g, один константний символ b і nунарних предикатних символів pa1, pa2., pan,
В класі інтерпретацій KI-2 схем із KS-1 множина D завждиспівпадає з множиною E* всіх слів в алфавіті E, а кожне відображення I із KI-2задовільняє наступним вимогам:
1) I(b) = е;
2) I (fai(x)) = con (I(x), 'ai')= I(x) aiдля всіх літер ai із E;
3) I (g(x)) = del (I(x));
4) I (pai(x)) = hai (I(x)) для всіх літер ai ізE;
5) I(xi) єE* для всіх вхідних змінних СОАі СПА виду (6), (7), і I(y) = e для всіх інших змінних із пам'ятівищезгаданих схем алгоритмів.
Замінивши у (5) сімволи fai, g, b і hai згідно зінтерпретацією I із класу KI-2 ми отримаємо програмноподібну структуру, рядкиякої будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-2далі інтерпретуються, як відповідні алгоритми (програми) iз класу прграм KП-2,функціонування яких подібно до функціонування програм, що написані на мовахпрограмування типу Паскаль, коли ці програми працюють на даних типу string.Ясно, що функціонуваня команд програм із класу КП-2 аналгічно, з точністю доінтерпретації символів її схеми, до функціонуваня команд програм із класу КП-1,яке було описано вище.
Зауважимо також, що по аналогії з N-БРМ БN можна ввестиE-БРМ БE, що реалізує програму із КП-2, а також NE-БРМ БNE. БNE можнарозглядати як «об'єднання» програм ПN i ПE для БN i БE в тому сенсі, що множинирегістрів БN i БE не перетинаються, але вони мають загальний блок управління (iспільні мітки), в якій поміщена спільна програма ПNE, в яку входять всікоманди, як із ПN так і із ПE.
Часткові або всюдиозначенні функцію g: E*вх –>E*вх,яка задана на множині слів довільного алфавіту E, або предикат P: E* –> T, F,будемо називати E – рекурсивною функцією (предикатом), або RE-функцією (RE-предикатом),якщо існує програма із класу КП-2 П1g, що обчислює g (P).
Як відомо [1], [2], за допомгою кодуючої функціїдоводиться, що, в певному сенсі, клас R-функцій (R-предикатів) і клас RE-функцій(RE-предикатів) є еквівалентні.
Приклади доведення по побудові RE-рекурсивності функційі предікатьв наведені далі.
Побудуємо алгоритм, що обчислює функцію
z:= f1 (x, y) = x + y.
x, y! z
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = x (q11, q11)
y1 = y (q12, q12)
z1 = 0 (q13, q13)
P0 (x1) (q16, q14)
z1 = z1 + 1 (q15, q15)
x1 = x1 -^ 1 (q13, q13)
P0 (y1) (q19, q17)
z1 = z1 + 1 (q18, q18)
y1 = y1 -^ 1 (q16, q16)
z = z1 (Я, Я)
Побудуємо алгоритм (не оптимальний), що заносить в zзначення функції добутку x i y, тобто z:= f1 (x, y) = x * y.
x, y! Z
q20
q21
q22
q23
x2 = x (q21, q21)
y2 = y (q22, q22)
z2 = 0 (q23, q23)
P0 (y2) (q25, q10)
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = z2 (q11, q11)
y1 = x (q12, q12)
z1 = 0 (q13, q13)
P0 (x1) (q16, q14)
z1 = z1 + 1 (q15, q15)
x1 = x1 -^ 1 (q13, q13)
P0 (y1) (q19, q17)
z1 = z1 + 1 (q18, q18)
y1 = y1 -^ 1 (q16, q16)
z2 = z1 (q24, q24)
q24
q25
z2 = z1 (q23, q23)
z = z2 (Я, Я)
Нехай алфавіт Е = a, b. Побудуємо алгоритм, щообчислює предикат Pe(w), де Pe(w) = T тоді і тільки тоді, коли w є пустеслово із E*, тобто w = e.
x! q [.t.], q [.f.]
q10 x1 = x (q11, q11)
q11 ha(x1) (q [.f.], q12)
q12 hb(x1) (q [.f.], q [.t.])
Побудуємо алгоритм (не оптимальний), що заносить в zзначення функції con (x, y) = xy, тобто z:= g1 (x, y) = con(x, y) = = xy для слів із Е = a, b.
x, y! Z
q20
q21
q22
x2 = x (q21, q21)
y2 = y (q22, q22)
z2 = e (q10, q10)
q10
q11
q12
x1 = y2 (q11, q11)
ha(x1) (q22, q12)
hb(x1) (q22, q28)
q22
q23
q24
ha(y2) (q23, q25)
x2 = con (x2, a) (q24, q24)
y2 = del(y2) (q22, q22)
q25
q26
q27
q28
hb(y2) (q26, q10)
x2 = con (x2, b) (q27, q27)
y2 = del(y2) (q25, q25)
z = x2 (Я, Я)
4. Операторні тапредикатні алгоритми -ІІ
(Рекурсивніфункції на областях, що відмінні від N)
ОскількиБРМ працює тільки з натуральними числами, наше визначення обчислюваності іможливості розв'язання застосовано тільки до функцій і предикатів віднатуральних чисел. Ці поняття легко поширюються на інші види об'єктів (тобтоцілі числа, поліноми, матриці і т.д.) за допомогою кодування.
Кодуванням області Dоб'єктів називається явне й ефективне відображення α: D →N. Мибудемо говорити, що об'єкт α € D кодується натуральнимчислом α (d). Припустимо, що f є функцією з D в D; тоді f природнокодується функцією f* з N в N, що відображає код кожного об'єкта d €Dom(f) у код об'єкта f (d). У явному виді це можна записати як
f*=α· f ·a-1
Теперможна поширити визначення Мнр-обчислюваності на область D, рахуючи функцію fобчислюваною, якщо f*–обчислювана функція натуральних чисел.
Приклад. Розглянемообласть Z. Явне кодування можна задати функцією α, де
/>2n, якщо n ³ 0,
α-(n)=
-2n-1,якщо n
Тодіα-1 задається так:
/>(1/2) m, якщо m парне,
α-1(m) =
(-1/2)(m+1), якщо m непарне.
Теперрозглянемо функцію х-1 на Z; позначаючи цю функ-ючерез f,одержуємо f*:N →N, що задається:
/>1, якщо x:==0 (тобтох=α(0)),
f*(x)=х-2,якщох>і х парне (тобто х=а(п), п>0),
х +2, якщо хнепарне (тобто х=α(n), п
Написанняпрограми, що обчислює f*, є рутинною вправою; отже, х-1 єобчислювана функція на Z.
Приведеневище визначення очевидним образом розширюється на n-місцеві обчислювальніфункції на області D і розв'язні предикати на D.
5.Алгоритмічні проблеми для L
Нижчедається огляд нерозв'язних проблем, що виникають у самій теоріїобчислювальності, і обговорюються деякі методи доказу нерозв'язності. Нагадаємо,що предикат М(х) називається розв'язним, якщо йогохарактеристична функція, що задається формулою
/>1, якщо M(x) правдиве,
Cm(x) =
0, якщоM(x) неправдиве
обчислювана.Це рівносильно твердженню про те, що предикат М (х) рекурсивний ПредикатМ (х) називається нерозв'язним, якщо він не є розв'язним. Улітературі використовуються наступні терміни, еквівалентні твердженню про те,що предикат М (х) розв'язний:
М(х) рекурсивний,
М(х) має рекурсивну проблему дозволу,
М(х) рекурсивно розв'язний,
М(х) обчислювальний.
Алгоритм,що обчислює см, називаєтьсяобчислювальною процедурою, дляM(x).
1.Нерозв'язні проблеми в теорії обчислюваності
Убільшості випадків докази нерозв'язності ґрунтуються на діагональному методі,як, наприклад, у наступному важливому прикладі.
1.1.Теорема. Проблема «x ÎWx»(чи, що еквівалентно, «функція fx(х) визначена»,чи «Рx(х)¯», чи «функціяyu(х, х)визначена»)нерозв'язна.
Доведення. Характеристичнафункція цієї проблеми задається наступною формулою:
/>1, якщо xÎ Wx
f(x)=0,якщо xÏ Wx
Припустимо,що функція f обчислювана, і приведемо це припущення до протиріччя. Саме задопомогою діагонального методу ми побудуємо обчислювану функцію g,таку, що Dom(g)¹Wx(= Dom(фx)), привсіх х, чого, мабуть, бути не може.
Якзавжди при використанні діагонального методу, ми будемо прагнути до того, щобмножина Dom(g) відрізнялося від Wx у njxці х. Тому будемодомагатися того, щоб
x Î Dom (g)Ûx ÏWx
Визначимотепер функцію g у такий спосіб:
g(x)= 0, якщо xÏ Wx (тобтоякщо f(x)=0),
невизначена, якщо xÎ Wx (тобто якщо f(x)=1).
Оскількифункція f обчислювана, то (по тезі Черча) обчислювана і функція g, що ідає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана,візьмемо таке т, що g=fm, тоді т Î WmÛ т Î Dom (g)Ûт Ï Wm,чого не може бути.)
Отже,ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x ÎWx» нерозв'язна. ÿ
Зауважимо,що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретногочисла а сказати, чи буде визначене значення fa (a). Длядеяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, щообчислює тотальну функцію, і Р=Рa, то ми відразу знаємо,що значення fa (a) визначено.Теорема говорить лише, що не існує єдиного загального методу рішенняпитання про те, чи буде fx(х) визначено;іншими словами, не існує методу, що працює при всіх х.
Простийнаслідок цього результату полягає в наступному.
1.2.Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x ÎDom(h)» і «х ÎRan(h)» нерозв'язні.
Доведення. Покладемо
/>x, якщо xÎ Wx
h(x)=
не визначена, якщо xÏ Wx
Тодів силу тези Черча і обчислюваності універсальної функції yu функція hобчислювана (більш формально ми маємо h(x)@ x1 (yu(х, х)), аця функція обчислювана як результат підстановки). Ясно, що x Î Dom(h)Û xÎ WxÛx Î Ran (h), так що обидвіпроблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні.
Зтеореми 1.1 виводиться ще одна важлива нерозв'язна проблема:
1.3.Теорема (проблема зупинки). Проблема «функція фx(у)визначена» (чи в еквівалентній формі «Рx(y)¯, чи «y ÎWx» нерозв'язна.
Доведення. Міркуючинеформально, ми відразу бачимо, що якби проблема «функція фx(у)визначена» була б розв'язна, то була б розв'язна і більш проста проблема «функціяфx(х) визначена», що суперечить теоремі 1.1.
Щобпровести всі ці міркування більш докладно, розглянемо характеристичну функціюпроблеми^ «функція фх(у) визначена», що має наступний вид:
/>1, якщо фх(у)визначена
g (x,y)=
0, якщо фх(у) невизначена
Якбифункція g була обчислювана, то обчислюваною була б і функція f(x)=g(x, х), але f є характеристична функція проблеми «х Î Wx»і, отже, не обчислювана в силу теореми 1.1. Отже, функція g необчислювана, і тим самим проблема «фx(y) визначена» нерозв'язна.ÿ
Теорему1.3 часто інтерпретують як твердження про нерозв'язність проблеми зупинки (дляМНР-программ), у якому говориться про те, що не існує ніякого ефективногозагального методу установити, чи зупиниться деяка конкретна програма, запущенапісля введення в неї деякого конкретного набору початкових даних. Зміст цьоготвердження для теоретичного програмування очевидний: не існує зовсім загальногометоду перевірки програм на наявність у них нескінченних циклів.
Розглянутав теоремі 1.1 нерозв'язна проблема «х Î Wx»важлива з кількох причин. Одна з них полягає в тому, що нерозв'язність багатьохпроблем можна довести, показавши, що вони принаймні не простіші, ніж ця. Саметаким шляхом ми довели, що проблема зупинки (теорема 1.3) нерозв'язна: цейпроцес називається зведенням однієї проблеми до іншої.
Узагалірозглянемо деяку проблему М (х). Часто вдається показати, що рішеннязагальної проблеми М (х) привело б до рішення загальної проблеми «хÎ Wx», Тоді говорять, щопроблема «х Î Wx» зводитьсядо проблеми М (х). Іншими словами, якщо мається дозволяюча процедура дляпроблемиМ (x), то ми можемо дати і дозволяючу процедуру для проблеми«х Î Wx».Таким чином, з можливості розв'язання М(х) випливає можливістьрозв'язання «х Î Wx»,звідки ми негайно робимо висновок, що М (х) нерозв'язна.
Длязведення проблеми «х Î Wx»до інших проблем часто використовується s-m-n-теорема, як показує, наприклад,доведення наступного результату.
1.4.Теорема. Проблема «фx=0» нерозв'язна.
Доведення. Розглянемо функціюf, визначену формулою
/>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.Покажіть, що наступні проблеми нерозв'язні.
(a) «х ÎЕх «. (Указівка.Скористайтеся діагональним методом чи зведіть до цієї проблеми проблему
«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, визначається втакий спосіб:
(a) якщо Ii=Z(n), тo ti, є твердження
"x1 … "xu: R(x1, …, xn, …, xu, i)®R (x1,…, O, …, xu, i ¢)
(b) якщо 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) відповідає вихідному стану
а …;
наступна команда 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]*.