A®B; B®C; C 6 страница

Упростить формулу.

1) удалить логическую связку “®”:

F=ù("_x(ùP₁(х)ÚùP₂(х)))Úù($_x(P₁(х)) &"_x(P₂(х)));

2) выполнить операцию отрицания формулы:

F=$_x(ù(ùP₁(х)ÚùP₂(х))))Ú "_x(ùP₁(х))Ú$_x(ùP₂(х)));

3) выполнить операцию отрицания формулы:

F=$_x(P₁(х)&P₂(х))Ú"_x(ùP₁(х))Ú$_x(ùP₂(х)));

4) применить закон дистрибутивности по квантору $_x:

F=$_x(P₁(х)&P₂(х)ÚùP₂(х))Ú"_x(ùP₁(х));

5)применить закон дистрибутивности к формуле:

F=$_x((P₁(х)ÚùP₂(х))&(P₂(х)ÚùP₂(х)))Ú"_x(ùP₁(х));

6) применить закон исключенного третьего и свойство констант для логической связки “&”:

F=$_x((P₁(х)ÚùP₂(х)))Ú"_x(ùP₁(х));

7) применить закон де Моргана:

F=$_x((P₁(х)ÚùP₂(х)))Úù$_x(P₁(х));

8) применить закон дистрибутивности по квантору $_x:

F=$_x(P₁(х))Ú$_x(ùP₂(х))Úù$_x(P₁(х));

9) применить закон исключенного третьего:

F=$_x(ùP₂(х))Úи;

10) применить свойство констант для логической связки “Ú”:

F=и,

т.е. формула F="_x(P₁(х)®ùP₂(х))®ù($_x(P₁(х))&"_x(P₂(х))) является тождественно истиной.

 

2.1.4 Предваренная нормальная форма

Для облегчения анализа сложных суждений формулы алгебры предикатов рекомендуется приводить к нормальной форме. Если в алгебре высказываний приняты две нормальные формы (ДНФ - дизъюнктивная и КНФ -конъюнктивная), то в алгебре предикатов - одна предваренная нормальная форма (ПНФ), суть которой сводится к разделению формулы на две части: кванторную и безкванторную. Для этого все кванторы формулы выносят влево, используя законы и правила алгебры предикатов.

В результате этих алгебраических преобразова­ний может быть получена формула вида: Â_x1 Â_x2 ¼Â_xn(M), где ÂÎ{"; $}, а М – матрица формулы. Кванторную часть формулы Â_x1 Â_x2 ¼Â_xnиногда называют префиксом ПНФ.

В последующем матрицу форму­лы преобразуют к виду КНФ, что облегчает механизм по принципу резолюции.

Пример:

F=$_x"_y((P²₁.(х; y)ÚùP₂.(х))&P₃(y)) формула, приведенная к ПНФ; F="_x(P²₁.(х; y)Ú$_x(P₂ (х))&$_y(P₃ (y)) формула, неприведенная к ПНФ.

"_x(P₁.(х)) &"_x(P₂(x))="_x(P₁.(х) &P₂(x)) слева от знака равенства формула, неприведенная к ПНФ, а справа, равносильная ей формула, но приведенная к ПНФ.

 

2.1.4.1 Алгоритм приведения формулы к виду ПНФ

Шаг 1. Исключить всюду логические связки «и ® по правилам:

(F₁«F₂)=(F₁®F₂)& (F₂®F₁)=(ùF₁ÚF₂)&(ùF₂ÚF₁);

(F₁®F₂)=(ù F₁ÚF₂);

Шаг 2. Продвинуть отрицание до элементарной формулы по правилам:

ù"x(F)=$x(ùF); ù(F₁ÚF₂)=(ùF₁&ùF₂);

ù$x(F)="x(ùF);. ù(F₁&F₂)=(ùF₁ÚùF₂);

Шаг 3. Переименовать связанные переменные по правилу:

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

Шаг 4. Вынести кванторы влево по законам алгебры логики.

Шаг 5. Преобразовать бескванторную матрицу к виду КНФ. Алгоритм приведения матрицы формулы к виду КНФ приведен в алгебре высказываний.

 

Пример: F=("_x(P₁ (х)®"_y(P₂ (y)®P₃ (z))))&(ù"_y(P²₄ (x; y)®P₅.(z))).

Привести формулу к виду ПНФ.

l) удалить логические связки “®”:

F=("_x(ùP₁ (х)Ú"_y(ù P₂ (y)ÚP₃ (z))))&(ù"_y(ù P²₄ (x; y)ÚP₅.(z)));

2) применить закон де Моргана ù "_x(F(x))=$_x ù F(x)):

