Реферат: Алгебра висловлень
Імплікація
Логічне слідування
Використовуватимемо перші з наведених назв та позначень. Нижче подано таблицю 2, що містить означення цих операцій.
Таблиця 2
| Ù | 0 | 1 | Ú | 0 | 1 | Ø | 0 | 1 | ® | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Застосовуючи до елементарних висловлень і пропозиційних змінних означені операції, діставатимемо складені висловлення , яким відповідатимуть так звані формули або вирази алгебри висловлень. Для запису цих формул, дослідження їхніх властивостей і співвідношень між формулами та висловленнями використовують формальні мови, тобто певні множини слів у деякому алфавіті.
Алфавіт найбільш поширеної формальної мови алгебри висловлень складається з трьох груп символів:
1) символи елементарних висловлень та пропозиційних змінних: a ,b ,c ,... і x ,y ,z ,... (можливо з індексами);
2) символи операцій: Ù,Ú,Ø,® ;
3) допоміжні символи - круглі дужки: ( і ).
З пропозиційних змінних і елементарних висловлень за допомогою операцій і дужок будуються пропозиційні формули або просто формули алгебри висловлень за такими індуктивними правилами:
1) всі пропозиційні змінні та елементарні висловлення є формулами;
2) якщо A і B - формули, то вирази (A ÙB ), (A ÚB ), (ØA ), (A ®B ) також є формулами;
3) інших формул, ніж побудовані за правилами 1) і 2), немає.
Традиційно формули алгебри висловлень позначають великими готичними літерами, але для зручності позначатимемо їх великими латинськими літерами.
Кожна формула A зображує форму або схему складеного висловлення: вона перетворюється у висловлення якщо замість її пропозиційних змінних підставити будь-які висловлення. Оскільки кожне з підставлених висловлень має значення 0 або 1, то послідовно обчислюючи значення всіх підформул формули A , одержимо значення формули A на цьому наборі висловлень, яке дорівнюватиме 0 або 1. Підставляючи у формулу A замість її пропозиційних змінних інший набір висловлень, аналогічним чином обчислимо нове значення формули A і т.д. Оскільки кожне з висловлень набору повністю характеризується своїм значенням (істинно або хибно, тобто 1 або 0), то замість пропозиційних змінних у формулу можна підставляти не самі висловлення, а їхні значення - 1 або 0.
Нехай p 1 ,p 2 ,...,pn - це всі пропозиційні змінні, що входять у формулу A ; будемо позначати цей факт A (p 1 ,p 2 ,...,pn ). Формулі A (p 1 ,p 2 ,...,pn ) поставимо у відповідність функцію f (p 1 ,p 2 ,...,pn ), що означена на множині Bn (B ={0,1}) і приймає значення у множині B , тобто функцію типу Bn ®B . Значення функції f на наборі значень a 1 ,a 2 ,...,an її змінних p 1 ,p 2 ,...,pn дорівнює значенню формули A (p 1 ,p 2 ,...,pn ) при підстановці в неї замість пропозиційних змінних p 1 ,p 2 ,...,pn значень a 1 ,a 2 ,...,an відповідно.
Зауважимо, що кількість елементів в області визначення функції f дорівнює 2n , тобто |Pr1 f |=2n .
Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності може бути побудована так звана таблиця істинності цієї функції (див.таблицю 3).
Таблиця 3
| p 1 p 2 ...... pn -1 pn | f (p 1 ,p 2 ,...,pn -1 ,pn ) |
|
0 0 ... 0 0 0 0 ... 0 1 0 0 ... 1 0 0 0 ... 1 1 ......................... 1 1 ... 1 0 1 1 ... 1 1 |
f (0,0,...,0,0) f (0,0,...,0,1) f (0,0,...,1,0) f (0,0,...,1,1) ..................... К-во Просмотров: 314
Бесплатно скачать Реферат: Алгебра висловлень
|