Числення висловлень, Детальна інформація

Реферат на тему:

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

Числення висловлень (ЧВ) згідно з поданою у розділі 1 схемою означається таким чином.

1. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a,b,c,d,...,x,y,z (можливо з індексами), знаків логічних операцій (,(,(,( і круглих дужок ( та ).

2. Поняття формули означається аналогічно алгебрі висловлень.

а) всі пропозиційні змінні та елементарні висловлення є формулами;

б) якщо A і B - формули, то вирази (слова) (A(B), (A(B), ((A), (A(B) також є формулами;

в) інших формул, ніж побудовані за правилами а) і б) немає.

Відзначимо важливу властивість даного означення. Можна довести, що існує формальна процедура, яка, будучи застосована до будь-якого слова у розглядуваному алфавіті, за скінченну кількість кроків встановить, чи є дане слово формулою, чи ні. Більш того, за записом формули ця процедура дасть повний її синтаксичний розбір, тобто дасть опис послідовності кроків побудови формули за означеними вище правилами.

Зауважимо також, що з метою зменшення кількості (економії) дужок у формулах вводять порядок виконання (або пріоритети, старшинство) операцій. Зокрема, звичайно, опускають зовнішні дужки формул та замість ((A) записують (A;

3. Аксіомами числення висловлень будуть такі формули:

A1. a((b(a)

A2. (a(b)(((a((b(c))((a(c))

A3. (a(b)(a

A4. (a(b)(b

A5. (a(b)(((a(c)((a((b(c)))

A6. a((a(b)

A7. b((a(b)

A8. (a(c)(((b(c)(((a(b)(c))

A9. (a((b)((b((a)

A10. ((a(a

4. Правилами виведення є:

правило підстановки. Якщо A - вивідна формула, яка містить літеру p (позначимо цей факт A(p)), то вивідною є і формула A(B), що здобувається з A заміною всіх входжень літери p на довільну формулу B; записується

A(p)

A(B)

2) правило висновку (modus ponens). Якщо A і A(B - вивідні формули, то вивідною є й формула B; записується

A, A(B

B

У поданому описі числення висловлень аксіоми є формулами числення (відповідними до означення формули); формули, що використовують у правилах виведення (A, A(B тощо), є метаформулами, або так званими схемами формул.

Схема формул - це вираз метамови для позначення нескінченної множини всіх тих формул числення, які отримують після заміни змінних метамови (метазмінних) цієї схеми певними формулами числення.