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

1.

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

2. g

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

3.

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

4.

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

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

→ .

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

Літералом називатимемо атом або заперечення атома. Прикладами літералів єр,

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

Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f₁

f₂ … f_n(n≥1) і всі f_i(i=1,2,...,n) різні. Тут кожна з формул f₁,f₂,…,f_n є диз'юнкцією літералів, у якій всі атоми різні.

Приклад 1.17. Нехай p, g та r — атоми. Тодіf=(р

) ( g) -формула, записана в кон'юнктивній нормальній формі. У цій формулі f₁=(р ) та f₂=( g), тобто f₁ - диз'юнкція літералівp, , , а f₂ - диз'юнкція літералів таg.

Кажуть, що формулу f записано у диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд f=f₁

f₂ … f_n(n≥1) і всі f_i (i=1,2,...,n) різні. Тут кожна з формул f₁,f₂,…,f_nє кон'юнкцією літералів, у якій всі атоми різні.

Приклад 1.18. Нехай p, g та r - атоми. Тодіf=(

g) (p ) -формула, записана у диз'юнктивній нормальній формі. У цій формулі f₁=( g) та f₂=( p ), де f₁ - кон'юнкція літералів та g, а f₂ - кон'юнкція літералів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) (r s) - закон подвійного заперечення 6 до формули 2.

4. ((

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

5. ((

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