F=("_x(ùP₁.(х)Ú"_y(ù P₂ (y)ÚP₃ (z))))&($_y(ù(ù P²₄ (x; y)ÚP₅.(z)));

3) применить закон де Моргана ù(F₁ÚF₂)=(ùF₁&ùF₂):

F="_x(ùP₁.(х)Ú"_y(ù P₂ (y)ÚP₃ (z)))&($_y(P²₄ (x; y)&(ùP₅.(z))));

4) переименовать связанную переменную x=w:

F="_w(ùP₁ (w)Ú"_y(ù P₂ (y)ÚP₃ (z)))&($_y(P²₄ (x; y)&(ù P₅.(z))));

5) переименовать связанную переменную y=v:

F="_w(ùP₁ (w)Ú"_v(ùP₂ (v)ÚP₃ (z)))&($_y(P²₄ (x; y)&(ùP₅.(z))));

6) вынести квантор "_v влево:

F="_w"_v(ùP₁ (w)ÚùP₂ (v)ÚP₃ (z))&($_y(P²₄ (x; y)&(ùP₅.(z))));

7) вынести квантор $_y влево:

F="_w"_v$_y(ùP₁ (w)ÚùP₂ (v)ÚP₃ (z))&P²₄ (x; y)&ùP₅.(z).

Матрица ПНФ содержит три элементарных дизъюнкта:

K={(ùP₁ (w)ÚùP₂ (v)ÚP₃ (z)); P₄ (x; y); ùP₅.(z)}.

Пример: F = "_x(P₁ (х)«$_x(P₂ (x)))®"_y(P₃.(y)).

Привести формулу к виду ПНФ.

1) удалить логические связки “«”:

F="_x((P₁ (х)®$_x(P₂ (x)))&($_x(P₂ (х))®P₁ (x)))®"_y(P₃.(y));

2) удалить логические связки “®”:

F=ù("_x((ùP₁.(х)Ú$_x(P₂ (x)))&(ù$_x(P₂.(х))ÚP₁ (x)))Ú"_y(P₃.(y));

3) применить закон ù"x(F(x))=$x(ùF(x)):

F=$_x(ù((ùP₁.(х)Ú$_x(P₂ (x)))&(ù$_x(P₂ (х))ÚP₁ (x))))Ú"_y(P₃.(y));

4) применить закон де Моргана ù(F₁&F₂)=(ùF₁ÚùF₂):

F=$_x((ù(ùP₁ (х)Ú$_x(P₂ (x)))Ú(ù(ù$_x(P₂.(х))ÚP₁ (x))))Ú"_y(P₃.(y));

5) применить закон де Моргана ù(F₁ÚF₂)=(ùF₁&ùF₂):

F=$_x((P₁ (х)&(ù$_x(P₂ (x))))Ú($_x(P₂ (х))&(ùP₁ (x))))Ú"_y(P₃.(y));

6) применить закон ù$_x(F(x))= "_x (ùF(x)):

F=$_x((P₁ (х)&"_x(ùP₂.(x)))Ú($_x(P₂ (х))&(ùP₁ (x))))Ú"_y(P₃.(y));

7) переименовать связанную переменную x=z:

F=$_z((P₁.(z)&"_x(ù P₂ (x)))Ú($_x(P₂.(х))&(ùP₁.(z))))Ú"_y(P₃.(y));

8) переименовать связанную переменную x=w:

F=$_z(P₁ (z)&"_w(ùP₂ (w))Ú$_x(P₂ (х)&ùP₁ (z)))Ú"_y(P₃.(y));

9) вынести квантор "_w, $_x и "_y влево:

F=$_z"_w$_x"_y(P₁ (z)&ùP₂ (w)ÚP₂ (х)&ùP₁ (z)ÚP₃.(y));

10) преобразовать матрицу к виду КНФ:

F=$_z"_w$_x"_y((P₁ (z)ÚP₂ (х)ÚP₃.(y))&(ùP₂ (w)ÚP₂ (х)ÚP₃.(y))& (ùP₂ (w)ÚùP₁ (z)ÚP₃.(y))).

Матрица ПНФ содержит три элементарных дизъюнкта:

K={(P₁ (z)ÚP₂ (х)ÚP₃.(y)); (ùP₂ (w)ÚP₂ (х)ÚP₃.(y)); (ùP₂ (w)ÚùP₁ (z)ÚP₃.(y))}.

Пример: F="_x$_y(P²₁ (х; y))&ù($_x"_y(P²₂(x; y))).

