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

главная страница Рефераты Курсовые работы текст файлы добавьте реферат (спасибо :)Продать работу

поиск рефератов

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

скачать
похожие рефераты
подобные качественные рефераты
1 2    

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

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


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

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

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

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

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

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

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

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

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

A1. a(ba)

A2. (ab)((a(bc))(ac))

A3. (ab)a

A4. (ab)b

A5. (ab)((ac)(a(bc)))

A6. a(ab)

A7. b(ab)

A8. (ac)((bc)((ab)c))

A9. (ab)(ba)

A10. aa

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

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

A(p)

A(B)

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

A, AB

B

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

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

Наприклад, для схеми формул AB, якщо замінити A на p, а B - на pq, то з даної схеми отримаємо формулу числення p(pq); якщо ж метазмінну A замінити на pq, а B - на (pq)p, то дістанемо формулу (pq)((pq)p) тощо.

Використання схем формул можна поширити і на всі аксіоми. Наприклад, якщо в системі аксіом пропозиційні змінні a,b,c замінити метазмінними A,B,C, то отримаємо десять схем аксіом, що задають десять нескінченних множин аксіом. Таким чином приходимо до іншого способу побудови числення висловлень: з нескінченною множиною аксіом (що задається скінченним числом схем аксіом), але без правила підстановки, оскільки воно неявно міститься у поясненні (інтерпретації) схем аксіом.

Перший спосіб є більш послідовно конструктивним: всі його засоби явно зафіксовані і скінченні; при введенні числення в ЕОМ (наприклад, для автоматизації доведень теорем та побудови виведень для заданих формул) він виглядає природнішим.

З іншого боку, другий спосіб більш відповідає математичній традиції тлумачення (інтерпретації) формул: наприклад, алгебраїчна тотожність (a+b)2=a2+2ab+b2 або відомі логарифмічні чи тригонометричні тотожності тлумачаться саме як схеми тотожностей, а не конкретні тотожності, справедливі лише для конкретних літер. Правило підстановки при цьому мається на увазі і присутнє неявно. Втім, досить очевидно, що перехід від одного способу побудови числення до іншого є нескладним.

Аксіоми числення висловлень разом з правилами виведення повністю визначають поняття довідної (вивідної) формули у ЧВ, або теореми ЧВ.

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

Розглянемо приклади виведення теорем ЧВ.

Приклад 5.2. Доведемо, що формула aa є теоремою ЧВ.

1) Підставляючи в аксіому A2 змінну a замість змінної c і ba замість b, матимемо вивідну формулу

(a(ba))((a((ba)a))(aa))

2) Підформула a(ba) є аксіомою A1. Тоді з вивідних формул

a(ba) і (a(ba))((a((ba)a))(aa))

за правилом висновку виводимо формулу

(a((ba)a))(aa)).

3) Замінимо в аксіомі A1 b на (ba):

a((ba)a).

4) Знову, застосовуючи правило висновку до двох останніх формул, матимемо, що формула aa є вивідною.

Для зручності приймемо таку форму запису виведення формул у ЧВ:

а) послідовність формул виведення писатимемо в стовпчик, нумеруючи їх у порядку слідування F1, F2,....

б) поряд з кожною формулою після двокрапки писатимемо пояснення, що встановлює законність її появи у виведенні.

Правило підстановки записуватимемо у вигляді
    продолжение
1 2    

Добавить реферат в свой блог или сайт
Удобная ссылка:

Скачать реферат бесплатно
подобрать список литературы


вверх страницы


© coolreferat.com | написать письмо | правообладателям | читателям
При копировании материалов укажите ссылку.