Предикатные формулы.

Понятие предикатной формулы(как и формулы алгебры высказываний) вводится индуктивно. Пусть x,y,z,x₁,x₂,… - бесконечный список переменных. Выражения вида P(x₁, …,x_n), Q_i(x₁,…,x_n) называются n–местными предикатными символами. Формулами алгебры предикатов являются:

1) предикатные символы и выражения, получающиеся из предикатных символов заменой переменных другими (не обязательно различными) переменными;

2) если Φ,Ψ – формулы, х – переменная, то (ùΦ), (ΦÙΨ), (ΦÚΨ), (Φ Ψ), (Φ Ψ), ( x Φ), ( x Φ) – формулы;

3) других формул нет.

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

Примеры. 1. Формулы P(x), P₃(x₁,x₂),Q(x,x,z) - простые.

2. Формулы (P₁(x) ( xQ(y₁,y₂))), ((( xQ(x,y)) ((ùP(x,z)) ( xP))) записаны без применения соглашения об употреблении скобок.

3. Формулы yP(x,y,z) ùQ(y,y) Q(x,y) R(x) записаны с учетом соглашения о применении скобок.

Замена n–местных предикатных символов на конкретные предикаты, зависящие от тех же переменных, дает некоторый предикат.

Пример. Подставим в формулу P xQ(x,y)Ù xR(z) вместо P - (2>3), вместо Q(x,y) - (x>y), вместо R(z) – (z²=1), получим предикат местности два (2>3) x(x>y)Ù x(z²=1).

Формулы Φ и Ψ называются равносильными (Φ≡Ψ), если всякий раз, при замене предикатных символов на конкретные предикаты, они превращаются в равносильные предикаты.

Формула Φ называется тавтологией (╞Φ), если после любой замены предикатных символов на конкретные предикаты получаем тождественно истинный предикат.

Формулы алгебры высказываний автоматически переходят в разряд формул алгебры предикатов. Здесь все предикатные символы – 0-местные.

Следует знать теорему, которая сразу же дает возможность на основании тавтологии алгебры высказываний строить широкий класс тавтологий алгебры предикатов. Кроме того, она окажется полезной и в дальнейшем.

Теорема. Если в тавтологии алгебры предикатов расширим предикатные символы, т.е. доставим новые переменные, не находящиеся под влиянием квантора, то получим снова тавтологию алгебры предикатов.

Пример. На основании тавтологии алгебры высказываний P Q ùP Q строится тавтология алгебры предикатов.

P(x₁,…,x_n) Q(y₁,…,y_m) ùP(x₁,..,x_n) Q(y₁,…y_m).

Обратим внимание на то, что как и формулы алгебры высказываний, две предикатные формулы Φ,Ψ равносильны тогда и только тогда, когда их эквиваленция Φ Ψ является тавтологией. Таким образом, можно утверждать, что P(x₁,…,x_n) Q(y₁,…,y_m) ≡ùP(x₁,…,x_n) Q(y₁,…,y_m)

Кроме описанного выше примера построения тавтологий алгебры предикатов (без кванторов), студент должен знать следующие основные тавтологии с кванторами:

1. ù P(x) xùP(x)

2. ù P(x) xùP(x)

3. x(P₁(x)ÙP₂(x)) x(P₁(x) Ù x(P₂(x)

4. x(P₁(x) P₂(x)) x(P₁(x) x(P₂(x)

5. x₁,x₂P(x₁,x₂) x₂, x₁P(x₁,x₂)

6. x₁, x₂P(x₁,x₂) x₂, x₁P(x₁,x₂)

7. x(P Q(x)) P xQ(x)

8. x(PÙQ(x)) PÙ xQ(x)

9. x(PÙQ(x)) PÙ xQ(x)

10. x(P Q(x)) P xQ(x)

Продолжая подчеркивать параллелизм между алгебрами высказываний и предикатов, отметим, что для формул алгебры высказываний и алгебры предикатов вводится понятие равносильных преобразований, причем, если в формуле Φ_Ψ с выделенной подформулой Ψ заменить эту подформулу на равносильную X, то получим формулу Φ_x, равносильную исходной.

Пример. Для формулы Φ=(ùP(x) xQ(x,y)) построить равносильную, которая не содержит операций , , .

Последовательно имеем:

Φº(ùP(x) xQ(x,y))Ù( xQ(x,y) ˥P(x))≡(ù ù P(x)

xQ(x,y))Ù(ù xQ(x,y) ùP(x)≡

≡(P(x) ù xùQ(x,y))Ù( xùQ(x,y) ù P(x)).

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

Формула, содержащая лишь операцииù,Ù, Ú, причем, ù относится только к простым формулам, называется приведенной. Говорят, что формула

Φ= K₁x₁… K_nx_nΨ имеет предваренную нормальную форму, если Ψ имеет приведенную форму, K_i - квантор общности или существования, 1≤i≤n - различные переменные, 1≤j≤n

Существует алгоритм приведения произвольной формулы к приведенной нормальной форме.

1. Используя соотношения Φ Ψ≡(Φ Ψ)Ù(Ψ Φ), Φ Ψ≡ùΦ Ψ избавляемся от знаков , .

2. С помощью законов де Моргана и их обобщения ù(Φ Ψ)= ùΦÙùΨ, ù(Φ^Ψ)=ùΦ ùΨ), ù xP(x)= xùP(x), ù$хP(x)≡ xùP(x) отнесем знак ù непосредственно к предикатным символам. Четное количество знаков: ùперед предикатным символом можно отбросить, а нечетное заменить одним (закон двойного отрицания).

3. Вынесем кванторы , к началу формулы так, чтобы действие каждого квантора распространялось на все выражение, стоящее справа. Для этого пользуемся тавтологиями, содержащими кванторы, под номерами 3,4, 7-10. при этом связанные кванторами переменные иногда целесообразно переименовывать.

4. Производим упрощение формулы, если это возможно.

Примеры. Привести формулу к предваренной нормальной форме.

1. Φ=(ùP(y) ù _iQ(x,y))≡ ùùP(y) ù yQ(x,y)≡P(y) yùQ(x,y)≡P(y) Ú

Ú zùQ(x,z)≡ z(P(y) ùQ(x,z))

Здесь сначала избавились от операции , затем, воспользовавшись обобщенным законом де Моргана, знак ù внесли под квантор, при этом символ поменяли на . закон двойного отрицания позволил нам отбросить два знака ù пред предикатным символом P(y). Следующее преобразование связано с применением тавтологии 10 (вернее, ее обобщение). Но перед этим, во избежание «столкновения» переменных, пришлось связанную квантором переменную у заменить на z, так как для у мы имеем свободное вхождение в P(y), а связанную переменную можно переименовать.

2. Φ= x yP(x,y) ù x yQ(x,y)≡ x yP(x,y) x yùQ(x,y)≡

≡ x( yP(x,y) yùQ(x,y))≡ x y(P(x,y) zùQ(x,z))) ≡ x y (P(x,y)

zùQ(x,z)) ≡ x y z (P(x,y) ù Q(x,z)).

Контрольные вопросы и упражнения

1. Указать свободное и связное вхождение переменных в следующие формулы:

а) ;

б) .

2. Какие из следующих выражений являются формулами алгебры предикатов?

а) ;

б) ;

в) ;

г) .

3. Привести доказательство тавтологий с кванторами (1-10).

4. Доказать следующие законы пронесения квантора всеобщности через эквиваленцию:

а) ;

б) .

5. Доказать следующие законы пронесения квантора существования через импликацию:

а) ;

б) ;

в) .

6. Привести равносильными преобразованиями к предваренной нормальной форме следующие формулы:

а) ;

б) ;

в) ;

г) .

7. Доказать, что если формула алгебры предикатов Ф, содержащая свободно только переменную х, является тавтологией, то формула также является тавтологией, и обратно.

8. Если формула алгебры предикатов Ф, содержащая свободно только переменную х, является тавтологией, то формула также является тавтологией. Верно ли обратно?

9. Доказать, что:

а) если формула является тавтологией, формулы и также являются тавтологиями;

б) если формула является тавтологией, формулы и также являются тавтологиями.

Дата добавления: 2015-11-14