Intel_Nils (526801), страница 35

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 35)

п. формуле приписывается значение Т или Р. Эти значения можно затем использовать для того, чтобы приписать значение Т или Р всей п. п. формуле. Правило приписывания значения атомной формулы очень простое: если термы предикатной буквы соответствуют элементам из О, удовлетворяющим соответствующему соотношению, то значением атомной формулы будет Т, в противном случае будет Р. Рассмотрим в качестве примера атомную формулу Р (а, 1 (Ь, с)) 176 Гл.

б. доиазательстео теорем е исчислении арединатое и следующую интерпретацию: Р— множество целых чисел, а — число 2, Ь вЂ” число 4, с — число 6, 1 — функция сложения, Р— отношение „больше". х,4 х, х, х,чх, х,лх, т т р р т т р т Этот метод вычисления называется методом таблиц истинности. При данной интерпретации для некоторой п. п, формулы (и, таким образом, для данных значений каждой атомной формулы, содержащейся в ней) всегда можно вычислить значение (Т или Р) этой п. п. формулы с помощью таблицы истинности. Если значение некоторой п.

п. формулы при данной интерпретации есть Т, то говорят, что эта интерпретация удовлетворяет указанной и. п. формуле (или выполняет указанную и. п. формулу). Неатомная п. п. формула и ее значение служат для опре- При такой интерпретации наша атомная формула утверждает, что «число 2 больше суммы чисел 4 н 6».

Это утверждение неверно, поэтому Р(а,)(Ь,с)) имеет значение Р. Если интерпретацию изменить так, что а станет числом !1, то Р(а,)(Ь,с)) будет иметь значение Т. Очевидно, что существует много других интерпретаций, для которых эта атомная формула имеет значение Т, и много таких интерпретаций, для которых она имеет значение Р, но для любой интерпретации будет либо Т, либо Р и никогда то и другое одновременно. Значение неатомной п.

п. формулы можно вычислить рекуррентно, исходя из значений составляющих ее формул. При таком вычислении используются следующие правила: Если Х~ — п. п. формула, то Х~ имеет значение Т, когда Хт имеет значение Р, и Хт имеет значение Р, когда Х~ имеет значение Т. Если Х~ и Хт †люб две п. п. формулы, то значения (Х~чт Хе), (Х, /~ Хт) и (Хт=)» Хт) даются следующей таблицей истинности: !77 бли Переменные и квонторм деления некоторого нового отношений между элементами из ьт: и. п. формула делает некоторое утверждение относительно элементов из О, истинное, когда значение этой п.

п. формулы есть Т. ал. пеРеменные н кВАнтОРы Рассмотрим п. п. формулу Р(а, Ь) и интерпретацию Р— конечное множество целых чисел 1,2,...,99,100, а — число 30, Ь вЂ” число 1, Р— отношение «больше или равно». При такой интерпретации п. п. формула утверждает, что «30 больше илн равно 1», Это утверждение, очевидно, истинное, и наша п.

п. формула при данной интерпретации имеет значе- ние Т. Предположим, что при той же самой области мы припи- сываем значения 1, 2, ..., 100 константным буквам 1ао Та, ... ...,1аии соответственно. С каждой нз этих бУкв можно сконст- руировать и. п. формулу вида При этом каждая из п, и. формул прн данной интерпретации имеет значение Т.

Часто бывает нужно высказать определенное утверждение, относящееся к каждому элементу некоторой области. Такое утверждение можно было бы сделать в виде конъюнкции' ) п. п. формул, утверждение каждой из которых касается одного из элементов. В рассмотренном выше примере п. п. формула Р ((и ~;) Л Р Д ~;) Л ... Л Р()',„, ~',) утверждает, что «каждое целое число от 1 до !00 больше илн равно 1». Так как каждая п.

п. формула Р(Р,', 1в) имеет значение Т, то мы устанавливаем с помощью таблиц истинности, что эта конъюнкция также имеет значение Т. Использование больших конъюнкций для выражения утверждений, содержащих слова каждый или для всех, привело бы к слишком громоздким выражениям. Для их сокращенной записи введем в наш язык символ и (означающий для всех) и индиеидные переменные х; (1) !). (Иногда вместо х; мы будем употреблять буквы и, и, ти, у, г.) Предполагается, что ') Конаюнкчией и.и. формул Хь Ха ..., Х» иааываетса и.и. формула А Л Х»Л...Л Х».

пв Гл. 6. Докозотелоство теорем в исчислении лредикотов переменные хс принимают значения из области интерпретации, Так, в нашем примере вместо выписывания конъюнкции, содержащей п. п. формулы для каждого элемента рассматриваемой области, мы будем писать просто (УУх) Р (х, го), Символ 1т называется квангором всеобщности, а переменная, стоящая сразу же за символом 1т, называется переменной, относящейся к квантору всеобщности.

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

