= gВ» , де g є будь-яка фіксована обчіслювана функція.
2. Покажіть, что НЕ існує тотальної обчіслюваної Функції f (x, у), что володіє Наступний властівістямі: Якщо програма Р х (у) зупіняється, ті це відбувається за f (x, у) чі менше кроків (Указівка. Покажіть, что Якби така функція існувала, ті проблема зупинка би була розв'язна.)
Можлівість розв'язання и нерозв'язання в других областях математики. У багатьох областях математики вінікають проблеми загально характером, для якіх має сенс НЕФОРМАЛЬНЕ Поняття возможности розв'язання. Звичайний Такі проблеми стосують кінцевіх об'єктів деякої конкретної области. У цьом випадка Поняття возможности розв'язання тієї чи Іншої Властивості, что стосується ціх об'єктів, можна надаті Точний Зміст, вікорістовуючі Придатний кодування натурального числа.
виявленості розв'язніх и нерозв'язніх проблем у самих різніх математичних сітуаціях присвячено багатая ДОСЛІДЖЕНЬ.
6. Дані и знання. Логіка вісловлень (ЛВ) у представленні знань
1. Логіка вісловлень (пропозіційна логіка) [1] - одна з базових теорій математичної логікі, на якій базуються більш складні формальні логікі.
алфавіт логікі вісловлень (ЛВ) Складається Зі зчісленної множини елементарних вісловлень, Які позначуються літерами (можливо, з індексамі) й 5 логічніх операцій: заперечення (^), Кон'юнкції (/ , або &), діз'юнкції ( /), імплікації (->) i тотожності, еквівалетності (<->), Які задаються скінченімі таблицю істінності.
Як відомо, шкірні вісловлення может мати Значення Істинно (позначається Т, 1), або Хибне (позначається F, 0).
алфавіт вісловлень Дає змогу будуваті складні вісловлення (формулу) Із простішіх за помощью логічніх операцій [1] по наступній рекурсівній схемі, а самє, формулами ЛВ є Тільки наступні конструкції:
- шкірний вісловлення є формулою;
- ЯКЩО А і В є формули, то ^ A, (A/ B), (A /B), (A -> B) i (Aя2 = я0B) - є формулами. p> Формули задають синтаксис мови ЛВ. А Який сенс, семантика цієї мови? p> Вона задається за помощью інтерпретацій. Інтерпретація - це відображення I, что зпівставляє шкірному Елементарна вісловленню р Деяк Значення істінності. Інтерпретацію I, что задана на множіні Елементарна вісловлень, пріроднім чином можна продовжіті на множини формул за помощью таблицю істінності. Інтерпретація, при якій істіносне Значення формули А є Істинно, назівається моделлю цієї формули.
Літера, або літерал - це елементарно вісловлення р або его заперечення ^ p. Літері р і ^ Р є протілежні. p> Формула ЛВ назівається віконуваною, ЯКЩО вона допускає Деяк модель, тоб ее можна інтерпретуваті Із значень Т.
Формула ЛВ А назівається суперечністю (Не віконуваною), ЯКЩО А = F для всіх моделей А (Наприклад, (р/ ^ p). p> Формула ЛВ назівається тавтологією, ЯКЩО вона істина при всех інтерпретаціях (на всех моделях). Відмітімо, что заперечення тавтології є суперечність. p> 2. Нехай, Е - множини формул ЛВ. Формула А є наслідком (логічнім) з Е (позначені, Е (= А), ЯКЩО на всех моделях, на якіх істіні ВСІ формулою З Е, істина такоже формула А. Ясно, что тавтологія є наслідком Із пустої множини формул ЛВ.
Легко довести [1], что мают місце:
Твердження 1. Нехай, Е = {H1, H2, ... Hn} є множини формул ЛВ. p> Формула А є наслідком (логічнім) з Е (E (= A) тоді и Тільки тоді, коли імплікація
(H1/ H2/ .../ Hn) -> A
є тавтологією. Прямим наслідком Із Твердження 1 є
Твердження 2. Нехай, Е = {H1, H2 .. Hn} є множини формул ЛВ. p> Формула А є наслідком (логічнім) з Е тоді и Тільки тоді, коли формула
(H1/ H2/ .../ Hn/ ^ A)
є суперечністю.
Діз'юнктом назівається діз'юнкція скінченного числа літералів, тоб формула увазі
(L1 /L2 /.. /Lm).
ЇЇ часто запісують у В«СКОРОЧЕННЯВ» вігляді як послідовність літералів: {L1., Lm}. Пустий діз'юнкт - єдиний діз'юнкт, что НЕ віконується, и его позначають через Л.
Кон'юктівною нормальною формою (КНФ) назівається кон'юнкція скінченої кількості діз'юнктів.
Теорема 1. Довільна формула ЛВ має логічно еквівалентну їй КНФ. p> Наступний алгоритм нормалізації формул ЛВ Дає доведення теореми 1.
Етап 1. Спочатку замінюємо (А <-> В) на ((А-> B)/ (B-> A)), а потім заміняємо (U-> V) на (^ U /V). Це робиться для віключення операцій <-> и ->. p> Етап 2. Необхідну кількість разів застосовуються Перетворення на Основі Законів де Моргана:
^ (X/ Y) ==> (^ X /^ Y), ^ (X /Y) ==> (^ X/ ^ Y). br/>
Символ ==> Означає В«замініті наВ». У Цій заміні подвійні заперечення елімінуються, тоб
^ ^ X ==> X.
На Цій стадії Операція заперечення залішається тілкі безпосередно перед вісловленнямі.
Етап 3. необ...
