logo
Elektr_prak_po_DM

1.3. Виды форм логики предикатов

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

Пусть P(х), Q(х) и U(x,y) – переменные предикаты. Тогда имеют место равносильности:

x P(x)  x P(x)

x P(x)  x P(x)

(x P(x) y Q( y))  x P(x)  y Q(y)

(x P(x)  y Q(y))  x P(x)  y Q(y)

  x P(x)  x P(x)

  x P(x)  x P(x)

x y U(x, y)  y x U(x, y)

x y U(x, y)  y x U(x, y)

x y U(x, y)  y x U(x, y)

x y U(x, y)  y x U(x, y)

x x Q(x)  x Q(x)

x x Q(x)  x Q(x)

x (P(x)  P(x))  x P(x)

x (P(x)  P(x))  x P(x)

x P(x)  y U(y)  xy (P(x)  U(y))

x P(x)  x U(x)  x (P(x)  U(x))

x P(x)  y U(y)  xy (P(x)  U(y))

x P(x)  x U(x)  x (P(x)  U(x))

x P(x)  x U(x)  x (P(x)  U(x))

x P(x)  x U(x)  x  a (P(x)  U(a))

x P(x)  x U(x)  x (P(x)  U(x))

x P(x)  x U(x)  x a (P(x)  U(a))

x P(x)  x U(x)  xa (P(x)  U(a))

x P(x)  x U(x)  xa (P(x)  U(a))

В логике предикатов различают два вида форм: приведенную и предваренную.

Говорят, что формула логики предикатов имеет приведенную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются перед всеми операциями алгебры логики.

Алгоритм получения ПНФ:

  1. выразите операции импликации и эквиваленции через конъюнкцию, дизъюнкцию и отрицание;

  2. внесите символы отрицания так, чтобы они относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме);

  3. для формул, содержащих подформулы вида: x P(x)  x U(x), xP(x)  xU(x), xP(x)  xU(x), xP(x)  xU(x) введите новые связанные переменные;

  4. используя свойства и законы логики предикатов, вынесите все кванторы перед высказыванием и получите формулу в виде ПНФ.

Примеры выполнения заданий