Визначення. Кажуть, що формула логіки предикатів має нормальну форму, якщо вона містить тільки операції кон'юнкції, диз'юнкції і кванторние операції, а операція заперечення віднесена до елементарних формулами.
Очевидно, що, використовуючи равносильности алгебри висловлювань і логіки предикатів, кожну формулу логіки предикатів можна привести до нормальної форми. Наприклад, наведемо до нормального формі формулу
Користуючись рівносильними перетвореннями. отримаємо
Серед нормальних форм формул логіки предикатів важливе значення мають так звані упереджені нормальні форми (п.н.ф.). У них кванторние операції або повністю відсутні, або вони використовуються після всіх операцій алгебри логіки, тобто попереджання нормальна форма формули логіки предикатів має вигляд
де під сімволомпонімается один з кванторовіліа формула А кванторів не містить.
Теорема. Будь-яка формула логіки предикатів може бути приведена до попереджання нормальній формі.
Доведення. Будемо вважати, що формула вже приведена до нормальної форми і покажемо, що її можна привести до попереджання нормальній формі.
Якщо дана формула є елементарною, то вона кванторів не містить, і, отже, вже має попереджання нормальну форму.
Припустимо тепер, що теорема справедлива для формул, що містять не більше k операцій, і доведемо що при цьому припущенні вона буде справедлива і для формул. містять рівно k + 1 операцію.
Нехай формула А містить k 1 операцію і має вигляд L (х), гдеобозначает один з кванторів.
Так як L (x) містить k операцій, і, отже, її можна вважати наведеної до попереджання нормальній формі, то у неї все кванторние операції коштують попереду. Але тоді формула L (x), очевидно, має попереджання нормальну форму.
Нехай формула А має вигляд, де формула L приведена до попереджання нормальній формі і містить k операцій. Тоді за допомогою рівносильних 1 і 2 заперечення можна ввести під знак кванторів, і це призведе формулу А до попереджання нормальній формі.
Нехай формула А має вигляд, гдеіпріведени до попереджання нормальній формі.
Перейменуємо в формулі пов'язані предметні змінні так, щоб в формулахівсе пов'язані предметні змінні були різними. При цьому формулиімoгyт бути записані у вигляді
Використовуючи равносильности 7 і 1, запишемо формулу А, вводячи формулу під знаки кванторів:
Потім введемо під знаки кванторів формулу. Тоді для формули А отримаємо попереджання нормальну форму:
Аналогічно проводиться доказ і в разі, коли формула А має вигляд .
Зауваження. Якщо в процесі приведення формули логіки предикатів до п.н.ф. доводиться розглядати вираз або вираз, то слід скористатися рівносильно 5 і 10.
Наприклад, приведемо до пред вареної нормальної