yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.2. Предваренные нормальные формы

Математическая логика

5.2. Предваренные нормальные формы

Определение 6.1. Формула А находится в предваренной нормальной форме (ПНФ), если она имеет вид: (Q1,x1,)...(Qnxn)M, где каждое Q1x1 есть х1 или x1, а М - формула, не содержащая кванторов. (Q1x1);..(Qnxn) называется префиксом, а М - матрицей формулы А.

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

Доказательство теоремы конструктивно. Докажем теорему индукцией по числу связок m.

1. Пусть m=0. Тогда формуле А не содержит связок и находится в ПНФ,

2. Предположим, что существует ПНФ для формулы В с числом связок m<n. Докажем, что существует ПНФ для, формулы А с числом связок n.

1 случай. Существует ПНФ для B=(Q1x1)...(Qnxn)M. Формула А образована из В с помощью операции отрицания: A=(Q1,xl)...(Qnxn)M. По законам де Моргана связка проносится через кванторы: ¬xMx¬M, ¬xMx¬M. Полученная формула будет находиться в ПНФ.

2 случай. Формула А образована из двух формул В1 и В2 с числом связок <n, с помощью связок & или v: (Qlxl)...(Qnxn)Ml&(Q1y1)...(Qnyn)M2 или (Q1 x1)…(Qnxn)Mlv(Qly1)...(Qnyn)M2. Тогда, если формулы В1 и В2 имеют кванторы по одной и той же переменной, используем законы замены связанных переменных, так чтобы ни одна свободная переменная не стала связанной в результате этой замены. После этого воспользуемся законами пронесения кванторов (12) - (17) и законами коммутативности.

3 случай. Формула А образована из В навешиванием квантора  или . Тогда, поскольку В находится в ПНФ, вновь полученная формула будет в ПНФ.

Пример. Рассмотрим посылки примера 4.2.

x(P(x)& y(D(y) L(x,y)))= x(P(x)& y(D(y)vL(x,y)))=

х(Р(х)& у(D(у)vL(х,у)))= х(у(D(у)vL(х.у))&Р(х))=xy((D(y)vL(x,y))&P(x)) - ПНФ.

x(P(x) y(Q(y) ¬L(xy)))= x(P(x)vy(Q(y}v¬L(x,y)))=

x(y(Q(y)v¬L(x,y))vP(x))= xy(Q(y)v¬L(x,y)vP(x)) - ПНФ.

 

32