Привести формулу к виду ПНФ.

1) применить закон ù$_x(F(x))="_x(ùF(x)):

F="_x$_y(P²₁(х; y))&("_xù("_y(P22(x; y))));

2) применить закон ù"_x(F(x))= $_x(ùF(x)):

F="_x$_y(P²₁(х; y))&("_x$_y(ù(P²₂(x; y))));

3) вынести квантор "_x по закону дистрибутивности:

F="_x($_y(P²₁(х; y))&$_y(ù(P²₂(x; y))));

4) переименовать связанную переменную y=v:

F="_x($_z(P²₁(х; z))&$_y(ù(P²₂(x; y))));

5) вынести кванторs $_z и $_y влево:

"_x$_z$_y(P²₁(х; z)&ùP²₂(x; y)).

Матрица ПНФ содержит два элементарных дизъюнкта:

K={P²₁(х; z); ùP²₂(x; y)}.

 

Пример: M=P₁(z)&ùP₂(w)ÚP₂(х)&ùP₁.(z)ÚP₃.(y);

1) по закону дистрибутивности:

M=P₁.(z)&ùP₂ (w)Ú(P₂ (х)ÚP₃.(y))&(ù P₁ (z)Ú(P₃.(y));

2) по закону дистрибутивности:

M=(P₁.(z)&ùP₂.(w)ÚP₂.(х)ÚP₃.(y))&(P₁.(z)&ùP₂.(w)ÚùP₁.(z)Ú P₃.(y));

3) по закону дистрибутивности:

M =(P₁.(z)ÚP₂.(x)ÚP₃.(y))&(ù P₂.(w)ÚP₂.(x)ÚP₃.(y))&

(P₁.(z)ÚùP₁.(z)ÚP₃.(y))&(ùP₂.(w)ÚùP₁.(z)ÚP₃.(y));

4) по закону исключенного третьего:

M=(P₁.(z)ÚP₂.(x)ÚP₃.(y))&(ùP₂.(w)ÚP₂.(x)ÚP₃.(y))&

&(ù P₂.(w)ÚùP₁.(z)ÚP₃.(y)).

Матрица содержит три элементарных дизъюнкта:

K={(P₁.(z)ÚP₂.(x)ÚP₃.(y)); (ùP₂.(w)ÚP₂.(x)ÚP₃.(y)); (ù P₂.(w)ÚùP₁.(z)ÚP₃.(y))}.

Дизъюнкты матрицы содержат контрарные атомы P₁.(z) и ùP₁.(z), P₂.(x) и ùP₂.(w), свободные переменные которых могут быть одинаковыми или разными.

 

2.1.5 С колемовская стандартная форма

Наличие разноимен­ных кванторов усложняет вывод заключения. Поэтому рассмотрим класс формул, содержащих только кванторы всеобщности. Фор­мула F называется "; - формулой, если она представлена в ПНФ и содержит только кванторы всеобщности, т.е.

F = ";_x1 ";_x2 ¼ ";_xn (M).

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

 

2.1.5.1 Алгоритм Сколема

Шаг 1. Представить формулу F в виде ПНФ, т.е.

F =Âx₁Âx₂¼Âx_n(M), где Â_iÎ{"; $}Шаг 2. Найти в префиксе самый левый квантор существования:

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

б) если квантор находится не на первом месте префикса, т.е. ";_x1 ";_x2¼"_xi-1 $ _xi.., то выбрать (i-1)-местный функциональный символ, отлич­ный от функциональных символов матрицы М и выполнить замену предметной переменной x_i, связанной кванто­ром существования, на функцию f(x₁;x₂;¼ x_i-1) и квантор существования удалить.

