Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Повнота і несуперечність теорії 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, ..., Вк. Нехай задано деякий розподіл істинних значень для В1, В2, ..., Вк. Нехай тоді

 

Нехай

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

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

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

А В ¬В  
и и л Л
и л и И
л и л И
л л и И

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

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

1 рядок

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

3 рядок

4 рядок

Доведення:

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

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

 

(*): , тобто стверджується, що - це так (Лема 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. Види і теорії сну. Повільний і швидкий сон. Механізм виникнення сну.




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

<== попередня сторінка | наступна сторінка ==>
Формальна аксиоматична теорія L для числення висловлювань. | Хід уроку

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.005 сек.