2.2.3. Рівносильні формули. Нормальні форми.

Приклад 1. Чи рівносильні формули логіки предикатів :

1. ;

2. ;

3. .

►а) Формули утворюють окремий випадок закону контрапозиції алгебри висловлень висловлень , тому вони рівносильні b) Оскільки фрмули рінносильні, якщоїх еквіваленція є тавтологією ⊨ , то при доведенні можна користуватись однією із схем прикладу 8 попереднього параграфа. Нехай існує, інтерпретація, у якій ліва частина Це можливо, коди предикат Р(х)→Р(у₀)спростовний. Тобто, існує елемент що . Звідси і . Отже предикат Р(x) спростовний і виконуваний. Але тоді і права частина, у цій інтерпретації . Тому формули не рівносильні. Далі для доведення рівносильності формул можна використовувати раніше виведені рівносильності і намагатись звести ліву і праву частини до однакового вигляду. Наприклад, ,a . Очевидно, що формули виду та не можуть бути рівносильними. с) Перетворимо ліву та праву частини: .

Очевидно, що формули не рівносильні. Легко навести приклад відповідної інтерпретації. Нехай Р(х)="х>5”_, Q(x)="x>10" - спростовні предикати на N.Тоді предикат Р(х)→Q(x) спростовний, бо перетворюється в хибне висловлення, наприклад, при х = 7. Тому ліва частина хибна, а права у цій же інтерпретації ◄

Приклад 2. Записати зведену форму формул логіки предикатів та перетворити її на випереджену:

1. та ;

2. ;

с) ;

d) ;

e) ;

f) ;

g) .

• а) Виразимо імплікацію через диз’юнкцію та скористаємось законами де Моргана для кванторів: та .Отримали зведені форми даних формул. Винести квантор загальності за дужки у першій формулі не можна, оскільки нема дистрибутивного закону для диз’юнкції. Потрібно у одному з доданків перейменувати змінну х якоюсь іншою буквою: . Далі по черзі проносимо квантори загальності через диз’юнкцію: - ВНФ. У другій формулі використовуємо відповідний дистрибутивний закон для квантора існування: – ВНФ

b)

- зведена форма. Квантор існування по х та zможна пронести через диз’юнкцію, а змінну у в області дії квантора перейменуємо на t:

.

с)

- зведена форма. Квантори поу та zможна винести за дужки, а змінну х в області дії квантора загальності перейменуємо: - ВНФ.

d)

- зведена форма. Щоб винести квантор загальності по y за дужки, в області дії цього квантора замінимо у на z : - ВНФ.

е)

- зведена форма.

- випереджена нормальна форма. Тут у перших дужках квантор існування пронесли через диз’юнкцію, а у другому множнику зробили заміну зиінних і пронесли усі квантори почергово через кон’юнкцію.

f)

- ВНФ, матриця якої записана у кон’юнктивній нормальній формі. Така форма називається клаузальною.

g)

- ВНФ.◄

Приклад 3. Записати сколемівські стандартні форми (ССФ) для всіх формул з прикладу 2.

► а) Префікс не містить кванторів існування, тому сколемівська форма рівносильна самій формулі : . У другій формулі замість х підставимо деяку сталу а: .

b) Перші два квантори існування вилучаємо, замінивши змінні х та zдеякими сталими а та b: .

с) Спочатку замість х вводимо сталу а : . Перед квантором існування по z є квантор загальності по у, тому замість z вводимо деяку сколемівську функцію z=f(y):

d) .

e) .

f) Тут потрібно замість х ввести деяку функцію :

.

g) .◄