ПРИКЛАДИ ФОРМАЛЬНИХ СИСТЕМ

Обчислення висловлювань

Ця формальна система називається ще логікою висловлювань, або пропозіціональной логікою. Формальні системи, як визначено вище, являють собою систему чотирьох об'єктів М = <Т, Р, А, В>: Т- алфавіт, Р - безліч синтаксичних правил, А - безліч аксіом, В - безліч правил виведення. Отже, задати формальну систему - це задати ці чотири об'єкти.

Визначення обчислення висловлювань

Логіка висловлювань визначається наступним чином.

  • 1. Алфавіт
  • - пропозіціональние символи - це букви латинського алфавіту (великі та малі) або ті ж букви з індексами, наприклад: А ,, А ь ..., Р, Q, а, Ь, х ь х 2 , ...; ці символи використовуються для позначення висловлювань, тобто тверджень про властивості або взаємозв'язках об'єктів предметної області;
  • - логічні зв'язки:

заперечення (читається «не», «заперечення», «невірно, що»); використовується для позначення частки «не» і всіх її синонімів, імплікація -> (читається «якщо ..., то ...», «тягне», «слід», «імплікація», «имплицирует»); використовується для позначення словосполучень «якщо ..., то ...», «тому що», «тому що» ит.п .;

  • - круглі дужки (і); використовуються для правильного написання та правильної інтерпретації формул.
  • 2. Синтаксичні правила
  • - будь-який пропозіціональний символ є формула;
  • - якщо т є формула, то (т) теж є формулою;
  • - якщо т, / і, і т 2 є формулами, то вирази -> т і т, -> т 2 теж є формулами.
  • 3. Аксіоми

У цих аксіомах символи т ь т 2 і т, позначають довільні формули.

4. Правило виводу (правило modus ponens, або правило відділення)

Правило modus ponens означає: якщо є дві формули т ] і т ^ т ь то можна записати формулу т 2 . Іншими словами, формула т 2 є логічним висновком з формул / і, і / і, -> / Видане визначення досить економно, так як використовує лише дві зв'язки (-1 і - ») і всього три аксіоми. Однак існує ще більш економне визначення цієї формальної системи, що використовує одну в'язку (штрих Шеффера) і одну аксіому. Про це докладніше йтиметься нижче.

