Попередня нормальна форма
Визначення 1. Формула логіки предикатів називається здійсненною в області М, якщо існують значення змінних, що входять до цієї формули і віднесених до області М, при яких формула набуває справжніх значення.
Визначення 2. Формула А називається здійсненною, якщо існує область, на якій ця формула здійсненна.
Визначення 3. Формула логіки предикатів називається тотожно істинною в області М, якщо вона набуває справжніх значення для всіх значень змінних , що входять до цієї формули і віднесених до цієї області.
Визначення 4. Формула А називається загальнозначущою, якщо вона тотожно істинна у будь-якій галузі.
Визначення 5. Формула А називається тотожно хибною в області М, якщо вона набуває хибних значень для всіх значень змінних, що входять до цієї формули і віднесених до цієї області.
З наведених визначень випливає:
- Якщо формула загальнозначима, вона і здійсненна у всякої області.
- Якщо формула тотожно істинна області, вона здійсненна у цій галузі.
- Якщо формула нездійсненна, вона тотожно хибна у будь-якій області.
Приклад 1. Довести, що формула
здійсненна.
Рішення. Для доказу здійсненності формули A досить знайти область визначення двомісного предикату P(x,y) і таке його значення, що в цій галузі формула набуває справжнього значення. Такий областю визначення предикату, в залежності, буде множиною М = N * N. Справді, якщо P(x,y) – предикат «y:x», то формула A тотожно істинна області М, і, отже, здійсненна у цій галузі. Однак, якщо як предикат P(x,y) взяти предикат «y
тобто. формула А тотожноістинна для будь-яких одномісних предикатів P(x) і Q(x) та у будь-якій області.
Приклад 3. Довести, що формула
Рішення. Оскільки формула
,
а формула , очевидно, тотожно хибна, то тотожно хибна і формула А.
Кажуть, що формула логіки предикатів має нормальну форму, якщо вона містить тільки операції кон'юнкції, диз'юнкції та кванторні операції, а операція заперечення віднесена до елементарних формул.
Серед нормальних форм формул логіки предикатів важливе значення мають так звані попередні нормальні форми. У них кванторні операції або повністю відсутні, або використовуються після всіх операцій алгебри логіки.
Справедливим є твердження про те, що будь-яка формула логіки предикатів шляхом рівносильних перетворень може бути приведена до попередньої нормальної форми (п.н.ф.). При цьому слід використовувати рівносильність логіки предикатів, які дозволяють виносити за дужки квантори існування та загальності, тобто. рівносильності
Приклад 4. Привести до п.н.ф. формулу
Рішення. Проводячи рівносильні перетворення, отримаємо