UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЧислення висловлень і алгебра висловлень. Основні проблеми числення висловлень (реферат)
Авторdimich
РозділЛогіка, формальна логіка, юридична логіка
ФорматWord Doc
Тип документуРеферат
Продивилось2011
Скачало500
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

Числення висловлень і алгебра висловлень. Основні проблеми числення

висловлень.

 

Довільну формулу F числення висловлень можна змістовно інтерпретувати

як складене висловлення, істинність або хибність якого залежить від

істинності елементарних висловлень, що до нього входять. Таким чином,

кожній формулі F числення висловлень можна аналогічно тому, як це було

зроблено в алгебрі висловлень, поставити у відповідність функцію

істинності f.

 

Виникає питання, як пов’язано таке змістовне «істинносне» тлумачення

(інтерпретація) формул числення висловлень з їхньою формальною

вивідністю.

 

Теорема 5.5. Будь-яка теорема числення висловлень ЧВ є тотожно істинним

висловленням (тавтологією).

 

Доведення. Тотожна істинність усіх аксіом легко перевіряється

безпосередньо побудовою відповідних таблиць істинності для кожної з них

(рекомендуємо це зробити самостійно).

 

Відтак, доведемо, що обидва правила виведення числення висловлень

перетворюють тотожно істинні формули у тотожно істинні.

 

A, що отримується з формули A шляхом підстановки замість пропозиційних

змінних p1,p2,...,pn довільних формул B1,B2,.....,Bn, оскільки останні

можуть набувати лише значень 0 або 1.

 

Доведемо, що коли формули A і A(B є тотожно істинними, тоді формула B,

яку ми дістаємо з них за правилом висновку, також є тотожно істинною.

Припустімо супротивне: нехай B не є тотожно істинною формулою, тобто

існує набір значень її змінних, на якому вона набуває значення 0. Тоді

підставимо цей набір у формулу A(B, оскільки A є тавтологією, то

дістанемо вираз 1(0, значенням якого є 0. Останнє суперечить припущенню

про тотожну істинність формули A(B.

 

Таким чином, ми переконалися в тому, що всі аксіоми числення висловлень

ЧВ є тотожно істинними формулами алгебри висловлень, а застосування обох

правил виведення (підстановки і висновку) до тотожно істинних формул

знову приводить до тотожно істинних формул. Отже, всі вивідні формули

(теореми) числення висловлень є тотожно істинними формулами алгебри

висловлень.

 

Справедливою є й обернена теорема, яку подамо без доведення.

 

Теорема 5.6. Будь-яка тотожно істинна формула алгебри висловлень є

теоремою числення висловлень ЧВ.

 

Дві останні теореми дозволяють вирішити три важливі проблеми числення

висловлень: проблему несуперечності, проблему повноти і проблему

розв’язності. Розглянемо їх послідовно.

 

1. Проблема несуперечності.

 

Для кожної формальної теорії кардинальним є питання несуперечності.

Справді, така теорія будується послідовним приєднанням нових теорем, які

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

жодної гарантії, що в цьому процесі ми не дійдемо до суперечності.

Iнакше кажучи, виникає питання, чи при поступовому нагромадженні теорем

формальної теорії (числення) не трапиться так, що одна з теорем

суперечитиме іншим. Саме так виникає проблема несуперечності числення.

 

Числення є несуперечним, якщо неможливо одночасно вивести з аксіом

числення як формулу A, так і її заперечення (A.

 

Наслідок 5.1. Числення висловлень ЧВ є несуперечною формальною теорією.

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