Головна |
Введемо позначення: F (x1, x2, ..., Xn) - Формула ІВ, x1, x2, ..., Xn - Список попарно різних пере-х, серед кіт. є все пере-е, що входять до ф-лу F. нехай s =
F?=
Пр-р: Нехай F = x1®x3; s = <0, 1, 1>, тоді. т. к. 0®1 = 1 .. Якщо s = <1, 0, 0>, то
, Т. К. 1®0 = 0.
Лемма (про виводимості). для люб. ф-ли F (x1, x2, ..., Xn) І люб. набору s справ-верба виводимість: x1s, х2s, ..., Хns Fs(x1, x2, ..., Xn). дано: Г = {x1s, х2s... Хns}. потрібно док-ть, що Г Fs. док-во проведемо м. м. і. по довжині ф-ли F (числу логічних зв'язок k, що входять до запису ф-ли). базис: k = 0; F = xi. потрібно док-ть: x1s, х2s, ... Xis, ..., Хns Fs= xis - Слід-т по св-ву 1 ° висновок-сти з гіпотез. нехай для люб. ф-ли довжини 0
Довести: Г Fs.Можливі 2 подслучая:
№ | F1 | F1? | F | F? |
a | F | |||
b | F1 |
1 подслучай: а) Дано: Г F1s=.
Док-ть: Г Fs= F =. то, що потрібно док-ть - дано.2 подслучай: б) Знач-е F1 на s дорівнює 1.
Дано: Г F1s= F1.
Док-ть: Г.
Необхідну след-т по з-ну введення дв. заперечення. р! 2-й випадок: F = F1 F2. по індукційному припущенням лема вважається вірною для ф-л F1 і F2. Тут можл. 4 подслучая:
F1 | F2 | F1? | |
a | |||
b | |||
c | F1 | ||
d | F1 | ||
F2? | F | F? | |
A | F | ||
b | F2 | F | |
c | |||
d | F2 | F |
У кожному з подслучаев запишемо, що дано і що потрібно док-ть.
а) Дано: Г, Г Док-ть:
Г F1®F2.1) Г дано. 2) Г, з 1) по 2 °. 3) Г, F1 F2 з 2) по О. к. 4) Г F1®F2 з 3) по ТД. б) Дано: Г, Г F2. Док-ть: Г F1®F2. Док-во збігається з попер. випадком. 1) Г дано 2) Г, з 1) по 2 °. 3) Г, F1 F2 з 2) по О. к. 4) Г F1®F2 з 3) по ТД.
в) Дано: Г F1, Г F2, Док-ть: Г. інакше, потрібно до-ть: Г, F1,. док-во:
1) Г, F1, F1®F2 F2 МР до ??списку гіпотез. 2) Г, F1, з 1) по П. к. 3) Г F1 -Даний. 4) Г, з 3), 4) по 3 ° .5) Г -Даний. 6) Г з 4), 5) по 3 °. г) Дано: Г F1, Г F2.
Док-ть: Г F1®F2. док-во: 1) Г F2 дано 2) Г, F1 F2 з 1) по 2 °
Г F1®F2 . з 2) по ТД.
Т. о., Лема справедлива для люб. ф-ли F.
13. Інтерпретація ІВ. Несуперечливість ІВ.(Зв'язок ІВ з АВ) Пропозіціональние перем-е б. тлумачити як Виска-я, кіт. приймають знач-я з мн-ва {0, 1}, логічні зв'язки ®, O б. тлумачити як операції над Виска-ми, визначені тими самими таблицями істинності, що і А ®,. опр. Ф-ла ІВ наз-ся тавтологією або т. І. ф., якщо на люб. наборі знач-й пере-х вона приймає значення 1 (істина). лема 1. Всі аксіоми ІВ є тавтологія. перевіримо аксіому А1: А® (В®А). Побудуємо таблицю істинності:
А | > | (В | > | А) |
Також перевіряються інші аксіоми. лема 2. Правило виводу МР зберігає тавтологічні ф-ли, т. е., якщо А і А ® - тавтології, то В - тавтологія. док-во (методом від противного): Припустимо, що В не явл-ся тавтологією, т. е. сущ-т набір значень пере-х, на кіт. знач-е ф-ли В дорівнює 0 (брехня), т. к. А - тавтологія, то імплікація А ® на наборі (1,0) помилкова, т. к. В - помилкова по допущенню, що суперечить умові А® В - тавтологія. След-но, ф-Ула В - тавтологія.
Звідси слід. теореми: Т1. Якщо формула ІВ виведена, то вона є тавтологією.
А А - Т. і. ф. док-во проведемо м. м. і. дано: ф-ла А - виведена з аксіом в ІВ, т. е. існує її висновок: F1, F2, ..., Fn= А - висновок А. покажемо що будь-яка ф-ла виведення явл-ся ТИФ. Індукцію б. проводити по довжині виведення ф-ли А. побудова базису. Нехай n = 1.F1 - Аксіома (по лемі 1 - вона тавтологія). індукційний крок. Нехай док-но, що для "nIN, 1
Для ф-ли Fk можливі випадки:
а) Fk - аксіома Fk - тавтологія по лемі 1. б) Fk отримана за правилом МР з Fi і Fj (i, j След-но, теорема справедлива "nIN. След-е: Якщо ф-Ула НЕ тавтологія, то вона в ІВ не виводиться. Опр. ІВ наз-ся несуперечливим, якщо не ім-т ф-ли А такий, що одночасно в цьому ІВ виведена вона сама і її заперечення, т. е. А та. зауваження: вимога несуперечності - найважливіша вимога до мат. теорії. Т2. Обчислення Виска-й несуперечливо. док-во: Припустимо противне. Нехай ІВ - суперечливо, т. Е. Сущ-т ф-ла А така, що А і. Т. к. А, то по Т1 вона є тавтологією, але тоді тавтологією явл-ся і тому вона виведеної бути не може. Приходимо до протиріччя. Якщо ф-ла виведена, то вона тавтологія 12. З-ни прямого і зворотного контрапозиции в обчисленні вис-й. Наступ. кроком на шляху побудови формалізованого исчисл-я виского-й явл-ся виявляючи-е подальших закономірностей процесу виведення одних ф-л з ін. і формулювання таких закономірний-й у вигляді правил виведення. Отримувані вторинні правила виведення носять назви похідних правил виведення (вторинних). ці правила наз-ся правилами видалення або введення лог. зв'язок. Введемо нові лог. символи в якості скорочення недо. Ф-л: B A B -сокращ-е диз-цією -сокращ-е кон-єю Похідні правила виведення: 1. ст. >: 2. уд. >: 3. ст. : 4. уд. : 5. О. к .: 6. П. к .: 7. ст. &: 8. уд. &: Г, А & В А | Г, А & В В 9. ст. : Г, а А В | Г, В А В 10. уд. : 5) 1) Г, дано 2) > (А > В) (А3) 3) Г, а > (А > В) з 2) по 2 ° 4) Г з 1) по ТД 5) Г, А з 4) по 2 ° 6) Г, А з 3), 5) по МР 7) Г, А по 1 ° 8) Г, А з 6), 7) по МР. 6) 1) Г, А В дано 2) В ст. OO 3) Г, А з 1), 2) по 4? 4) Г, А, з 3) по 2 ° 5) Г, А уд. OO 6) Г, з 4), 5) по 3 ° 7) Г, з 6) по обрат. контр. 11 .. правила введення і видалення подвійного заперечення в обчисленні вис-й. Наступ. кроком на шляху побудови формалізованого исчисл-я виского-й явл-ся виявляючи-е подальших закономірностей процесу виведення одних ф-л з ін. і формулювання таких закономірний-й у вигляді правил виведення. Отримувані вторинні правила виведення носять назви похідних правил виведення (вторинних). ці правила наз-ся правилами видалення або введення лог. зв'язок. Введемо нові лог. символи в якості скорочення недо. Ф-л: B A B -сокращ-е диз-цією -сокращ-е кон-єю Похідні правила виведення: 1. ст. >: 2. уд. >: 3. ст. : 4. уд. : 5. О. к .: 6. П. к .: 7. ст. &: 8. уд. &: Г, А & В А | Г, А & В В 9. ст. : Г, а А В | Г, В А В 10. уд. : Док-во: 3) 1) Г А дано 2) А > приклад 5 3) Г А > з 2) по 2 ° 4) Г з 1), 3) по МР. 4) 1) Г дано 2) > А приклад 4 3) Г > А з 2) по 2 ° 4) Г А з 1), 3) по МР. 10. правила введення і видалення диз'юнкцій обчисленні вис-й. Наступ. кроком на шляху побудови формалізованого исчисл-я виского-й явл-ся виявляючи-е подальших закономірностей процесу виведення одних ф-л з ін. і формулювання таких закономірний-й у вигляді правил виведення. Отримувані вторинні правила виведення носять назви похідних правил виведення (вторинних). ці правила наз-ся правилами видалення або введення лог. зв'язок. Введемо нові лог. символи в якості скорочення недо. Ф-л: B A B -сокращ-е диз-цією -сокращ-е кон-єю Похідні правила виведення: 1. ст. >: 2. уд. >: 3. ст. : 4. уд. : 5. О. к .: 6. П. к .: 7. ст. &: 8. уд. &: Г, А & В А | Г, А & В В 9. ст. : Г, а А В | Г, В А В 10. уд. : Док-во: 9) Аналіз док-ва: Г, А А В; Г, а > В; Г, А, В; Г,,. Док-во: 1) Г,,. по 1?. 2) Г, А, В О. к. 3) Г, а > В Т. д. 4) Г, А А В скор. -ів. 10) Аналіз док-ва: Г, А В С; Г, > В С; Г,; Док-во: 1) дано. 2) дано 3) Г, П. к. 1). 4) Г, П. к. 2). 5) Г, & з 3), 4) -вв. & 6) Г, - Розшифруйте. & Продовження аналізу: ; ; ,; , Продовж-е док-ва: 7), МР до ??списку гіпотез 8), ст. 9) ТД 10) П. к. 11) Г, з 6), 10) по 4? 12) Г, > В С - О. к. 13) Г, а В С з 12) по скор. -ів. 9. правила введення і видалення кон'юнкції в обчисленні вис-й. Наступ. кроком на шляху побудови формалізованого исчисл-я виского-й явл-ся виявляючи-е подальших закономірностей процесу виведення одних ф-л з ін. і формулювання таких закономірний-й у вигляді правил виведення. Отримувані вторинні правила виведення носять назви похідних правил виведення (вторинних). ці правила наз-ся правилами видалення або введення лог. зв'язок. Введемо нові лог. символи в якості скорочення недо. Ф-л: B A B -сокращ-е диз-цією -сокращ-е кон-єю Похідні правила виведення: 1. ст. >: 2. уд. >: 3. ст. : 4. уд. : 5. О. к .: 6. П. к .: 7. ст. &: 8. уд. &: Г, А & В А | Г, А & В В 9. ст. : Г, а А В | Г, В А В 10. уд. : Док-во: 7) Аналіз док-ва: Г А & В, Г, Г, А,, Г, А, А >. Док-во: 1) Г (дано). 2) Р О (дано). 3) Г, А, В, А > МР до ??списку гіпотез. 4) Г, А, В,, П. к. 5) Г, А, В - ст. 6) Г, А, В з 4), 5) по 3?. 7) Г, В з 1), 6) За 3?. 8) Г з 2), 7) по 3?.9) Г. з 8 скор. & - їй. 8) Г, А & В А Аналіз док-ва: Г, А & В А; Г,; Г,; Г, А >; Г,, А; Г, в, а А. Док-во: 1) Г, в, а А по 1?. 2) Г, А П. к. 3) Г, А >. 4) Г, П. к. 5). Г, А уд. 6). г, А & В А сокращ. & - їй. 8. Теорема дедукції(Довів угорський математик Ербрана). Ця теорема дозволяє спростити багато док-ва. т. Якщо Г, А В, то Г А ®. Суть теореми закл-ся в слід .: якщо з посилок А (мн-во гіпотез Г м. Б. Порожнім) виводиться за правилами логіки недо. висновок У, то імплікація А ® доказова, т. е. виводиться вже без всяких посилок, з одних аксіом, кіт. явл-ся логічно істинними пропозиціями. В процесі док-ва теорема дозволяє вводити допущення, а потім звільнятися від них. дано: дано висновок ф-Ули В з Г, А .: (1) F1, F2, ..., Fn= B. док-ть: ф-ла ® У виведена з мн-ва гіпотез Г. док-во: Побудуємо допоміжну послід-ть ф-л: (2) А®F1, а®F2, ..., А®Fn= А®B. Вона закінчується потрібної нам ф-лій. Док-м, що доповнивши послід-ть (2) некіт. придатними ф-лами, ми зможемо отримати з неї шуканий висновок. док-во б. проводити М. м. і. по довжині виведення n ф-ли В. I. Побудова базису мат. індукції. нехай n = 1. дано: Г, А В, довжина виводу ф-ли В дорівнює 1, т. е. F1= В. до-ть: виведена ф-ла А®F1 (Г А®F1). можливі випадки: F1 явл-ся або аксіомою, або гіпотезою з Г, або збігається з А. Р! -м їх. (Для визна-ти знак висновок-ти будемо опускати) .1) F1 - Аксіома. Потрібно пів-ть: Г А®F1. Побудуємо висновок: 1.F1аксіома 2.F1® (А®F1) (А1) .3. а®F1, МР до ??1, 2. У послід-ть (2) слід записати перед А®F1 формули 1 і 2.2) F1 - Гіпотеза зі списку Г.1. F1-гіпотеза, 2. F1® (А®F1) (А1) 3. А®F1 МР до ??1, 2. Висновок аналогічний предидущему.3) F1 збігається з А. Треба док-: Г А®А. Висновок ф-ли А®А побудований (див. Приклад 1 - 5 ф-л). За св-ву 2 ° м. Записати Г А®А. при n = 1 теорема справедлива. II. Індуктивний крок. предпол-м, що теорема дедукції вірна для люб. n 1. Fk - аксіома. 2.Fk-гіпотеза з Г.3.Fk збігається з А.4.Fk виходить з двох попередніх формул Fi і Fj за правилом (МР). перші три випадки збігаються з пред.1. Fk -гіпотеза.2. Fk® (А®Fk) (А1) 3. А®Fk, МР до ??1, 2. в остан-ть (2) слід записати перед А®F1 формули 1 і 2. Будемо для визначеності вважати, що Fi - мала посилка, Fj - велика посилка. Отже, Fj = Fi®Fk. Запишемо остан-ть ф-л: А2: А® (В®С) ® ((А ®) ® (А®С)). Зробимо переобозначеніе пере-х: В на Fi, С на Fk 1. А® (Fi ® Fk) ® ((А® Fi) ® (А®Fk)) (А2) 2. А® (Fi ® Fk) = А® Fj за припущенням: т. К. J 3. (А® Fi) ® (А®Fk) МР до ??1, 2. 4. А® Fi за припущенням: т. К. I 5. А®Fk МР до ??3, 4. В остан-сть (2) слід-т вставити ф-ли 1 і 3, а інші в ній вже є. За принципом математичної індукції теорема справедлива для будь-якого натурального n: Г А®Fn = А®B. повнота ІВ | Висновок формул з гіпотез
Поняття про елементарні теоріях. | Побудова числення предикатів: алфавіт, формула, аксіоми. Правила виведення, опр. Виведення формули та виведення з гіпотез в ВП. Теорема ЛП. Несуперечливість ВП. | Попереджання нормальна форма (ПНФ), її знаходження. | Метод Генцен для вирішення проблеми виконуваності формул логіки предикатів. | протиріччя | Проблеми здійсненності, общезначимости в тотожною хибності формул логіки предикатів. Зв'язок між цими проблемами. Т. Черча (без док-ва). | Поняття моделі даної сигнатури і істинності формули на моделі. | Приклади запису математичних пропозицій формулами логіки предикатів | Способи завдання предикатів | квантори |