• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Повнота і несуперечність теорії L

Допоміжні правила виведення в теорії L.

Наслідок 2.

1. гіпотеза

2. гіпотеза

3. гіпотеза

4. по m.p. з 1, 3

5. С по m.p. з 2, 4

За теоремою дедукції .

Теорема дедукції (обернена). Нехай Г – деяка множина формул (гіпотез) теорії L. А, В – деякі формули теорії L. Якщо , то .

Доведення:

, тобто з Г формули , де .

Отримали, що . Що і треба було.

Лема. Для будь-яких формул А, В наступні формули є теоремами теорії L:

а)

Доведення:

(А3)

1. (А3)

2. Лема 1

3. наслідок 2 з 1, 2

4. (А1)

5. наслідок 1 з 3, 4

b)

1.

2. (а)

3. m.p.1, 2

4. (А1)

5. наслідок 1 з 3, 4

c)

1. гіпотеза

2. А гіпотеза

3. (А1)

4. (А1)

5. m.p.1, 3

6. (А3)

7. m.p. 5, 6

8. m.p. 2, 4

9. В m.p. 7, 8

,

За теоремою дедукції

За теоремою дедукції

d)

1. гіпотеза

2. А гіпотеза

3. (А3)

4. (А1)

5. m.p. 1, 3

6. наслідок 1 з 4, 5

7. В m.p. 2, 6

,

За теоремою дедукції

Ще раз застосуємо теорему дедукції

e)

1. гіпотеза

2. (а)

3. наслідок 1 з 1, 2

4. (b)

5. наслідок 1 з 3, 4

6. (d)

7. по m.p. 5, 6

За теоремою дедукції

f)

m.p.

Теорема дедукції

Теорема дедукції

(е)

наслідок 1 з теореми дедукції

(g)

1. гіпотеза

2. гіпотеза

3. (е)

4. m.p. 1, 3

5. (е)

6. m.p. 2, 5

7. (А3)

8. m.p. 6, 7

9. В m.p. 4, 8

Теорема дедукції

Теорема дедукції

Доведемо декілька тверджень, які будуть корисними при рішенні задач.

1. Правило контрапозиції.

Якщо , то .

Доведення:

1. за умовою

2. т.д. 1

3. (е)

4. (γ) 2,3

5. т.д. (обр.) 4

2. Правило введення кон’юнкції.

Доведення:

1. А гіп.

2. В гіп.

3. ЛП2

4. m.p. 2, 3

5. ЛП6

6. наслідок 2 т.д.

7. m.p. 1, 6

3. Правило видалення кон’юнкції.

Доведення:

Покажемо, що .

1. (с)

2. т.д. (обр.) 1

3. пр.І, 2

4. (а)

5. властивість (γ) 3,4

Покажемо, що .

1. (А1)

2. т.д. (обр.)

3. пр.І, 2

4. (а)

5. властивість (γ) 3,4

4. Правило введення диз’юнкції.

Доведення:

1. (с)

2. т.д. (обр.) 1

3. (в)

4. властивість (γ) 2, 3

1. (А1)

2. т.д. (обр.) 1

5. Правило видалення диз’юнкції.

Якщо , , то .

Доведемо правило видалення диз’юнкції.

1. за умовою

2. пр.І, 1

3. за умовою

4. пр.І, 3

5. введення &, 2,4 + властивість (γ)

6. пр.І, 5

7. (а)

8. властивість (γ) 6,7

9. (в), властивість (γ) 8

10. наслідок 1

11. властивість (γ) 9,10

Покажемо, що формула теорії L тоді і тільки тоді є теоремою цієї теорії, коли вона є тавтологією.

Твердження 1. Кожна теорема теорії L є тавтологія.

Доведення:

Неважко переконатися в тому, що кожна аксіома теорії L є тавтологія.

Наприклад, (А1):

Нами доведена Лемма 1 про тавтології: якщо А і (А ⊃ В) - тавтології, то В - тавтологія. Значить, правило modus ponens, застосоване до тавтології, призводить до тавтології. Отже, будь-яка теорема теорії L є тавтологія.

Для доказу того, що кожна тавтологія є теорема теорії L нам буде потрібно наступна лема.

Лема про штрихи. Нехай А - формула теорії L, до запису якої входять пропозіціональние букви В₁, В₂, ..., В_к. Нехай задано деякий розподіл істинних значень для В₁, В₂, ..., В_к. Нехай тоді

Нехай

Тоді , , …, ⊢ (*)

Приклад.Нехай А – це формула :

Істинна таблиця:

Для кожного рядка цієї таблиці лема про штрихи стверджує факт відповідної виводимості.

Першому рядку відповідає твердження:

1 рядок

2 рядок (так, )

3 рядок

4 рядок

Доведення:

Доведення проведемо за індукцією по числу l примітивних зв’язок (¬,⊢), за допомогою яких записана формула А.

1. Базис індукції. L=0. Тоді формула А представляє собою пропозиційну літеру В₁.

(*): , тобто стверджується, що - це так (Лема 1: ).

2. Індуктивне припущення: нехай твердження (*) істинне для будь-якого l<k.

3. Індуктивний крок: покажемо, що тоді (*) істинна для l=k.

Розглянемо 2 можливих випадки:

Випадок 1: А – це ¬В, де l(В)= k-1.

Випадок 2: А – має вигляд В С, де l(В)+ l(С)=γ-1.

Читайте також:

1. А .Маршалл - основоположник неокласичної теорії.
2. Аксіоматичний метод у математиці та суть аксіоматичної побудови теорії.
3. Альтернативні теорії вартості
4. Альтернативні теорії капіталу
5. Альтернативні теорії макроекономічного регулювання
6. Альтернативні теорії максимізації
7. Альтернативні уявлення щодо макроекономічного регулювання: теорії раціональних сподівань та економіка пропозиції. Крива Лафера.
8. Базові поняття теорії і методики фізичного виховання.
9. Більш повну практику ціноутворення в сучасних умовах у розвинутих країнах світу допоможе з’ясувати короткий виклад розвитку теорії ціни.
10. Біологічні і психологічні теорії.
11. Взаємозв’язок психодинамічної теорії АСПН з іншими теоріями
12. Види і теорії сну. Повільний і швидкий сон. Механізм виникнення сну.

Переглядів: 586