Головна

Лемма про повноту ІВ

  1. Глава 34. Вирішальна дилема
  2. Лемма Больцано-Вейєрштрасса.
  3. Лемма про вкладені проміжках
  4. Поняття про повноту системи булевих функцій
  5. Теорема Дедекинда про повноту R
  6. трілемми

Введемо позначення: F (x1, x2, ..., Xn) - Формула ІВ, x1, x2, ..., Xn - Список попарно різних пере-х, серед кіт. є все пере-е, що входять до ф-лу F. нехай s = - упорядкований набір довжини n з 0 і 1: giI {0, 1},.

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 1 F2, F1 і F2 мають довжину менше, ніж s і для них твердження леми вип-ся, т. е. Г F1s, Г F2s. Потрібно док-ть: Г Fs.1) Розглянемо 1-й випадок:. дано: Г F1s.

Довести: Г 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 n явл-ться тавтологією. док-м, що при n = k - Fk тавтологія.

Для ф-ли 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.

повнота ІВ | Висновок формул з гіпотез


Поняття про елементарні теоріях. | Побудова числення предикатів: алфавіт, формула, аксіоми. Правила виведення, опр. Виведення формули та виведення з гіпотез в ВП. Теорема ЛП. Несуперечливість ВП. | Попереджання нормальна форма (ПНФ), її знаходження. | Метод Генцен для вирішення проблеми виконуваності формул логіки предикатів. | протиріччя | Проблеми здійсненності, общезначимости в тотожною хибності формул логіки предикатів. Зв'язок між цими проблемами. Т. Черча (без док-ва). | Поняття моделі даної сигнатури і істинності формули на моделі. | Приклади запису математичних пропозицій формулами логіки предикатів | Способи завдання предикатів | квантори |

© 2016-2022  um.co.ua - учбові матеріали та реферати