У будь-якої формальної системі, якщо необхідно, можна визначати нові зв'язки і правила освіти формул на основі заданих у визначенні формальної системи. Наприклад, в логіці висловлювань, як правило, в алфавіт вводяться нові логічні зв'язки л (сполучення), v (диз'юнкція) і = (еквівалентність), які визначаються через задані зв'язки і в такий спосіб:

Аль позначає формулу -. (ДГ -> -, й), avb позначає формулу (^ а-> Ь), а = Ь позначає формулу (а-> Ь) л (Т-> а).

Введення нових логічних зв'язок в алфавіт логіки висловлювань супроводжується доповненням списку синтаксичних правил новим правилом: - якщо т х і т 2 є формулами, то вираження т ^ т 2 , m { vm 2 і т х = т 2 теж є формулами.

До правилом виведення ( МР) при цьому додаються такі правила переписування:

Правила переписування застосовуються як до всієї формулою в цілому, так і до окремих її частин. Символ | => вказує на те, що відповідне правило виведення є саме правилом переписування. Правило виводу (МР) застосовується тільки до формул в цілому, до частин формул його застосовувати не можна.

Так що логіку висловлювань можна було відразу визначити з усіма п'ятьма зв'язками і з тими доповненнями до списку синтаксичних правил і до списку правил виведення, про які щойно йшлося. При цьому обидва визначення призводять до одного і того ж безлічі теорем.

До цього ж безлічі теорем призводить ще більш економне визначення логіки висловлювань, засноване на єдиній логічній зв'язці | (Штрих Шеффера). Логіка висловлювань в деякому сенсі еквівалентна формальної системі, в якій алфавіт, синтаксичні правила, аксіоми та правила виведення задаються наступним чином.

  • 1. Алфавіт
  • - пропозіціональние символи - це букви латинського алфавіту (великі та малі) або ті ж букви з індексами, наприклад: А ,, А ,, ..., Р, Q, а, Ь, х ь х 2 , ...; ці символи використовуються для позначення висловлювань, т. е. тверджень про властивості або взаємозв'язках об'єктів предметної області;
  • - логічна зв'язка : | (штрих Шеффера);
  • - круглі дужки (і); використовуються для правильного написання та правильної інтерпретації формул.
  • 2. Синтаксичні правила
  • - будь-який пропозіціональний символ є формула;
  • - якщо т є формула, то ( т) теж є формулою;
  • - якщо т : і т 2 є формулами, то вираз т, | т 2 теж є формулою.
  • 3. Аксіома
  • (Р | (0І) 1 (ЖФ)) 1 ((* 1?) 1 ((НОМ?))) -

Тут символи p, q, r, snt позначають довільні формули.

4. Правило виводу

Еквівалентність описаної формальної системи логіці висловлювань слід розуміти в тому сенсі, що якщо у всіх теоремах цієї формальної системи запису аЬ замінити формулою (-.av -, /;), то отримане безліч формул повністю вичерпує всі теореми логіки висловлювань.

Цей факт був встановлений Ж. Ніко в 1917 р Зауважимо, що п'ять логічних зв'язок логіки висловлювань можуть бути виражені через штрих Шеффера: -> р відповідає формулі р | р, pvq відповідає формулі ((pp) (qq)), p / q відповідає формулі ((/; | с /) | (/; | с /)), p ^> q відповідає формулі (p (qq)), р = q відповідає ({p (qq)) (q (pp))) (((p (qq)) (q (pp))) -

Є ще один економний варіант визначення логіки висловлювань в порівнянні з даними на початку. Він був запропонований Я. Лукасевич і Б. Собочінскім і заснований на тих же двох зв'язках і -но на одній єдиній аксіомі при використанні правила виведення modus ponens. Цей варіант визначення призводить до того ж безлічі формул, що і первинне визначення логіки висловлювань.

Введені вище три зв'язки л, v і = збагачують логіку висловлювань, надаючи додаткові кошти формалізації знань про об'єкти предметної області. Зокрема, можна відзначити, що три закони логіки з великого списку законів, сформульованих Аристотелем, в збагаченої новими трьома зв'язками логіці висловлювань виражаються строго доказовим формулами (теоремами):

  • - закон тотожності р ^> р,
  • - закон виключеного третього pv-, p,
  • - закон суперечності ~ ^ (рк ^ р).

Як приклад докази в численні висловів розглянемо доказ закону тотожності /? - »/ ?.

  • 1 • р-> ((/? -> /?) -> /?) Аксіома 1) при / і, = р, т 2 = (р> р)
  • 2. (р-> ((/? -> /?) -> /?)) -> ((/? -> (/? - »/?)) -> (/? -> /?)) Аксіома (А2) при т ] = т 3 = р, Щ = (р ^ р)
  • 3. (р-> (р ^> р)) ^> (р ^ р) правило ( МР ), застосоване до формул (1) і (2)
  • 4. /? -> (/? -> /?) Аксіома (AI) при т ] = т 2 = р
  • 5. р ^ р правило (МР), застосоване до формул (3) і (4)

Нехай в алфавіт логіки висловлювань введені зв'язки а, уі =, як це описано вище. Деякі теореми логіки висловлювань, які відіграють в ній важливу роль, називають законами логіки висловлювань. Перерахуємо їх.

I. Закони коммутативности

II. закони асоціативності

III. закони дистрибутивности

IV. закони ідемпотентності

V. Закони де Моргана (закони двоїстості)

VI. Закон подвійного заперечення

VII. Закон виключеного третього

VIII. закон суперечності

У законах логіки висловлювань символами я, b і з позначені довільні формули, тому закони розглядаються як схеми теорем: підстановка в закон будь-яких формул замість символів а, Ьмс приводить до формули, яка сама є теоремою.

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >