Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Равносильные формулы | Некоторые логические законы | Нормальные формы | Логическое следствие | Применение к переключательным схемам | Теория L. Аксиомы и правила вывода | Общезначимость теорем. Непротиворечивость L | Полнота теории L | Понятие предиката. | Простейшие логические операции над предикатами. |


Читайте также:
  1. Формулы. Булевы функции

 

Понятие предикатной формулы(как и формулы алгебры высказываний) вводится индуктивно. Пусть 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)) xQ(x)

9. x(PÙQ(x)) 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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Операции квантификации.| Язык алгебры предикатов.

mybiblioteka.su - 2015-2024 год. (0.017 сек.)