Математична логіка (стр. 5 из 8)

6. (

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

7. (

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

Ми одержали ДНФ. Звернемо увагу, що її можна спростити, якщо двічі використати закон поглинання 9б: диз'юнктивний член к поглинає члени (

g r) та (r s). Отже, ДНФ заданої формули ((p )→r) ( →s) також буде ( g s) 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. (

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

Формула (

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

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

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

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

(i>100)", а сам оператор матиме вигляд "повторювати, якщо (¬((x=y) (i>100)))"

Приклад 2.1. Прикладами речень, які містять змінні є "х>3", "x=y+3", "x+у=z". Ці речення ні істинні, ні фальшиві доти, поки змінні не одержать значення.

У наведеному прикладі речення "х>3", або, в іншій формі, "х більше 3" складається з двох частин: першу, змінну х, називають предметом, другу - "більше 3", - яка вказує властивість предмета, називають предикатом. Часто предикатом називають все речення.

Уведемо логіку першого ступеня (логіку предикатів), в якій до понять логіки висловлювань додано нові поняття. Для формулювання складних думок у логіці висловлювань уведено атоми як основні елементи, з яких будують формули. Атом розглядався як неподільне ціле - його структура та склад не аналізувались. У той же час існує багато міркувань, які неможливо описувати лише за допомогою висловлювань. Тому введемо поняття атома у логіці першого ступеня. Для запису атомів логіки першого ступеня використовують такі типи символів:

1) Індивідні символи або сталі - це імена об'єктів, які починаються з великої букви: Іван, Марія та сталі: Т, F або 3.

2) Предметні символи - імена змінних, які позначають малимибуквами, можливо, з індексами: х,у,z,v_i,w_j.

3) Предикатні символи — імена, якими позначають предикатита записують великими буквами: Р,Q, R, або змістовними словами,які записують великими буквами БІЛЬШЕ, ЛЮБИТЬ тощо.