Курсовая работа: Математична логіка

Наведені еквівалентності можна перевірити побудовою таблиць стинності. Приклад 1.14 свідчить, що імплікація не комутативна. Покажемо, як застосувати закони логіки висловлювань для доведення еквівалентності формул.

Приклад 1.15. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→(gr) та (p→g)(p→r). Випишемо послідовність перетворень та запишемо біля кожного рядка назву застосованого закону або правила.

1. (gr) - правило вилучення мплікації з першої із заданих формул.

2. (g)(r) - закон дистрибутивності 9б для формули 1.

3. (р→g)(p→r) - правило введення імплікації для формули 2.

Отже, задані формули еквівалентні: р→(gr) та (p→g)(p→r).

Приклад 1.16. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→g та →. Цю еквівалентність називають правилом контрапозиції.

1.  g - правило вилучення мплікації у першій із заданих формул.

2.  g - закон комутативності 1а для формули 1.

3.   - закон подвійного заперечення 6 для формули 2.

4.       → - правило введення імплікації для формули 3.

Отже, задані формули еквівалентні: р→g=→.

1.3. Нормальні форми логіки висловлювань.

Літералом називатимемо атом або заперечення атома. Прикладами літералів є р, , r. Літерал називають позитивним, якщо він не має знака заперечення, та негативним, якщо він має знак заперечення. Пару літералів {p, } називають контрарною парою.

Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f1f2…fn(n≥1) і всі fi (i=1,2,...,n) різні. Тут кожна з формул f1,f2,…,fn є диз'юнкцією літералів, у якій всі атоми різні.

Приклад 1.17. Нехай p, g та r — атоми. Тоді f=(р)(g) - формула, записана в кон'юнктивній нормальній формі. У цій формулі f1=(р) та f2=(g), тобто f1 - диз'юнкція літералівp, , , а f2 - диз'юнкція літералів  таg.

Кажуть, що формулу f записано у диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд f=f1f2…fn(n≥1) і всі fi (i=1,2,...,n) різні. Тут кожна з формул f1,f2,…,fn є кон'юнкцією літералів, у якій всі атоми різні.

Приклад 1.18. Нехай p, g та r - атоми. Тоді f=(g)(p) - формула, записана у диз'юнктивній нормальній формі. У цій формулі f1=(g) та f2=( p), де f1 - кон'юнкція літералів  та g, а f2 - кон'юнкція літералівp,  та .

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

Крок 1. Використати правила f→g=g та f~g=(f→g)(g→f) (див. параграф 1.2) для усунення логічних зв'язок "→" та "~".

Крок 2. Використати закон подвійного заперечення та закони де Моргана для перенесення знаку заперечення безпосередньо до атомів.

Крок 3. Використати відповідні закони дистрибутивності закони для побудови нормальної форми. Для побудови кон'юнктивної нормальної форми використати закон дистрибутивності для диз'юнкції відносно кон'юнкції (закон 3а з табл. 1.8). Для побудови диз'юнктивної нормальної форми використати закон дистрибутивності для кон'юнкції відносно диз'юнкції (закон 3 б з табл. 1.8).

Приклад 1.19. Побудуємо диз'юнктивну нормальну форму формули ((p)→r)(→s). Наведемо послідовність кроків для побудови ДНФ та застосовані закони.

1. (r)() - усунення логічної зв'язки "→" із заданої формули.

2.  (()r)() - закон де Моргана 8а до формули з рядка 1.

3.  ((g)r)(rs) - закон подвійного заперечення 6 до формули 2.

4.  ((g)(rs))(r(rs)) - закон дистрибутивност 3б до формули 3.

5.  ((gr)(gs))((rr)(rs)) - закон дистрибутивності 3б до формули 4.

6.  (gr)(gs)(rr)(rs) - асоціативний закон 2а до формули 5.

7.  (gr)(gs)r(rs) - закон ідемпотентності 7б до формули 6.

Ми одержали ДНФ. Звернемо увагу, що її можна спростити, якщо двіч використати закон поглинання 9б: диз'юнктивний член к поглинає члени (gr) та (rs). Отже, ДНФ задано формули ((p)→r)(→s) також буде (gs)r. Останні міркування свідчать, що ДНФ певної формули, якщо казати загалом, не єдина.

Приклад 1.20. Побудуємо кон’юнктиву нормальну форму формули (р(g→r))→s. Наведемо послідовність кроків побудови КНФ і застосовані закони та правила.

1.   - усунення логічної зв'язки "→" з заданої формули.

2.  s - закон де Моргана 8б до формули 1.

3.  ()s - закон де Моргана 8а до формули 2.

4.  (g)s - закон подвійного заперечення 6 до формули 3.

5.  s(g) - закон комутативності 1а до формули 4.

6.  (s)(g) - закон асоціативності 2а до формули 5.

7.  (gs)(s) - закон дистрибутивност За до формули 6.

Формула (gs)(s) є КНФ формули (р(g→r))→s.

Розділ ІІ: Логіка предикатів.

2.1. Основні поняття логіки предикатів.

Як уже відзначалось під час вивчення логіки висловлювань, існують речення, які не є висловлюваннями та містять змінні. Був наведений приклад речення "х+1=3". Речення зі змінними не є висловлюваннями, але перетворюються в них, якщо надати значення змінним. Речення зі змінними дуже поширені. Вони містяться в математичних формулах та комп'ютерних програмах. Зокрема, у мовах програмування зустрічаються оператори такого змісту "повторювати цикл доти, поки змінні х та у не стануть рівними, або припинити обчислення циклу після 100 повторень". Якщо позначити через лічильник повторень, то умова закінчення програми задаватиметься виразом "(x=y)(i>100)", а сам оператор матиме вигляд "повторювати, якщо (¬((x=y)(i>100)))"

Страницы: 1, 2, 3, 4