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

Елементарна формула, правильно побудовані формули, область дії квантора, інтерпретація формул логіки предикатів, загальнозначущі та суперечливі формули, логічний наслідок

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

Визначення

Якщо Р — n-місний предикат і t₁,..., t_n— терми, то P(t₁,..., t_n)називається атомом або елементарною формулою логіки предикатів. Наприклад: ДІЛИТЬСЯ(х, 13), ДІЛИТЬСЯ(х, у),БІЛЬШЕ(плюс(х, 1), х), ДОРІВНЮВАТИ(x, 1), СКЛАДАТИ(студенти, сесії).

Визначення

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

І.Атом є формулою.

2. Якщо F і G— формули, то (ØF), (F Ú G), (F Ù G),(F ® G), (F - G)також є формулами.

3. Якщо F — формула, а х — вільна змінна, то ("x) F і ($x)F теж формули.

4. Ніяких формул, крім породжених вказаними вище правилами, не існує.

Визначення

Частина формули, на яку поширюється дія квантора, називається областю дії квантора.

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

Приклад. Визначити, які змінні є зв'язаними, а які — вільними у таких формулах:

1. А(х, у).

2. $у (B(х) ® "x A(x, у)).

3. $х (В(х) ® "x A(x, у)).

Розв'язок. Обидві змінні у формулі 1 є вільними. У формулі 2 змінна у є зв'язаною, а змінна х— і зв'язаною, і вільною (змінна х вільна у предикаті В(х) і зв'язана у предикаті А(х, у)).15 формулі 3 змінна х є зв'язаною, а змінна у — вільною.

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

Визначення

Інтерпретація формули F логіки предикатів складається з елементів непорожньої предметної області D, значень всіх констант, функціональних символів і предикатів, що зустрічаються в F. Вказані значення задаються таким чином:

1. Кожній константі ставиться у відповідність деякий елемент з D.

2. Кожному n-місному функціональному символу ставиться у відповідність відображення з Dⁿ у D. Тут Dⁿ = (х₁, x₂,..., х_п),де х₁,..., х_п Î D.

3. Кожному n-місному предикату ставиться у відповідність відображення з Dⁿ в {І, X}.

Для кожної інтерпретації на області D формула може одержати істиннісне значення І або X згідно з такими правилами:

1. Якщо задані значення формул F і G, то істиннісні значення формул (ØF), (F Ú G), (F Ù G), (F ® G), (F ~ G) одержуються за допомогою таблиць істинності відповідних логічних операцій.

2. Формула ("x)F одержує значення І, якщо F одержує значення І для кожного х з D, у протилежному випадку вона одержує значення X.

3. Формула ($x)F одержує значення І, якщо F одержує значення І хоча б для одного х з D, у протилежному випадку вона одержує значення X.

4. Формула, що містить вільні змінні, не може одержати істиннісне значення.

Після уточнення поняття інтерпретації в логіці предикатів такі поняття, як загально значущість, суперечливість, здійсненність, нейтральність (незагальнозначущість) формули і логічний наслідок можуть бути визначені точно як для формул логіки висловлень (див. п. 5.2, 5.3).

Запитання

1. Дайте визначення атома у логіці предикатів.

2. Що називається формулою в логіці предикатів?

3. Сформулюйте поняття інтерпретації формули логіки предикатів.

4. Що розуміють під областю дії квантора?

5. Порівняйте поняття інтерпретації у логіці висловлень і логіці предикатів.

6. Назвіть види формул логіки предикатів залежно від прийнятих ними істиннісних значень.

7. Запишіть правила, згідно з якими формула логіки предикатів може одержати істиннісне значення.

Завдання

1. Нехай предикат М(х, у) означає «х менше у»,предикат D(х, у)— «х дорівнює у», а предикат S(x, у, z)— «х = у + z». Наведені висловлення сформулюйте природною мовою:

а) ("x) М(0, х);

б) ("x) S(x, x, х);

в) ($x) М(х, х - 1);

г) Ø(($х) S(x, x, x));

д) ($y)($х) S(x, у, z);

e) ($y)("x) (D(х, у)Ú М(х, у));

ж)("х)("у)(S(x, у, у)® М(у, х)).

2. Нехай X — множина співробітників відділу, а Р(х), Q(x) і R(х)— предикати, що означають відповідно: х займається спортом, х вивчає іноземну мову, х має винаходи, х Î X. Розшифруйте:

а) ($х) P(x)Q(x);

б) ("x) P(x)(Q(x) ® R(x)).

3. Вказати вільні і зв'язані входження змінних у такі формули, що містять предикати А і В:

а) ("x₂) A(x₁, х₂);

б) ("x₃)(("x₁)A(x₁, х₂) А(х₃, х₁);

в) ("x₂) А(х₃, х₂) ® "x₃ В(х₃, х₂);

г) ("x₂) А(x₁, х₂) ® $х₁ А(x₁, х₂);

д) ($x₂)("x₁) А(x₁, х₂)® B(х₁).

4. Задано предметну область В = {1, 2},значення констант a і b,функціональних символів f, а також предиката Р:

Знайти істиннісні значення таких предикатних виразів:

а) Р(а, f(a))Ù Р(b, f(.b));

б) ("x)("y)(P(x, у) ® P(f(x), f(y))).

5. Оцінити формулу ("х)(Р(х)) ® Q(f(x), а)на інтерпретації

.