Точно Не проект 2 / Не books / Источник_1

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

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

Таблица 3.1 – Таблица истинности простейших высказываний

чение A B ). Например, импликацией будет высказывание: “Если я пойду на стадион (А), то встречу друга (В)”. В импликации первый элемент А называется антецедентом (лат. аntecedens – предшествующий), а второй элемент В – консеквентом (consequens – последующий). Высказывание

A B называется двойной импликацией (эквиваленцией) и читается “если и только если А, то В”. Это высказывание истинно тогда и только тогда, когда А и В имеют одно и то же истинностное значение. Эквиваленцией будет следующее высказывание: “Я пойду на стадион (А), тогда и только тогда, когда встречу друга (В)”. Для обозначения эквиваленции употребляется также знак .

Сложные высказывания, составленные из исходных высказываний (обозначаемых пропозициональными буквами) и знаков логических операций, называют формулой. Так высказывание “Если 30 делится на 2 и на 3, то 30 делится на 6 “ можно записать в виде формулы A B C . Данная формула будет соответствовать не только конкретному высказыванию, упомянутому выше, но и множеству всех других высказываний, имеющих подобную структуру. Поэтому исчисление высказываний не рассматривает конкретное содержание высказываний, а занимается анализом и синтезом формул и изучением отношений между формулами.

Множество базовых элементов Т исчисления высказываний состоит

из:

1)пропозициональных переменных – А, В, С,…;

2)логических констант – “истина”(И) и “ложь”(Л);

3)символов логических операций – , , , , ;

4)скобок – ( ).

ППФ исчисления высказываний определяются с помощью следующих правил:

1)всякая пропозициональная буква есть ППФ;

2)логические константы И и Л – это ППФ;

3)если F1 и F2 ППФ, то F1,F1 F2 ,F1 F2 ,F1 F2 ,F1 F2 – также ППФ;

4)других правил образования ППФ нет.

Правила 1) и 2) определяют элементарные формулы (атомы), а пра-

вило 3) указывает, как из элементарных формул строить новые формулы. Пусть формула F состоит из атомов А1,А2,…,Аn. Под интерпретацией

формулы будем понимать приписывание атомам А1,А2,…,Аn истинностных значений. Если в формуле имеется n различных атомов, то можно задать 2n интерпретаций формулы.

Среди формул исчисления высказываний выделяют формулы, которые истины во всех интерпретациях. Данные формулы называются тавтологиями или общезначимыми формулами. Примерами тавтологий являются:A A , A A . Чтобы в этом убедиться, необходимо составить таблицы истинности. Для указания того, что формула является тавтологией, используется знак |= . Например, |=(A B) (B C) A C .

Формула исчисления высказываний называется противоречием, если она принимает значение “ложь” во всех интерпретациях. Примером противоречия является A A .

Тавтологии играют особую роль в исчислении высказываний. Различные подстановки в тавтологию, независимо от их конкретного содержания, всегда дают истинные высказывания. Поэтому тавтологии рассматривают как логически истинные схемы рассуждений, которые играют роль законов исчисления высказываний. Ясно, что всегда можно установить, является ли данная формула тавтологией, построив ее таблицу истинности. С другой стороны, формула не является тавтологией, если она принимает значение “ложь” хотя бы на одном наборе значений переменных. Это обстоятельство используется для распознавания тавтологий методом обратного рассуждения, заключающемся в поиске таких значений переменных, при которых формула оказывается ложной.

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

Две формулы называют равносильными (эквивалентными), если они принимают одинаковые значения на всех наборах входящих в них переменных (интерпретациях). Для обозначения равносильности применяется знак (или знак тождества , или знак равенства =), например, F1 F2 .

82 Глава 4

Две формулы равносильны, если их двойная импликация (эквиваленция)

гда истинное значение, т.е. |=(A B) (A B). Следовательно, импликация может быть выражена через дизъюнкцию и отрицание:

(A B) (A B).

Отношение равносильности позволяет выражать одни логические операции через другие. Например, эквивалентны следующие формулы (законы де Моргана):

A B A B ,

A B A B .

Отметим, что данные записи не являются формулами исчисления высказываний, так как знак не входит в множество Т. Эти записи представляют собой высказывания о формулах логики, выраженные на метаязыке, на котором изучается логика.

