Языки и исчисления


Общезначимые формулы - часть 2


Можно ли из этого заключить, что она общезначима? (Указание: воспользуйтесь теоремой Левенгейма-Сколема об элементарной подмодели.)

Две формулы и (с параметрами или без) называются эквивалентными, если в любой интерпретации и на любой оценке, на которой истинна одна из них, истинна и другая. Это определение равносильно такому: формула общезначима. Здесь, напомним, есть сокращение для .

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

Двойственное к общезначимости понятие — выполнимость. Формула называется выполнимой, если она истинна в некоторой интерпретации на некоторой оценке. Очевидно, формула

общезначима тогда и только тогда, когда формула

не является выполнимой.

90. Закончите утверждение: выполнимость формулы с параметрами равносильна выполнимости замкнутой формулы, которая получится, если\,

Чтобы проверить, является ли формула тавтологией, достаточно подставить в нее все возможные наборы значений переменных. Хотя этот процесс может быть на практике невыполним (наборов слишком много), теоретически мы имеем простой алгоритм проверки, является ли формула тавтологией. Для общезначимых формул в общем случае такого алгоритма не существует (теорема Черча; ее доказательство можно прочесть в [5]); он есть только для очень ограниченных классов формул. Например, если сигнатура содержит только нульместные предикатные символы, то задача по существу сводится к проверке тавтологичности (в этом случае кванторы фиктивны). Чуть более сложен случай с одноместными предикатами.

91. Пусть сигнатура содержит только одноместные предикаты. Докажите, что всякая выполнимая формула этой сигнатуры, содержащая различных предикатов, выполнима в некоторой конечной интерпретации, содержащей не более элементов. Как использовать этот факт для алгоритмической проверки выполнимости формул такой сигнатуры?




- Начало -  - Назад -  - Вперед -



Книжный магазин