Шаг 3. Найти следующий справа квантор существования и перей­ти к исполнению шага 2, иначе конец.

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

Пример:

F=$_x1"_x2"_x3$_x4"_x5$_x6 ((P²₁ (x₁; x₂) ÚùP³₂(x₃; x₄; x₅))&P ²₃(x₄; x₆)).

1) заменить предметную переменную x₁ на постоянную a:

F="_x2"_x3$_x4"_x5$_x6 ((P²₁. (a; x₂)ÚùP³₂.(x₃; x₄; x₅))&P²₃ (x₄; x₆));

2) заменить предметную переменную x₄ на функцию f² ₁.(x₂;x₃):

F="_x2"_x3"_x5$_x6 ((P²₁.(a; x₂)ÚùP³₂ (x₃; f ²₁(x₂; x₃); x₅))&P²₃ (f²₁(x₂; x₃); x₆));

4) заменить предметную переменную x₆ на функцию

f³₂(x₂; x3; x₅):

F="_x2"_x3"_x5((P²₁(a; x₂)ÚùP³₂(x₃; f²₁(x₂; x₃); x₅))&

&P²₃(f²₁(x₂; x₃);f³₂(x₂; x₃; x₅))).

К={(P²₁(a; x₂)ÚùP³₂(x₃; f²₁(x₂; x₃); x₅)); P²₃(f²₁(x₂; x₃);f³₂(x₂; x₃; x₅))}.

 

2.2. Исчисление предикатов

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

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

 

 

2.2.1 Интерпретация формул

Под интерпретацией следует понимать систему, состоящую из не­пустого множества V, называемом универсумом, и однозначного отображения на двухэлементное множество {и; л}, кото­рое каждому предикатному символу Pⁿ (t₁; t₂;¼ t_n) ставит в соот­ветствие n - местное отношение на множестве V, каждому функциональному символу f ⁿ_i (t₁; t₂;¼ t_n) - n-местную операцию на множестве V, каждой предметной постоянной - элемент множе­ства V.

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

Например, если универсум задан множеством целых чисел, то для $_x $_y $_z (P²(+(x, y); z)):= “существуют числа x, y, z, для которых z больше суммы чисел х и у", то при х=2, у=3, z=10 имеем двухместную операцию =5 и двухместное отношение между целым числом 10 и значением операции +(2,3)=5. Отображение P²(5;10) на двухэлементное множество дает значение “и”. При х=2, у=3, z=4 имеем +(2,3)=5 и P²(5; 4)=л.

На рис. 10 приведена графическая интерпретация этой задачи.

 

 

 

Рис.10 Интерпретация $_x $_y $_z (P²(+(x, y); z)) для x=2, y=3, z=10 или z=4.

 

Другими словами, интерпретация функциональных символов опре­деляется по значениям функции на универсуме, заданном на множестве термов, входящих аргументами в эту функ­цию, а интерпретация предикатных символов по отображению на двухэлементное множество {и; л}.

Особо следует рассмотреть влияние свободных переменных на интерпретацию формул исчисления предикатов.

Формула, не содержащая свободных переменных, называется замк­нутой и представляет собой высказывание об элементах, функциях и отношениях, которое принимает значение и или л. На рис. 10 рассмотрен случай замкнутой формулы.

Формула, содержащая свободные переменные, называется открытой и представляет собой отношений, заданное на множестве V,

Это отношение может быть истинным для одних значений из области интепретации и ложным для других.

При такой интерпретации выделяют три класса формул, тождест­венно истинные, тождественно ложные и выполнимые.

Тождественно истинные формулы (или тавтологии) -это особый класс формул исчисления предикатов, которые принимают значение “истины” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; эти формулы иг­рают роль законов и аксиом исчисления предикатов; любые подстановки и замещения в тождественно истинной формуле не изменяют ее значения.

Например,

для предиката P²(x, y):=”число x меньше числа y” формула "_x$_y(P²(x, y)):=”для любого целого числа x найдется число y, большее числа x” является тождественно истинной;