Процесс дедуктивного вывода базируется на понятии логического следования. Формула В является логическим следствием формулы А (пи-

шут A B или A |= B), если В истинна на всех наборах значений переменных (интерпретациях), на которых истинна А. Можно показать, что A B, если и только если импликация A B является тавтологией, т.е. |= A B. Иными словами, из истинности А всегда следует истинность В, но если А ложно, то относительно В ничего нельзя утверждать. Понятие логического следствия можно обобщить на совокупность высказываний

A1 A2 ... An B ,

т.е. В логически следует из истинных высказываний А1,А2,…,Аn. Иными

словами, В выводимо из А1, А2,…, Аn, т.е. А1, А2,…, Аn В.

Можно также показать, что формула В является логическим следствием последовательности формул А1, А2,…, Аn тогда и только тогда, когда формула

является противоречием. Таким образом, доказательство того, что формула В является логическим следствием конечной последовательности формул А1, А2,…, Аn, сводится к доказательству общезначимости формулы

A1 A2 ... An B (3.2)

или доказательству противоречивости формулы (3.1).

Для доказательства общезначимости необходимо показать, что в любой интерпретации I, в которой истинны А1, А2,…, Аn , В также истинно. Если в формуле имеется n переменных, то необходимо будет построить таблицу истинности на 2n входов, что приведет к экспоненциальному росту времени вычисления в зависимости от n. Поэтому на практике чаще применяют второй способ, соответствующий методу обратного рассуждения.

Задачей вывода является образование из некоторой совокупности исходных тавтологий новых формул, которые также являются тавтологиями. Существует бесконечное множество тавтологий, а значит и законов логики высказываний. Тавтологии формируют систему аксиом исчисления высказываний (множество А в определении ФС). В общем, не все общезначимые формулы могут быть выведены из произвольного множества тавтологий. В то же время доказано, что можно выбрать такую систему исходных тавтологий (аксиом исчисления высказываний), из которых выводимы все общезначимые формулы. Наиболее часто используют систему аксиом П.С. Новикова [25]:

1)A (B A);

2)(A (B C)) ((A B) (A C));

3)(A B) A;

4)(A B) B ;

5)(A (B (A B));

6)A (A B);

7)B (A B);

8)(A C) ((B C) ((A B) C));

9)(A B) ((A B) A);

10)A A.

Данная система аксиом обладает следующими важными свойствами: полнотой, непротиворечивостью и независимостью. Теорема о полноте исчисления высказываний утверждает, что если ППФ А общезначима, то она является выводимой. Непротиворечивость означает, что в исчислении высказываний не выводимы никакие две ППФ, одна из которых является отрицанием другой. И наконец, независимость системы аксиом означает, что ни одна аксиома не выводима из остальных аксиом.

Множество правил вывода R исчисления высказываний задается двумя правилами: правилом подстановки и правилом заключения.

Правило подстановки. Если Ф – выводимая формула (тавтология), содержащая букву А, то, заменив в ней всюду букву А на произвольную ППФ В, получим также выводимую формулу (тавтологию). Данное правило можно записать в виде:

Ф(А) .

Ф(В)

Правило заключения (modus ponens). Если А и A B – выводимые формулы (тавтологии), то В – также тавтология. Данное правило записывается в виде:

A,A B .

B

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

В исчислении высказываний часто применяют дополнительные правила вывода, которые значительно сокращают путь доказательства теорем. Например, правило силлогизма:

(A B),(B C) .

A C

В ходе доказательства широко используется определенный класс ППФ, называемых предложениями Хорна. Предложения Хорна имеют вид:

A1 A2 ... An B.

Имеются две важные частные формы предложений Хорна:

1) если B ложно, то для общезначимого предложения Хорна верно A1 A2 ... An (данное предложение содержит только отрицательные атомы);

2)когда n=1 и A1=true, получаем предложение true B , которое эквивалентно атомарному истинному высказыванию B (данное предложение состоит только из одного положительного атома).

Не каждая БЗ может быть представлена предложениями Хорна. Но в тех случаях, когда это возможно, можно использовать простую процедуру вывода, основанную на применении правила modus ponens. Данная процедура должна применять modus ponens, пока не перестанут образовываться новые предложения.

Применение правил вывода для получения следствий опирается на свойство монотонности исчисления высказываний. Предположим, что в БЗ накоплено определенное множество истинных высказываний М1 (формул), из которого выводимо высказывание (формула) А. Монотонность означает, что добавление в БЗ нового множества выводимых высказываний (формул) М2 не повлияет на выводимость А, т.е. если М1 |– A, то и {M1 M2}|– A. Иными словами, при таком логическом выводе все истинные высказывания остаются истинными, а ложные – ложными. Вывод нового высказывания не требует возврата к предыдущим шагам вывода и изменения истинностных значений ранее полученных высказываний.