п. формул, содержащих кванторы, можно вычислить, минуя оценку бесконечных конъюнкций. (Например, согласно таблице истинности, простая п. п. формула [(Чх) Р (х) Ф (Чх) Р (х)) в любой интерпретации имеет значение Т.) Иногда требуется высказать утверждение, касающееся всех пар элементов из некоторой области или всех троек и т. п. Тогда используется несколько переменных и для каждой из ннх символ У. Так, правильно построенную формулу, соответствующую утверждению кдля всех пар целых чисел, расположенных между 1 и 100, первое больше второго», можно запиеать в виде (Чх) (Уу) Р(х, у). Очевидно, что эта и.

п. формула (двойная конъюнкция) при нашей интерпретации имеет значение Р. Подобное сокращение имеется и для дизъюнкций'), перечисляющих каждый элемент области. Предположим, мы имеем дизъюнкцию (з([о) ту () ([о) ттс () (то) т т где )оы узо, ... — элементы области .О. Согласно таблице истинности, зта правильно построенная формула имеет значение Т, ') Лизаюккциеа п.п. формул ХиХ», ..., Х называется п.п. формула Х~ ~/ т/ Хе тс'... тс'Х».

б.б. Общезначимость и выполнимость 179 когда верно утверждение «по крайней мере один элемент из Р обладает, свойством Я». Вместо дизъюнкций, в которых упоминается каждый элемент области, пользуются символом '"-1 и соответствующей переменной. Тогда приведенная выше дизъюнкция принимает вид (Зх) Я (х).

Символ З (существует) называется квантором существования, а переменная, стоящая сразу же после символа ~, называется переменной, относящейся к квантору существования. Когда такая переменная появляется внутри области действия квантора ~, про нее говорят, что она относится к квантору существования, а также, что она связывается этим квантором. С помощью таблиц истинности (для конечных областей) можно показать, что всегда значение истинности п. п. формулы - (чгх) Я7(х) совпадает со значением истинности п. п. формулы (Зх) ( ИГ (х)).

Аналогично З (х) й7 (х) и (ч'х) ( ЯГ (х)) эквивалентны. Мы будем считать, что эти соотношения эквивалентны и в неограниченных областях. При комбинировании кванторов всеобщности и существования действие квантора существования может оказаться «зависящим» от каких-нибудь предшествующих кванторов всеобщности. Так, утверждение «для любого целого числа существует большее целое число» можно записать в виде (Ъ'х) (Зу) Р(у, х). Очевидно, что если эта п.

п. формула должна иметь значение Т, то переменная у, которая «существует», должна зависеть от х. В п. п. формулах, состоящих более чем из одной предикатной буквы, мы будем использовать фигурные скобки для обозначения области действия кванторов. Так, (У х) ( ) означает, что любая переменная х, появляющаяся в этих фигурных скобках, относится к квантору всеобщности. 6,5. ОБЩЕЗНАЧИМОСТЬ И ВЫПОЛНИМОСТЬ Если некоторая п. и. формула имеет значение Т при всех интерпретациях, то ее называют общезначимой. Так, по таблице истинности п. и. формула Р(а)ь(Р(а)'/Р(о)) при любой интерпретации имеет значение Т и, следовательно, она общезначима. С помощью таблиц истинности всегда можно определить, общезначима ли данная п. п.

формула, не содержащая кванторов. Нужно просто проверить, имеет ли эта и. и. формула значение Т при всех возможных значениях (Т или Р) содержащихся в ней атомных формул. 180 Гл. В. докивательство теорем в исчислении нредикотов Когда же появляются кванторы, общезначимость или ее от- сутствие не всегда можно установить. Было показано, что об- щего метода нахождения значений всех бесконечных формул, содержащих кванторы, не существует. По этой причине исчис- ление предикатов называют неразрешимым. Можно установить общезначимость лишь некоторых типов ' формул, содержащих кванторы, и поэтому можно говорить о разрешимых подклассах исчисления предикатов.

Более того, если некоторая п. п. формула на самом деле общезначима, то существует процедура для проверки ее общезначимости. (Та же процедура, примененная к п. п. формулам, не являющимся общезначимыми, может привести к неограниченной последова- тельности операций.) Поэтому исчисление предикатов можно назвать полуразрешимым. Если при данной интерпретации каждая п. п. формула нз некоторого множества п. п. формул имеет значение Т, то гово- рят, что данная интерпретация удовлетворяет этому множеству. Правильно построенная формула )т логически следует из неко- торого множества 5 п. п. формул, если каждая интерпретация, удовлетворяющая 5, удовлетворяет также и ))т. Так, очевидно, что (1е хну) (Р (х) 1Г Я (у)) логически следует из ((тухЧу) (Р (х) ~/ Я (у )) (чг) Я(г) 1тЯ(а))), а Р(а) логически следует из ((чх) Р(х)).

Характеристики

Список файлов книги