WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Числення висловлень - Реферат

Числення висловлень - Реферат

у численні вивідність вигляду Г A, де Г - множина формул, A - довільна формула, можна розглядати як правило виведення , яке можна додати до заданої множини правил.
Наприклад, доведену у прикладі 3(1) вивідність a b a разом з правилом підстановки можна розглядати як правило , що може бути інтерпретовано так: "якщо формула A є вивідною, то вивідною є і формула B A, де B - довільна формула". Це правило надалі можна використовувати для побудови нових виведень. Такі правила називатимемо похідними правилами. За допомогою додаткових похідних правил дістаємо можливість скоротитививедення формул, не виконуючи повного виведення. Маючи скорочене виведення, завжди можна побудувати повне виведення, замінюючи кожну формулу, яка є результатом застосування похідного правила виведення, на повне її виведення. Такою формулою є, наприклад, формула F2 у прикладі 3(3). Iнакше кажучи, похідні правила - це будівельні блоки при побудові виведень формул ЧВ, кожен з яких замінює кілька кроків звичайного виведення.
Могутнім засобом одержання ряду важливих і корисних похідних правил виведення є так звана метатеорема дедукції (МТД); зокрема, сама МТД може розглядатись як таке похідне правило.
Теорема 3 (метатеорема дедукції). Якщо Г,A B, то Г A B, де Г - множина формул (можливо, порожня), A і B - формули.
Доведення. Зауважимо, що доведення метатеорем на відміну від теорем числення проводиться змістовно як звичайне математичне доведення.
Будемо виходити з того, що задані аксіоми є схемами аксіом, тобто не будемо користуватись правилом підстановки.
Нехай Г,A B. Тоді існує виведення B1,B2,...,Bn з Г,A таке, що Bn=B. Доведемо за індукцією, що для будь-якого k n Г A Bk.
Розглянемо спочатку випадок k=1, тобто формулу B1. B1, як перша формула виведення, повинна або бути аксіомою, або міститися в Г, або співпадати з A.
Зі схеми аксіоми A1 випливає, що B1 (A B1) є аксіомою. Якщо B1 - аксіома або міститься в Г, то за правилом висновку A B1 є вивідною з Г. Якщо ж B1=A, то з прикладу 2 маємо, що A A, тобто A B1 є вивідною формулою. Отже, у будь-якому випадку отримаємо Г A B1.
Відтак, припустімо, що Г A Bі для довільного iа) Bk - аксіома;
б) Bk міститься у Г;
в) Bk = A;
г) Bk є вивідною з деяких попередніх формул Bj та Bl за правилом висновку; у цьому випадку формула Bl повинна мати вигляд Bj Bk.
У випадках а), б), в) доведення твердження Г A Bk здійснюється аналогічно доведенню для B1 (випадки а) і б) - за допомогою схеми аксіоми A1; випадок в) - за допомогою результату прикладу 5.2).
У випадку г) за індуктивним припущенням маємо Г A Bj і Г A Bl, де Bl - це Bj Bk, тобто Г A (Bj Bk).
Підставимо у схему аксіоми A2 A замість a, Bj замість b і Bk замість c. Дістанемо (A Bj) ((A (Bj Bk)) (A Bk)).
Застосовуючи до останньої вивідної формули двічі правило висновку, отримаємо Г A Bk. Залишилось покласти k=n.
Розглянемо декілька застосувань метатеореми дедукції.
1. Дуже поширеним методом математичних доведень є метод доведення від супротивного: припускаємо, що A є вірним (істинним твердженням), і доводимо, що, по-перше, з A виводиться B, а по-друге, що з A виводиться B, що неможливо; отже, A невірно, тобто вірно A.
У термінах числення висловлень цей метод формулюється так:
"якщо Г, A B і Г,A B, то Г A".
Доведемо справедливість цього правила у численні висловлень.
Справді, за теоремою дедукції, якщо
Г, A B і Г, A B, то Г A B і Г A B
F1: A B
F2: A B
F3: A9 = (A B) (B A)
F4: MP(F2,F3)=B A
F5: A2 = (A B) ((A (B C)) (A C))
F6: MP(F1,F5) = (A (B C)) (A C)
F7: F6 = ((A B) (B A)) ((A B) A))
F8: A1 = (B A) ((A B) (B A))
F9: MP(F4,F8) = (A B) (B A)
F10: MP(F9,F7) = (A B) A
F11: MP(F1,F10) = A
Доведене твердження (метатеорему) часто називають правилом введення заперечення і записують у вигляді
Г, A B; Г, A B
Г A
Крім того, неважко переконатись у справедливості для числення висловлень такого твердження або метатеореми, яку можна вважати оберненою до метатеореми дедукції (ОМТД): "якщо Г A B, то Г, A B"
Послідовно маємо
F1: A
F2: A B
F3: MP(F1,F2) = B
2. Доведемо тепер закон виключення третього: A A.
F1: A6 = A (A A)
F2: (a a) = ( (A A)) ( (A A)) (див.приклад 2)
З формул F1 і F2 маємо (за ОМТД)
F3: (A A),A A A
F4: (A A), A (A A)
За доведеним правилом введення заперечення у формула з F3 і F4 отримаємо:
F5: (A A) A.
Аналогічно використовуємо аксіому A7, в якій замість b підставляємо A.
A7 = A (A A)
(A A), A A A
(A A), A (A A)
Отримуємо
F6: (A A) A.
За правилом введення заперечення з F5 і F6 дістанемо:
F7: (A A)
F8: A10 = (A A) (A A)
F9: MP(F7,F8) = A A, тобто A A.
Iснують й інші числення висловлень, тобто числення з іншими системами аксіом і правилами виведення.
Наприклад, розглянемо числення висловлень ЧВ1, яке використовує тільки логічні операції і і має таку систему аксіом:
S1. a (b a)
S2. (a (b c)) ((a b) (a c))
S3. ( a b) (( a b) a)
Правилами виведення в новому численні є ті самі правила, що і в старому, тобто правило підстановки і правило висновку.
Якщо в системі аксіом першого числення замінити підформули (a b) на ( a b), а підформули (a b) - на (a b), то справедливою є така теорема.
Теорема 4. Обидва наведені числення висловлень ЧВ і ЧВ1 є рівносильними в тому смислі, що множини формул вивідних у кожному з цих числень (множини теорем цих числень) співпадають між собою.
Доведення теореми полягає в тому, що доводиться вивідність усіх аксіом першого числення з аксіом другого, і навпаки (з урахуванням зауважень відносно і ).
Яке з двох числень краще? Однозначної відповіді на це питання немає. Друге числення є більш компактним і наочним; відповідно більш компактними є доведення різних його властивостей. У той же час, у багатшому першому численні виведення різноманітних формул є, взагалі кажучи, коротшими.
Можливі й інші числення, що рівносильні двом наведеним.
Loading...

 
 

Цікаве