В заключение отметим, что исчисление высказываний – это разрешимая формальная система. Это следует из теоремы о полноте исчисления высказываний, которая утверждает, что в исчислении высказываний выводима любая общезначимая ППФ. Значит, если рассматриваемая формула общезначима, то она выводима в исчислении высказываний. Если это не так, то формула не принадлежит множеству семантически правильных формул.

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

Исчисление высказываний характеризуется ограниченными возможностями для представления знаний. Объясняется это тем, что в исчислении высказываний рассматриваются логические связи только между утверждениями, а сама структура утверждений не анализируется. Поэтому в исчислении высказываний нельзя установить связь между тем, о чем идет речь (объект) и тем, что сообщается о данном объекте (предикат). Исчисление предикатов рассматривает логические связи между различными элементами утверждений.

Предикатом называется неоднородная двузначная логическая функция от любого числа аргументов. Ее записывают в виде Р(х1,х2,..,хn) и называют n-местным предикатом. Здесь аргументы х1,х2,..,хn – принадлежат одному и тому же или различным множествам, представляющим объекты предметной области. Аргументы х1,х2,..,хn называют предметными пере-

менными, а их конкретные значения – предметными постоянными. Функ-

циональную букву Р называют предикатной буквой.

Предметные переменные и предметные постоянные называются термами. При подстановке вместо предметной переменной хn константы а n-местный предикат Р(х1,х2,…,a) от хn уже не зависит. Если все переменные предиката заменить соответствующими предметными постоянными, то получается 0-местный предикат или высказывание.

86 Глава 4

Например, трехместный предикат Р(х1,х2,х3) = “х1 есть произведение х2 на х3” переходит в высказывание при постановке х1=6, х2=2, х3=3.

В общем случае n-местный предикат Р(х1,х2,..,хn) задает отношение между элементами х1,х2,..,хn , которое означает, что “ х1,х2,..,хn находятся между собой в отношении Р”. При n=1 предикат выражает свойство предметной переменной, например, “х – студент отличник “.

Вместо предметных переменных в предикаты могут подставляться n- местные функции f(х1,х2,..,хn), определенные на множестве объектов предметной области.

Множество базовых элементов (алфавит) исчисления предикатов включает:

1)знаки логических операций , , , , ;

2)знаки кванторов , ;

3)знаки пунктуации ( );

4)предметные переменные x, y, z…;

5)предметные постоянные a, b, c…;

6)функциональные символы f, g, h…;

7)предикатные буквы P, Q, R, S, T, V, N.

Множество синтаксических правил, определяющих понятие ППФ исчисления предикатов, строится на основе понятий терм и элементарная формула. Терм определяется рекурсивно следующим образом:

a)каждая предметная переменная или предметная постоянная есть терм;

b)если t1, t2, .., tn – термы и f – n-местная функциональная буква, то f(t1, t2, .., tn ) – терм;

c)никакие другие выражения термами не являются.

Элементарная формула (атом) вводится следующим образом: если Р – предикатная буква, а t1, t2, .., tn – термы, то Р(t1, t2, .., tn ) – элементарная формула (атом). Частным случаем элементарной формулы является высказывание.

ППФ исчисления предикатов определяется следующим образом:

a)всякая элементарная формула есть формула;

b)если P и Q – формулы, и х – предметная переменная, то каждое из выражений

P(x),P(x) Q(x),P(x) Q(x),P(x) Q(x), xP(x), xP(x)

есть формула;

c) никакое другое выражение формулой не является.

Здесь знаки и обозначают соответственно кванторы существования и общности. Кванторы – это знаки, которые в сочетании с переменными дают возможность утверждать, что для всех или некоторых объектов

предметной области выполняется определенное свойство или отношение. Пусть Р(х) – предикат, где предметная переменная определена на множестве Х, т.е. x X . Утверждение, что все x X обладают свойством Р, записывается в виде формулы xP(x), которая читается “для всех х, Р от х”. Утверждение о том, что существует хотя бы один объект х предметной области Х, обладающий свойством Р, записывают в виде формулы xP(x) и читают: “существует такое х, что Р от х”. Выражения xP(x) и xP(x) не зависят от переменной х. Приписывая квантор впереди предметной переменной, переходим к высказываниям. Например, если Р(х) означает “х – четное число m”, то xP(x) – ложное высказывание, а xP(x) – истинное высказывание.

