ФОРМУЛИ ЛОГІКИ ПРЕДИКАТІВ. ІНТЕРПРЕТАЦІЯ ФОРМУЛ. ВИКОНУВАНІ ТА ЛОГІЧНО ЗАГАЛЬНОЗНАЧУЩІ ФОРМУЛИ

Алфавітом логіки предикатів є наступні категорії символів:

1) предметні змінні;

2) предметні константи;

3) функціональні символи (і – порядковий номер, n – кількість аргументів);

4) предикатні символи (і – порядковий номер, n – кількість аргументів;

5) знаки логічних операцій: ;

6) знаки пунктуації «(», «)».

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

Формулами логіки предикатів є:

1) будь-які елементарні формули;

2) формули, отримані наступним чином , де і – формули логіки предикатів;

3) якщо формула логіки предикатів, а вільна змінна цієї формули, то слова і також є формулами логіки предикатів.

4) всі інші слова, крім тих, які утворюються за правилами 1)-3), не є формулами логіки предикатів.

Приклад 1. Перевірити, чи утворюють наступні слова формули логіки предикатів: « », « ».

Слово не є формулою логіки предикатів, оскільки є формулою згідно пунктів 1)-3), але в цій формулі змінна є частково вільною, а тому навішування квантора існування не відповідає пункту 3) і, згідно 4), слово не утворює формулу логіки предикатів.

Слово утворює формулу логіки предикатів. Дійсно, слова і є формулами згідно пункту 1). А слова , і є формулами логіки предикатів згідно пункту 2). Отже формула є формулою логіки предикатів.

Формула, яка не має вільних входжень предметних змінних, називається замкнутою. В протилежному випадку формула є відкритою.

Інтерпретацією формули логіки предикатів називається система, яка складається з непорожньої множини , яку називають областю інтерпретації, і деякої відповідності, яка кожному предикатному символу ставить у відповідність певний n-місний предикат, заданий на множині М, кожному функціональному символу – деяку n-арну операцію, кожній константі – деякий конкретний елемент із .

Приклад 2. Побудувати деяку інтерпретацію для формули .

Наша формула містить тримісний предикат, один функціональний символ, дві вільні та одну зв’язану змінну. За область інтерпретації оберемо множину всіх дійсних чисел. Функціональному символу поставимо у відповідність унарну операцію піднесення до квадрата . Предикатний символ позначимо тримісним предикатом « ». В цій інтерпретації ми отримали формулу , яка буде виконуватись на тих наборах дійсних чисел, для яких і .

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

Якщо формула логіки предикатів істинна в будь-якій інтерпретації, то така формула називається загальнозначущою або логічно загальнозначущою (ЛЗЗ). Якщо формула логіки предикатів хибна в будь-якій інтерпретації, то вона називається тотожно хибною. В інших випадках формула логіки предикатів називається виконуваною (спростовною).

Інтерпретація називається моделлю для даної множини Г формул логіки предикатів, якщо кожна формула з Г істинна в даній інтерпретації.

Якщо ми маємо деяку формулу алгебри висловлення , то при застосуванні підстановки , де – довільні формули логіки предикатів, ми отримаємо деяку формулу логіки предикатів (це не важко довести). Це правило дає можливість на основі тотожно істинних формул алгебри висловлень будувати, використовуючи правило підстановки, загальнозначущі формули логіки предикатів.

Приклад 3. Формула логіки предикатів

є загальнозначущою, оскільки одержана підстановкою

,

застосованою до формули алгебри висловлень , що є законом контрапозиції.

Приклад 4.Чи буде формула логіки предикатів виконуваною? ЛЗЗ?

Знайдемо умови, які повинні задовольняти предикати в інтерпретації. Припустимо, що існує інтерпретація на множині М: . Тобто і існують інтерпретації предикатних символів і - і - такі, що:

.

Це рівносильно системі умов:

Останню систему можна переписати так:

Умови системи не суперечать одна одній. Тобто: повинен бути спростовним і на всіх значеннях множини інтерпретації, де набуває хибних значень, також повинен набувати хибних значень, або бути тотожно хибним.

Наприклад, нехай =« » і =« » на множині . Одержимо формулу , яка набуває істинних значень на всіх цілих числах . Таким чином - виконувана.

Можна розглянути інтерпретацію нашої формули на одноелементній множині . На цій множині та перейдуть відповідно в і , які позначимо і . Тоді матимемо формулу алгебри висловлень, яка є спростовною. Дійсно:

.

Остання формула алгебри висловлень є спростовною. Отже, задана формула логіки предикатів не є істинною в даній інтерпретації, і, як наслідок, не є ЛЗЗ.

Приклад 5.Довести, що формула логіки предикатів є ЛЗЗ.

Припустимо, що наша формула є спростовною. Тобто існує така інтерпретація на деякій множині М, на якій предикатні символи і мають інтерпретації і , і .

Остання рівність рівносильна системі

Використовуючи означення операцій квантування та імплікації прийдемо до рівносильної системи

яка містить суперечність. Отже наше припущення про спростовність формули є невірним. А тому вона є логічно загальнозначущою.

ВПРАВИ.

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

a) ;

b) ;

c) ;

d) .

3.15. Записати наведені нижче математичні твердження за допомогою формул логіки предикатів:

a) існують такі дійсні числа x, y, z, що ;

b) будь-який опуклий чотирикутник має площу;

c) якщо кожна з двох прямих паралельна третій, то вони паралельні між собою;

d) для довільного дійсного числа х: ;

e) існують три точки, що не належать одній прямій.

3.16. Побудувати інтерпретації для наступних формул:

a) ;

b) ;

c) ;

d) .

3.17. Записати деяку інтерпретацію формули над множиною і записати таблицю значень отриманого предиката:

a). ;

b). ;

c). .

3.18. Навести приклад формули F логіки предикатів, для якої виконується наступна умова:

a). F є тотожно істиною на всіх скінченних множинах і виконуваною на всіх нескінченних;

b). F є виконуваною на деякій нескінченній множині і тотожно хибною на всіх скінченних множинах;

c). F виконувана на скінченних множинах з парною кількістю елементів і тотожно хибна на всіх інших скінченних множинах.

3.19. Перевірити, чи буде формула логіки предикатів логічно загальнозначущою:

a) ;

b) ;

c)

d) ;

e) ;

f)

g) ;

h)

i) .

3.20. Перевірити, чи буде виконуваною формула логіки предикатів:

a) ;

b) ;

c) ;

d) ;

e) ;

f) ;

g)

h) ;

i)

j) .

Поиск по сайту: