Читайте также: |
|
Понятие предикатной формулы(как и формулы алгебры высказываний) вводится индуктивно. Пусть x,y,z,x1,x2,… - бесконечный список переменных. Выражения вида P(x1, …,xn), Qi(x1,…,xn) называются n–местными предикатными символами. Формулами алгебры предикатов являются:
1) предикатные символы и выражения, получающиеся из предикатных символов заменой переменных другими (не обязательно различными) переменными;
2) если Φ,Ψ – формулы, х – переменная, то (ùΦ), (ΦÙΨ), (ΦÚΨ), (Φ Ψ), (Φ
Ψ), (
x Φ), (
x Φ) – формулы;
3) других формул нет.
Относительно употребления скобок принимается обычное соглашение. Формулы, определяемые первым условием, называются простыми. Другие предикатные формулы строятся из простых с помощью символов логических операций.
Примеры. 1. Формулы P(x), P3(x1,x2),Q(x,x,z) - простые.
2. Формулы (P1(x) (
xQ(y1,y2))), (((
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) – (z2=1), получим предикат местности два (2>3)
x(x>y)Ù
x(z2=1).
Формулы Φ и Ψ называются равносильными (Φ≡Ψ), если всякий раз, при замене предикатных символов на конкретные предикаты, они превращаются в равносильные предикаты.
Формула Φ называется тавтологией (╞Φ), если после любой замены предикатных символов на конкретные предикаты получаем тождественно истинный предикат.
Формулы алгебры высказываний автоматически переходят в разряд формул алгебры предикатов. Здесь все предикатные символы – 0-местные.
Следует знать теорему, которая сразу же дает возможность на основании тавтологии алгебры высказываний строить широкий класс тавтологий алгебры предикатов. Кроме того, она окажется полезной и в дальнейшем.
Теорема. Если в тавтологии алгебры предикатов расширим предикатные символы, т.е. доставим новые переменные, не находящиеся под влиянием квантора, то получим снова тавтологию алгебры предикатов.
Пример. На основании тавтологии алгебры высказываний P Q
ùP
Q строится тавтология алгебры предикатов.
P(x1,…,xn) Q(y1,…,ym)
ùP(x1,..,xn)
Q(y1,…ym).
Обратим внимание на то, что как и формулы алгебры высказываний, две предикатные формулы Φ,Ψ равносильны тогда и только тогда, когда их эквиваленция Φ Ψ является тавтологией. Таким образом, можно утверждать, что P(x1,…,xn)
Q(y1,…,ym) ≡ùP(x1,…,xn)
Q(y1,…,ym)
Кроме описанного выше примера построения тавтологий алгебры предикатов (без кванторов), студент должен знать следующие основные тавтологии с кванторами:
1. ù P(x)
xùP(x)
2. ù P(x)
xùP(x)
3. x(P1(x)ÙP2(x))
x(P1(x) Ù
x(P2(x)
4. x(P1(x)
P2(x))
x(P1(x)
x(P2(x)
5. x1,x2P(x1,x2)
x2,
x1P(x1,x2)
6. x1,
x2P(x1,x2)
x2,
x1P(x1,x2)
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)).
Для формулы алгебры высказываний мы имеем стандартные формы – дизъюнктивную и конъюнктивную нормальные формы (в частности, совершенные). Аналогично для формул алгебры предикатов вводится предваренная нормальная форма.
Формула, содержащая лишь операцииù,Ù, Ú, причем, ù относится только к простым формулам, называется приведенной. Говорят, что формула
Φ= K1x1… KnxnΨ имеет предваренную нормальную форму, если Ψ имеет приведенную форму, Ki - квантор общности или существования, 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; просмотров: 71 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Операции квантификации. | | | Язык алгебры предикатов. |