Кванторы xи x связывают переменную в области своего действия. Поэтому переменная х в формулах xP(x) и xP(x) является связанной. Если область действия квантора распространяется на несколько предикатов, связанных логическими операциями, то используются скобки. Например,

x y(P(x, y) R(x)).

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

Порядок следования одноименных кванторов не имеет значения, но разноименные кванторы переставлять нельзя. Так, x yP(x, y) и y xP(x, y)

– разные высказывания.

Для кванторов справедливы следующие законы де Моргана:

xP(x) xP(x) ,

xP(X) xP(x) .

Знак квантора общности соответствует перевернутой букве А и возник как сокращение английского слова all (все). Знак квантора существования соответствует перевернутой букве Е (от англ. exists – существовать). Квантор общности можно понимать как обобщение конъюнкции, а квантор существования – как обобщение дизъюнкции. Так, если область определения предиката Р(х) конечна и Х={a,b,c}, то высказывание xP(x) эквивалентно конъюнкции P(a) P(b) P(c), а высказывание xP(x) – дизъюнкции P(a) P(b) P(c). Когда предикатная формула определена на бесконечном множестве, то кванторы общности и существования можно рассматривать как “бесконечные” конъюнкции и дизъюнкции.

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

-предметной переменной x – элемент множества М, т.е. I(x) M ;

-n-местной функциональной букве f в формуле – n-местную функцию на М;

-n-местной предикатной букве Р в формуле – определение отношения между элементами на М.

На основе интерпретации определяется выполнимость и общезначимость формул.

Рассмотрим элементарную формулу Р(f(x1,x2),a). Пусть областью интерпретации является множество целых чисел и f(x1,x2)=x12 + x22, а=9, а P(x,y) соответствует отношению x>y. Тогда рассматриваемая формула обозначает отношение x12 + x22>9, которое выполнимо для всех х1 и х2, если |x1|+|x2|>5. Для упрощения интерпретации предикатных символов их часто записывают словами, которые являются названиями определяемых отношений. Например, отец(x,y) – означает, что х приходится отцом y.

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

Важными понятиями исчисления предикатов являются понятия отношений равносильности и логического следования. Эти понятия определяются аналогично исчислению высказываний. Напомним их.

Две формулы P и Q называются равносильными, если формула P Q является общезначимой, т.е. P Q, если |=P Q. Например,

P Q P Q .

Формула Q логически следует из формул P1,P2 ,...,Pn , тогда и только тогда, когда всякая интерпретация I, удовлетворяющая P1,P2 ,...,Pn , удовлетворяет также и Q. Отношение логического следования P1,P2 ,...,Pn Q(или P1,P2,...,Pn|=Q) соответствует общезначимости формулы |=P1 P2 ... Pn Q

или противоречивости формулы P1 P2 ... Pn Q . Таким образом, выяснение логического следования сводится к установлению общезначимости или противоречивости определенных формул.

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

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

1)xP(x) P(t), где t – терм;

2)P(t) xP(x) .

Вэтих аксиомах Р(х) – любая формула, содержащая свободное вхождение аргумента х, причем ни одно из них не находится в области действия квантора по t. В этом случае говорят, что P(х) свободна для t. Формула Р(t) получается из Р(х) заменой всех свободных вхождений х на t.

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

Правило универсальной конкретизации (УК)

xP ( x )

P ( t ) ,

где Р(t) получается заменой в Р(х) переменной х на фундаментальный терм t ( константа или функция от фундаментального терма). Например,xпредпочитает(х, мороженое), подставив вместо х константу “Иван”, по-

лучим: предпочитает(Иван, мороженое).

Правило экзистенциональной конкретизации (ЭК):

xP ( x)

Р(а ) .

Данное правило справедливо для любой формулы Р(х) и предметной постоянной а, которой нет в базе знаний. Например, из xнравится(х,

спорт) можно вывести нравится(спортсмен,спорт), если константа “спорт-

смен” отсутствует в базе знаний.

Правило экзистенциального обобщения (введение квантора ):

P (a) .

хР (х)

Оно позволяет перейти от Р(а) к xP(x), если Р(а) истинно.

Правило универсального обобщения (правило введения квантора ):

Q P(x)

Q xP(x) .