Пример неравносильных формул

Покажем, что

Вместо предикатных переменных P (x) и Q (x) подставим конкретные предикаты A (x) и B (x), определенные на N.

A (x) = “ x – четное число”, B (x) = “ x – нечетное число”

Левая часть формулы есть высказывание:

«Каждое число четно или нечетно» (которое истинно).

Правая часть – высказывание:

«Каждое натуральное число четно, либо каждое натуральное нечетно» (которое ложно).

Определение. Формулы F и H равносильны тогда и только тогда, когда формула является тавтологией:

Определение. Приведенной формой для формул логики предикатов называется такая равносильная ей формула, в которой имеются только операции , и знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Теорема. Для любой формулы логики предикатов существует приведенная форма.

Определение. Предваренной нормальной формой для формулы логики предикатов называется такая ее предваренная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т.е. формула вида , где – один из кванторов или , , а формула F не содержит кванторов и является приведенной формулой.

Замечание. Кванторы в формуле могут отсутствовать.

Теорема. Для любой формулы логики предикатов существует предваренная нормальная форма.

Примеры:

1) Приведение к нормальной (приведенной) форме.

2) Приведение к предваренной нормальной форме (пнф).

Равносильности логики предикатов, которые позволяют выносить за скобки кванторы общности и существования: