Головна

Аксіоматичні теорії. Визначення та властивості обчислення висловлювань.

  1.  C) немонетарні статті, які оцінюються за справедливою вартістю в іноземній валюті, слід переводити за обмінним курсом на дату визначення справедливої ??вартості.
  2.  C) вказати функціональну валюту підприємства і метод перекладу, використаний для визначення допоміжної інформації.
  3.  I. ВИЗНАЧЕННЯ
  4.  II. Основні визначення
  5.  III. Загальні хімічні властивості металів
  6.  V. Хімічні властивості деяких сполук неметалів
  7.  VII. Хімічні властивості алюмінію

Обчислення висловлювань - це приклад аксіоматичної теорії. ІВ визначається наступним чином:

1. Алфавіт ІВ - це висказивательную змінні, дужки: (,) і логічні символи и  . Будь-який набір символів алфавіту ІВ (навіть безглуздий) - це вираз ІВ.

2. Є підмножина виразів, зване формулами ІВ. Формули ІВ: а) все висказивательную змінні - це формули; б) якщо A і B формули, то  A і A  B теж формули. Формули ІВ - це підмножина формул логіки висловлювань, що містять тільки логічні символи и .

3. Виділено деяку підмножину формул, зване аксіомами ІВ. Які б не були формули A, B і C, такі формули є аксіомами ІВ:

A1. A  (B  A);

A2. (A  (B  C))  ((A  B)  (A  C));

A3. ( B  A)  (( B  A)  B).

Вирази A1 - A3 називаються схемами аксіом, оскільки кожне з них породжує безліч аксіом ІВ. Наприклад, формула X  (Y  X) є аксіома, отримана за схемою A1, а формула ( A  A)  (( A  A)  A) - аксіома ІВ, отримана за схемою A3.

4. Є правило виведення ІВ, що дозволяє з попередніх формул виведення отримувати наступні. Висновком в ІВ називається всяка послідовність формул ІВ (кроків виведення) така, що будь-яка формула є або аксіома або теорема ІВ, або отримана з попередніх формул виведення за допомогою правила виведення ІВ.

Формула T називається теоремою ІВ, якщо існує висновок, в якій ця формула є останньою. Цей висновок називається висновком теореми T ІВ:  T. Зліва від символу  аксіоми ІВ, теореми ІВ і те, що отримано з них за правилом виведення ІВ, що не записується.

Правило виводу m.p. (Modus ponens): якщо у висновку є дві формули виду А  В і А, то після них у висновку можна писати формулу В. Вважається, що формула В отримана за правилом m.p. з формул А і А  В. Правило записується так:  або А, А В  В. Порядок формул А і А  В у висновку не важливий (A може зустрітися виведення раніше А  В, а може і пізніше), але формулу B можна писати раніше, ніж А і А  У з'являться у висновку.

Всі аксіоми ІВ - це тавтології, що можна перевірити по їх таблиці істинності. За правилом m.p. з тавтологію можна отримати тільки тавтології.

12. Теорема дедукції і два її слідства. Правило modus ponens.

Висновок теореми A  A складний. Починаємо спрощувати (скорочувати) висновок теорем ІВ і наслідків з гіпотез. теорема: Якщо Г  A і B - будь-яка формула, то Г B  A. Доведення: Нехай A1, ..., An = A - виведення формули A з Г. Тоді A1, ..., An, A  (B  A), B  A - виведення формули B  A з Г. Тут An = A, передостанній крок виведення отриманий за схемою аксіоми A1, а формула B  A отримана за правилом m.p. з двох передостанніх кроків виведення. Теорема доведена.

Теорема про дедукції: Нехай набір гіпотез Г (може бути і порожньою) і виділена гіпотеза A призводять до B: Г, A  B. Тоді Г A  B. Доведення проведемо індукцією по n - довжині виведення формули B з Г і A. Нехай B1, ..., Bn - це висновок формули B з Г і A. Робимо перший крок індукції. При n = 1 B = B1. За визначенням виведення ІВ можливі три випадки: B1 - це аксіома, або формула з безлічі гіпотез Г, або B1 = A = B. Для аксіоми і формули з Г маємо: Г  B1. Згідно зі щойно доведеної теореми для кожної формули A Г A  B1, тобто Г A  B.

Для B = A формула A  B має вигляд A  A, що є теоремою ІВ ( A  A). Звідси Г A  A. Перший крок індукції по довжині виведення n доведений. Зробимо індуктивне припущення, що якщо довжина виводу формули B з Г і A менше n, то теорема про дедукції виконується. З цього доведемо, що теорема вірна і для довжини виведення, рівного n.

За визначенням виведення ІВ можливі чотири випадки: Bn - це аксіома, або формула з безлічі гіпотез Г, або Bn = A = B, або Bn отримана по m.p. з попередніх кроків виведення Bi і Bj, де i

Висновок формули Bi - це перші i формул з виведення формули Bn з Г і A. Висновок формули Bj - це перші j формул з виведення формули Bn з Г і A. Довжини цих висновків менше n, так як i

(1) Г A  Bi;

(2) Г A  Bj (Г A  (Bi  Bj));

за схемою аксіом A2 маємо:

(3) Г  (A  (Bi  Bj))  ((A  Bi)  (A  Bn)), де замість B підставлена ??Bi, а замість C - Bn;

застосовуючи шосте властивість виводимості з гіпотез до (2) і (3), отримуємо:

(4) Г  (A  Bi)  (A  Bn);

застосовуючи шосте властивість виводимості з гіпотез до (1) і (4), отримуємо:

(5) Г  (A  Bn). Теорема про дедукції доведена.

 




 Формули логіки висловлювань та їх еквівалентність. Правило рівносильних перетворень. |  Двоїстість. Закон подвійності. |  Нормальні форми формул. Теорема про єдиності СДНФ і СКНФ. |  Повні системи булевих функцій. Суперпозиції. Теорема про повноту системи функцій, виражених за допомогою суперпозиції через функції іншої повної системи. |  Функціонально решітка поста. Замкнені класи T0, T1. |  Незалежна система функцій і базис функціонально замкнутого класу. |  Предикати, квантори, їх область дії. Вільні і зв'язані змінні. |  Равносильность формул логіки предикатів. Правила переходу до рівносильним формулам в логіці предикатів, що збігаються з аналогічними правилами в логіці висловлювань. |  Здійснимість і общезначімость формул логіки предикатів. Теорема Черча. |  Общезначімость виведених в численні предикатів формул. |

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