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

Формальна аксиоматична теорія L для числення висловлювань.

Властивості поняття виведення із гіпотез

Поняття формальної теорії

Числення висловлювань

Формальна теорія Т вважається визначеною, якщо виконані наступні умови:

1. Задана рахункова множина символів теорії Т (її абетка). Кінцеві послідовності символів називаються виразами теорії Т.

2. Є деяка підмножина виразів-формул теорії Т. (Звичайно існує процедура, яка дозволяє визначити чи є вираз формулою, чи ні).

3. Виділена деяка підмножина формул-аксіом теорії Т. Якщо існує алгоритм розпізнати за формулою є вона аксіомою чи ні, то таку теорію називають аксіоматичною.

4. Є кінцеве число відношень між формулами , які називаються правилами виведеня.

При цьому кожному правилу відповідає ціле додатне число j таке, що для кожних j формул та формули А може бути вирішене питання: чи знаходяться дані j формул в відношенні з формулою А.

Якщо це так, то формула А називається безпосереднім наслідком формул за правилом .

Означення. Виведенням в теорії Т називається послідовність формул така, що формула є або аксіома, або безпосередній наслідок яких-небудь попередніх формул по одному з правил виведення.

df. Формула А називається теоремою теорії Т, якщо існує висновок в теорії Т, в якому останньою формулою є А.

Нехай Г – деяка множина формул теорії Т (множина гіпотез).

df. Висновком з Г в теорії Т називається послідовність формул така, що j або гіпотеза, або аксіома, або безпосередній наслідок деяких попередніх формул по одному з правил виведення.

Говорять, що з Г виведена формула А , якщо існує висновок з Г, в якому останньою формулою є А.

Якщо множина Г кінцева: , то будемо писати .

Якщо Г – пуста множина , то А є теоремою. Замість пишуть звичайно .

(1) Якщо та , то .

(тобто якщо А виводиться з множини гіпотез Г, то А залишається виведеним, якщо додати до Г нові гіпотези).

(2) тоді і тільки тоді, коли в Г існує кінцева підмножина , для якої .

(3) Якщо та , то .

Зокрема, якщо , то .

1) Символами теорії L є

а) пропозийні літери з індексами .

б) зв’язки ; (примітивні зв’язки)

в) дужки (, ).

2) Формули.

а) Усяка п.літера є формулою.

б) Якщо А та В – формули, то та - також формули.

в) Вираз є формулою тоді і тільки тоді, коли це випливає з пунктів а) та б).

3) Аксіоми. формул А, В, С теорії L наступні формули є аксіомами:

(А1)

(А2)

(А3) .

4) Єдиним правилом виведення є правило modus ponens: .

Правила зняття дужок залишаються колишніми. Властивості поняття виведення .

Введемо інші зв’язки за допогою наступних означень:

означає

означає

означає

Лема 1. (тобто - це теорема теорії L).

Доведення:

Побудуємо висновок в L.

1) підстановка в схему аксіом (А1)

2) схема аксіом (А2)

3) по m.p. з 1, 2

4) схема аксіом (А1)

5) по m.p. з 3, 4

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

(Зокрема, якщо , то ).

Доведення:

Нехай висновок формули В з Г, А.

Індукцією по i доведемо, що (*) .

1) Перевірка базиса індукції. i=1.

Варіант 1. Нехай вірно a) або b). Маємо наступний висновок з Г:

1. a) або b)

2. (А1)

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

Ми показали, що .

Варіант 2. є А.

За лемою 1 . Значить, . Але, якщо виведена з Г (властивість (d) поняття виведення).

2) Індуктивне припущення: нехай твердження (*) вірне .

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

Варіант 1. доводиться так само, як і для .

Варіант 2. є .

Нехай отримується з деяких формул та по m.p.. Тоді повинна бути влаштована так . Тут k<m, j<m, тому для та твердження (*) вірне.

тобто

тобто

Продовжимо висновок з Г

…

2.

3.

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

5. по m.p. 1, 4

Ми побудували висновок з . Що і треба було.

Наслідок 1.

1. гіпотеза

2. гіпотеза

3. гіпотеза

4. гіпотеза

5. гіпотеза

Показали, що .

Звідси, за теоремою дедукції .

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

1. E) теорія раціонального вибору.
2. I. Теорія граничної продуктивності і попит на ресурси
3. V теорія граничної корисності визначає вартість товарів ступенем корисності останньої одиниці товару для споживача.
4. Автододавання та автообчислення.
5. Алг W2 (ОБЧИСЛЕННЯ Y)
6. Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.
7. Алгоритми переведення чисел з однієї позиційної системи числення в іншу
8. Аналітичні показники динаміки та прийоми їх обчислення
9. Арифметичні операції в різних системах числення
10. База оподаткування, ставки податку та порядок обчислення.
11. Балансова теорія визначення статі. Диференціація статі і роль гормонів у цьому процесі.
12. Безпосереднє обчислення з використанням формули Ньютона-Лейбніца.

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