для любой F(x) формула $_x(F(x))«ù"_x(ùF(x)):=“формула ”существуют x, для которых F(x)=и”, эквивалентна формуле “не для всех x F(x)=л”” является тождественно истинной.

Тождественно ложные формулы (или противоречие)-это особый класс формул исчисления предикатов, которые принимают значение “ложь” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; любые подстановки и замещения в тождественно ложной формуле не изменяют ее значения.

Например, для предиката P²(x, y):=”число x меньше числа y” формула $_x"_y(P²(x, y)):=”существует целое число x, которое меньше любого целого числа y” является тождественно ложной;

для любой F(x) формула $_x(F(x))&"_x(ùF(x)):=”“существует x, для которой F(x)=и”, и “для всех x F(x)=л ”” является тождественно ложной.

Выполнимые формулы - это особый класс формул исчисления преди­катов, которые принимают значение “истина”в некоторой области, т.е. не для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов.

Например, формула $_x(F(x))®ù"_x(F(x)) является истинной для одного элемента множества V и ложной для всех элементов этого множества, т.к.

$_x(F(x))®ù"_x(F(x)):=” если существует x, для которого F(x)=и, то не для всех х универсума F(x)=и”.

 

2.2.2 Правила вывода

Вывод заключения из множества посылок записывается так же, как в исчислении высказываний

F₁;F₂;¼F_n|¾ B, где слева от знака “|¾” записывают множество формул посылок и необходимые аксиомы F₁;F₂;¼F_n, а справа – формулу заключения B. Тогда знак “|¾” означает “верно, что B выводима из F₁;F₂;¼F_n.

Отношение логического вывода эквивалентно теореме

|¾F₁;F₂;¼F_n®B.

Другая форма записи: F₁; F₂;¼F_n

B,

где над чертой записывают множество посылок и аксиом F₁;F₂;¼F_n, а под чертой заключение B.

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

 

2.2.2.1 Правила подстановки

Если в формулу F(х), содержащей свободную переменную x, выполнить всюду подстановку вместо x терма t, то получим формулу F(t).

Этот факт записывают так:

 

_xò^tF(x)

F(t).

 

Подстановка некоторого терма t в формулу F(x) вместо ее свободной переменной x состоит в замещении всех свободных вхождений этой переменной данным термом t. Такая подстановка называется правильной. Подстановка будет неправильной если в результате подстановки сколемовской функции свободная переменная окажется в области действия квантора.

Например,

1. _x1ò^x2$_x3(P²₁(x₁, x₃)® P₂ (x₂))

$_x3(P²₁(x₂, x₃)® P₂ (x₂)).

Это правильная подстановка, т.к. x₁ –свободная переменная.

 

2. _x1ò^{f(x2, t)} $_x3(P²₁(x₁, x₃)® P₂ (x₂))

$_x3(P²₁(f(x2, t), x₃)® P₂ (x₂)).

Это - правильная подстановка, т.к. x₁ –свободная переменная.

3. _x3ò^x2$_x3(P²₁(x₁, x₃)® P₂ (x₂))

$_x3(P²₁(x₁, x₂)® P₂ (x₂)).

Это - неправильная подстановка, т.к. x₃ –связанная квантором $.

4. _x2ò^x3$_x3(P₁(x₁, x₃)® P₂ (x₂))

$_x3(P₁(x₁, x₃)® P₂ (x₃)).

Это - неправильная подстановка, т.к. предикат P₂ (x₃) попадает в область действия квантора $.

Понятие правильной подстановки необходимо, например, для формулировки законов снятия квантора общности

"_x F(x)

F(t)

 

и введения квантора существования

F(t)

$_xF(x).

 

 

2.2.2.2 Правила введения и удаления кванторов

Наиболее распространенными правилами являются:

1) Введение квантора общности: “если F₁(t)® F₂(x) выводимая формула и F₁(t) не содержит свободной переменной x, то F₁(t)® "x(F₂(x)) также выводима”, т.е.

(F₁(t)® F₂(x))

(F₁(t)® "_x(F₂(x))).

2) Удаление квантора общности: "если "_x(F(x)) выводимая формула, то вместо x можно выполнить подстановку терма t, свободного от x, и получить также выводимую формулу F (t), т.е.