Студопедия
Главная страница | Контакты | Случайная страница | Спросить на ВикиКак

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Числення висловлень. Аксіоми і правила виводу

Читайте также:
  1. Cтратегiя виводу новинки на ринок.
  2. I. Правила ведения дневника
  3. I. Правила оформления отчета по практике
  4. I. Правила оформления отчета по практике
  5. I. Правила терминов
  6. I. Прочтите слова и объясните правила чтения буквы е
  7. II. Правила оформления курсовой работы
  8. II. ПРАВИЛА ОФОРМЛЕНИЯ РАБОТЫ
  9. III. Общие правила заполнения рецепта.
  10. IV. Упражнения пауэрлифтинга и правила их выполнения.

У численні висловлень ми знову зустрічаємося з об'єктами, з якими якось уже мали справу - з формулами алгебри логіки. Проте тут формули розглядаються не як спосіб представлення функцій, а як складові висловлення, утворені з елементарних висловлень (змінних) за допомогою логічних операцій Ú, &, ¯ , ®. Наприклад Х®Y. Остання операція читається: "якщо X, то Y". При цьому особлива увага приділяється тотожньо-істинним висловленням, оскільки, як уже відзначалося, вони повинні входити в будь-яку теорію як загальнологічні закони. Їхнє породження і є основною задачею числення висловлень. Числення висловлень визначається в такий спосіб.

Алфавіт числення висловлень складається зі змінних висловлень (пропозиційних букв): А, В, С, ... , знаків логічних зв'язків Ú, & , ¯ , ® і скобок ( , ).

Формули:

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

б) якщо 2τ і 2p - формули, то (2τ Ú2p), (2t&2p), (2t ® 2p) і ` 2τ - формули;

в) інших формул немає.

Зовнішні скобки у формулах звичайно домовляються опускати: наприклад, замість (2τ Ú 2p) пишуть 2t Ú 2p. Замість синтаксично більш зручного знака ┐ часто вживається риска над формулою.

 

Аксіоми. Наведемо тут дві системи аксіом. Перша з них безпосередньо використовує всі логічні зв'язки:

 

Система аксіом І.

І 1. A®(B®A);

І 2. (A®B) ® ((A® (B®C)) ® (A®C));

І 3. (A&B) ®A;

Ι 4. (A&B) ®B;

І 5. A® (B® (A&B));

Ι 6. A® (AÚB);

І 7. B® (AÚB);

І 8. (A®C) ® ((B®C)((AÚB) ®C));

І 9. (A®B)((A®┐B) ®A);

І 10. ┐┐A®A.

 

Інша система використовує тільки дві зв'язки ┐ і ® ; при цьому скорочується алфавіт числення ( викидаються знаки Ú, &) і відповідно визначені формули. Операції Ú, & розглядаються не як зв'язки числення висловлень, а як скорочення ( уживати які зручно, але не обов'язково ) для деяких його формул: АÚВ заміняємо ┐А ®В, А&У заміняємо ┐( А ® ┐В). У результаті система аксіом стає набагато компактніше.

 

Система аксіом II.

ІI 1. A®(B®A);

II 2. (A®(B®C))®((A®B)®(A®C);

II 3. (ùA®ùB)®((ùA®B)®A).

 

Наведені системи аксіом рівносильні в тому сенсі, що породжують ту саму множину формул. Яка із систем краще? Це залежить від точки зору. Система II компактніше й більш наглядна; відповідно більш компактні і докази різноманітних їх властивостей. З іншого боку, у більш багатій системі I коротше виведення різноманітних формул.

 

Правила виведення:

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

u(A)

u : ;

u(β)

2) правило висновку (Modus Ponens). Якщо u і u ® β виведені формули, то β виведена:

u, u ® β

u: .

β

У цьому описі числення висловлень аксіоми є формулами числення (відповідному визначенню формули); формули ж, використані в правилах виведення (u, u ® β і т.д.), - це ”метаформули“ або схеми формул. Так, схема формул, u ® β позначає множину всіх тих формул числення, що утворюються, якщо її метазмінні замінити формулами числення: наприклад, якщо u замінити на А, а β - на A&B, то зі схеми формул u ® β одержимо формулу А ® A&B.

 


Дата добавления: 2014-12-15; просмотров: 19 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2017 год. (0.007 сек.)