Алфавіт логіки предикатів

Алфавіт - будь-яка непорожня безліч, складається із символів.

Квантор - загальна назва для логічних операцій, що обмежують область істинності будь-якого предикату і створюють висловлювання. Найчастіше згадують:

• Квантор загальності (позначення: , читається: «для всіх…», «для кожного…» або «кожен…», «будь-який…», «для будь-якого…»).
• Квантор існування (позначення: , Читається: «існує ...» або «знайдеться ...»).

Формула - слово для моделювання висловлювання.

Правила побудови:

1) Кожна нульмісцева предикатна змінна є формулою;

2) якщо - n-місцева предикатна змінна, тобто формула, в якій всі предметні змінні вільні;

3) якщо формула, то також формула. Вільні (пов'язані) предметні змінні у формулі ті і тільки ті, які є вільними (пов'язаними) у ;

4) якщо - формули і якщо предметні змінні, що входять одночасно в обидві ці формули, вільні в кожній з них, то вирази

також є формулами. При цьому предметні змінні, вільні (пов'язані) хоча б в одній із формул називаються вільними (пов'язаними) і в нових формулах;

5) якщо - формула і - предметна змінна, що входить у вільно, то вирази і також є формулами, в яких змінна пов'язана, а решта предметних змінних, що входять у формулу вільно або пов'язано, залишаються і в нових формулах відповідно такими ж;

Правила переходу до рівносильних формул:

1) перенесенняквантора через заперечення

2) винесення квантора за дужки

3) перестановка однойменних кванторов

4) перейменування пов'язаних змінних

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

Формула F називаєтьсясуперечливою тоді і тільки тоді, коли вона помилкова при всіх інтерпретаціях (інакшенесуперечлива ).

Формула F називаєтьсязагальнозначною тоді і тільки тоді, коли вона істинна при всіх інтерпретаціях (незагальнозначна в іншому випадку).

---