Предикатні формули
Предикатні формули (формули логіки предикатів) вводяться так:
всяка елементарна формула є предикатна формула:
якщо А і В - предикатні формули, то суть предикатні формули. Якщо А — предикатна формула і предметна змінна, то суть предикатні формули;
вираз є предикатна формула в тому випадку, якщо воно є елементарною формулою або побудовано з елементарних формул послідовним застосуванням правил а) та b).
Предикатні формули, які є елементарними формулами, називаються складовими предикатними формулами.
Для позначення формул логіки предикатів вживатимемо великі літери латинського алфавіту, надруковані жирним шрифтом: А, В, С, Р, Q і т.д.
У формулах формула А називається областю дії кванторів відповідно.
Зазвичай беруть угоди про опускання дужок. Крім того, вважають, що квантори пов'язують сильніше за інші операції. Тому формулу можна записати так: .
ВИЗНАЧЕННЯ. Предикатна формула називається загальнозначущою, якщо після заміни елементарних формул, що входять до неї, будь-якими предикатами виходить тотожно істинний предикат.
ВИЗНАЧЕННЯ. Предикатні формули називаються рівносильними, якщо після заміни елементарних формул, що входять до них, будь-якими предикатами виходять рівносильні предикати. Записувати рівносильність формул А і будемо так: .
Легко довести, що предикатна формула є загальнозначущою тоді і тільки тоді, коли А і В — рівносильні предикатні формули.
Цілий ряд рівносильностей логіки предикатів можна отримати з рівносильності логіки висловлювань. Наприклад, рівносильностям логіки висловлювань
відповідають рівносильності логіки предикатів
Аналогічно, тотожноСправжні формули логіки висловлювань є джерелом для отримання загальнозначимих формул логіки предикатів. Наприклад, тавтології відповідає загальнозначуща формула логіки предикатів. Дійсно, підставивши в будь-яку конкретну формулу А замість предикатних символів, що входять до неї, довільні предикати, отримаємо деякий предикат. При цьому формула перетвориться на предикат який набуває значення І при будь-яких допустимих значеннях змінних (через закон виключеного третього в логіці висловлювань).
Розмірковуючи так само, можна довести інші загальнозначущі формули та рівносильності логіки предикатів, перенесені з логіки висловлювань.
Крім загальнозначимих формул і рівносильностей логіки предикатів, одержуваних таким чином, існують специфічні загальнозначущі формули та рівносильності, пов'язані із застосуванням кванторів. Деякі їх ми розглянемо.