Курсовая работа: Математична логіка
Літералом називатимемо атом або заперечення атома. Прикладами літералів єр, 
, r. Літерал називають позитивним, якщо він не має знака заперечення, та негативним, якщо він має знак заперечення. Пару літералів {p, 
} називають контрарною парою.
Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f1 
f2 …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=f1 f2 …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)", а сам оператор матим