Визначення 8. Формула А логіки предикатів називається здійсненним в області М, якщо існують значення змінних входять в цю формулу і віднесених до області М (інакше - існує модель), при яких формула А приймає дійсні значення.
Определеніе9. Формула А логіки предикатів називається здійсненним. якщо існує область, на якій ця формула здійсненна.
Визначення 10. Формула А логіки предикатів називається тотожно-істинною в області М (здійсненним), якщо вона приймає дійсні значення для всіх значень змінних, що входять в цю формулу і віднесених до цієї області.
Визначення 11. Формула А логіки предикатів називається загальнозначущої. якщо вона тотожна істинна на кожній окрузі (на будь-якої моделі).
Якщо дві рівносильні формули логіки предикатів з'єднати знаком еквіваленціі. то отримана формула буде приймати значення І для будь-якого набору змінних в будь-якій області, тобто буде загальнозначущої.
Це поняття є узагальненням поняття тотожною істинності формули логіки висловлювань. Всі логічні закони, представлений в логіці висловлювань формулами є загальнозначущими формулами логіки предикатів і висловлюють, як і інші загальнозначущі формули, закони логіки на мові логіки предикатів.
Общезначімость формули логіки предикатів, наприклад, F позначається # 9500; F. Все загальнозначущі формули можуть бути джерелами нових # 9500; формул. Наприклад, підставляючи в закон виключеного третього - замість х предикат Р (х1, ..., хn), отримуємо общезначимую формулу Р (х1, ..., хn) (х1, ..., хn). При n = 1 маємо общезначимую формулу. і, таким чином, - загальнозначуща формула логіки предикатів.
З тотожно істинною формули логіки висловлювань підстановкою замість х предиката Р (х, y), а замість y- предиката Q (x, y) отримуємо общезначимую формулу і т. Д.
Визначення 12. Формула А логіки предикатів називається тотожно хибною в області М, якщо вона приймає помилкові значення для всіх значень змінних, що входять в цю формулу і віднесених до цієї області (іншими словами, на даній моделі).
Визначення 13. Формула А логіки предикатів називається тотожно хибною (нездійсненним), якщо вона тотожно помилкова на кожній окрузі (на будь-якої моделі).
Наприклад, формула є тотожно хибною (нездійсненним) формулою логіки предикатів.
З наведених визначень з очевидністю випливає:
1. Якщо формула А общезначима, то вона і здійсненна на кожній окрузі (моделі).
2. Якщо формула А тотожно істинна в області М, то вона і здійсненна в цій області.
3. Якщо формула А тотожне помилкова в області М. то її не реалізовано в цій області.
4. Якщо формула А нездійсненна, то вона тотожно помилкова на кожній окрузі (на будь-якої моделі).
5. Для того, щоб формула А логіки предикатів була общезначима, необхідно і достатньо, щоб її заперечення було здійсненно.
6. Для того, щоб формула А логіки предикатів була здійсненним, необхідно і достатньо, щоб формула була общезначима.
Приклад 1. Довести равносильность (логічне тотожність):
Помітивши, що в кожній з кванторних подформул обидві предметні змінні пов'язані і що, таким чином, вони є висловлюваннями, введемо позначення:
В = або позначивши першу і другу предметні змінні через n1 і n2, відповідно:
У цих позначеннях заданий для розгляду тотожність буде виглядати так:.
Провівши рівносильні перетворення, можемо переконатися в справедливості цієї тотожності:
Якщо охарактеризувати розглядається вираз в цілому, то бачимо, що це загальнозначуща формула.
Приклад 2. Визначити тип формули.
Нехай Р (х). "Число х - парне -" предикат, визначений в М = N 2.
Таким чином, розглянута формула на даній моделі є наступне твердження: "Серед натуральних чисел існують як парні, так і непарні". Очевидно, що цей вислів істинно і, таким чином, на даній моделі формула F тотожно істинна.
Однак, якщо цей же предикат поставити на множині M = NхN, де N - безліч парних чисел, то формула F на такій моделі виявиться тотожне помилковою.
З огляду на викладене, робимо висновок, що розглянута формула F здійсненна (але не общезначима).
Приклад 3. Для формули підібрати модель, на якій вона є тотожно істинною (і, таким чином, в цілому здійсненним).
Нехай Р (x, x, y): "x · x = y", або інакше "x 2 = y" - предикат, визначений на множині натуральних чисел, тобто М = N. Тоді розглянута формула виражає твердження про існування натурального квадрата натурального числа, що, очевидно, є істиною, тобто на даній моделі формула тотожно істинна, що й треба було довести.
Приклад 4. Розглянемо формулу. Це здійсненне формула. Дійсно, якщо Р (х, y, x): "x + y = x" - предикат суми, то на M = N існує підстановка замість y відповідного значення, що дає значення істинності цієї формули. Очевидно, це y = 0, оскільки в цьому випадку отримуємо "х = х".
Якщо ж P (x, y, x): "xy = x" - предикат твори, то таким значенням y є y = 1, так як при ньому отримуємо справжнє висловлювання.
Але це єдині підстановки, що призводять до вірних тверджень, що і говорить саме про здійсненності даної формули (але не про її общезначимости).
Приклад 5. Чи є загальнозначущої формула:?
Нехай P (x, y) - предикат порядку (бінарного відношення) "", певний на кінцевій множині натуральних чисел M1. Тоді при підстановці в формулу замість вільної змінної y величини ми отримаємо істинне твердження, а при підстановці будь-який інший константи з безлічі М1 - помилкове. Таким чином, розглянута формула не є загальнозначущої.
Приклад 6. Розглянемо формулу. Покажемо, що вона нездійсненна.
Припустимо противне, тобто що вона здійсненна. Це означає, що існує така безліч М і такий конкретний предикат в ньому, що коли. то дана формула перетворюється в такий конкретний предикат. який, в свою чергу, перетворюється в істинне висловлення при всякій підстановці замість y елементів з безлічі М. Візьмемо будь-який. Тоді висловлювання істинно, як ми тільки що встановили. Отже, істинні висловлювання і.
З істинності другого висловлювання робимо висновок, що висловлювання істинно (оскільки "для всіх предметних змінних", як би вони не позначалися). Але це суперечить істинності першого висловлювання.
Таким чином, наше припущення про здійсненності формули невірно.
Проблема можливості розв'язання в логіці предикатів ставиться так само, як і в алгебрі логіки: чи існують алгоритми, що дозволяють для будь-якої формули А логіки предикатів встановити, до якого типу (класу) вона відноситься, тобто чи є вона загальнозначущої, здійсненним або тотожне помилковою (нездійсненним). Якби такий алгоритм існував, то, як і в алгебрі висловлювань, він зводився б до критерію тотожною істинності будь-якої формули логіки предикатів. Відзначимо, що, на відміну від алгебри логіки, в логіці предикатів не застосовують метод перебору всіх варіантів значень змінних, що входять в формулу, так як таких варіантів може бути безліч.
Обчислення предикатів - приклад нерозв'язною формальної системи. Нерозв'язність числення предикатів довів в 1936 р американський логік Алонзо Черч. У доведеною їм теоремою йдеться про відсутність ефективної процедури при вирішенні питання щодо довільної формули формальної системи, що містить арифметику натуральних чисел, чи є ця формула теоремою.