29Алгоритм построения резолюций для множества фраз Хорна.

Пусть S – множество фраз Хорна. : При условии Ложь Ï S, выбираем p и с, такие что:

p – унитарный позитивный дизъюнкт из S

c – дизъюнкт из S, содержащий Øp

вычисляем резольвенту r;заменяем множество S на (S/{c}È{r}).

Таким образом, на каждом этапе одна фраза Хорна заменяется другой, и некоторый атом удаляется из одного дизъюнкта. Отсюда следует, что выполнение алгоритма всегда завершается, какая бы стратегия ни была принята при выборе p и с. Если N – число атомов, первоначально присутствующих в S (c учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.

Существует два случая завершения алгоритма: либо порождён пустой дизъюнкт, тогда множество будет не выполнимым, либо получено множество S, не содержащее дизъюнктов для вычисления очередной резольвенты, тогда множество S будет выполнимым.

30Свойства формализованного счисления высказываний.

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

В то же время алгебра высказываний, изложенная в пь 1, пронизана содержательным смыслом: за каждой пропозициональной переменной стоит конкретное высказывание нашего языка, каждая формула может превращаться в конкретное составное высказывание, некоторые формулы могут превращаться только в истинные высказывания (тавтологии) и т.д. В данной сфере, являющейся областью семантики, каждое понятие наполнено каким-то внутренним содержанием, смыслом. Понятия истины и лжи, тождественной истинности и тождественной ложности формул, равносильности и логического следования формул считают понятиями семантическими.

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

Теорема 16.5. Всякая тогкдественно истинная формула (иви тавтология) алгебры высказываний доказуема в формализованном исчислении высказываний.

Теорема 1б.б (о полноте формализованного исчисления высказываний). Формула тогда и только тогда доказуема в формализованном исчислении высказываний (является теоремой исчисления), когда она является тавтологией алгебры высказываний.

Теорема адекватности. Теорема адекватности является обобщением предыдущей теоремы о полноте и вытекает из нее.

Теорема 1б. 7(адекватности). Формула G выводима в формализованном исчислении высказываний из конечного множества гипотез Г тогда и только тогда, когда она является логическим следствием всех формул из этого множества.

Непротиворечивость формализованного исчисления высказываний. Непротиворечивость — важнейшее свойство, которым должна обладать аксиоматическая теория. Противоречивая теория никакой ценности не имеет.

Определение 16.8. Аксиоматическая теория называется непротиворечивой, если ни для какого утверждения А, сформулированного в терминах этой теории, само утверждение А и его отрицание А не могут быть одновременно теоремами данной теории. Если для некоторого утверждения А теории оба утверждения А и не А — теоремы этой теории, то аксиоматическая теория называется противоречивой.

Применительно к формализованному исчислению высказываний непротиворечивость означает, по в нем не существует такой формулы F, что сама формула и ее отрицание F являются теоремами формализованного исчисления высказываний, т.е. выводимы из аксиом. Следующая теорема утверждает, по это действительно так.

Теорема 16.9(о непротиворечивости формализованного исчисления высказываний). Формализованное исчисление высказываний есть непротиворечивая аксиоматическая теория.

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

Теорема 1б.11 (разрешимости формализованного исчисления высказываний). Формализованное исчисление высказываний есть разрешимая аксиоматическая теория.

31Предикат. Предикаты и отношения. Предикаты и функции. Предикаты и высказывания.

Предикатом P(x₁, …,x_n) называется функция P: Mⁿ ® B, где M — произвольное множество, а B — двоичное множество. Иначе говоря, n–местный предикат, определенный на M, — это двузначная функция от n аргументов, принимающих значения в произвольном множестве M.

M — предметная область предиката,

x₁, …,x_n — предметные переменные.

N местный предика это повествовательное предложение, содержащее н предметных переменных, определяющихся каждая своим множеством. Например p(x,y), где x это валюта,y это государство.

Можно определять предикат по другому: предикат как функция P: M₁ ´ M₂ ´…´ M_n ® B.

Определенным на множествах M₁ , M₂ , … , M_n n–местным предикатом называется предложение, содержащее n переменных x₁, …,x_n , превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M₁ , M₂ , … , M_n , соответственно.

Предикаты и высказывания

Под н-местным предикатом понимается произвольное высказывание.

Выражения P(a₁, …,a_n), где a₁, …,a_n ÎM, будем понимать как высказывание «P(a₁, …,a_n) = 1» или как «P(a₁, …,a_n) истинно», а выражение P(x₁, …,x_n), где x₁, …,x_n — переменные, как переменное высказывание

!!! P(x₁, …,x_n) — это логическая переменная, а x₁, …,x_n — нелогические переменные.

Соответствие между n–местными отношениями и n–местными предикатами

a)каждому n–местному отношению R соответствует предикат P такой, что P(a₁, …,a_n) = 1, если и только если (a₁, …,a_n) Î R;

б) всякий предикат P(x₁, …,x_n) определяет отношение R такое, что (a₁, …,a_n) Î R, если и только если P(a₁, …,a_n) = 1.

Соответствие между предикатами и функциями

Всякой функции f(x₁, …, x_n), f: Mⁿ ® M соответствует предикат P(x₁, …, x_n, x_n+1), P: M_n+1 ® B, такой, что P(a₁, …,a_n, a_n+1) = 1, если и только если f(a₁, …,a_n) = a_n+1.

Понятие предиката шире понятия функции, поэтому обратное соответствие (от (n + 1)-местного предиката к n-местной функции) возможно не всегда, а только для таких предикатов P¢ для которых выполняется условие: если P¢(a₁, …,a_n, a_n+1) = 1, то для любого a¢_n+1 ¹ a_n+1 P¢(a₁, …,a_n, a¢_n+1) = 0.