Нормальные формы формул логики предикатов.
В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т.е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.
Определение.
Говорят, что формула логики предикатов имеет приведенную нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.
Пример 1.
.
Получили приведенную нормальную форму исходной формулы.
Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид
,
где под символом понимается один из кванторов или , а формула А кванторов не содержит.
Процедура получения (приведения) ПНФ. Состоит в следующем:
1. Используя формулы 18, 19 (отнесенные к предикатам), заменить операции и ~ на .
2. Используя формулы логики предикатов 31, 32, а также формулы логики высказываний 1, 16, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).
3. Для формул, содержащих подформулы вида , вести новые переменные, позволяющие использовать соотношения 46, 47, 49, 50 или 53, 54.
4. С помощью формул 35 – 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.
Пример 2.
обозначим в предикате Q переменную y через z
Пример 3.
обозначим в предикате Q переменную x через z
– ПНФ.
Пример 4.
последний предикат не зависит от переменной z
два первых предиката не зависят от переменной u - ПНФ.
Пример 5.
Дата добавления: 2022-05-27; просмотров: 89;