Cтраница 4
Целью логики высказываний является описание класса всех общезначимых формул при данной интерпретации. Одним из способов такого описания является построение В. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. Наиболее часто при построении В. [46]
Приведенное описание отношения л с помощью подмножества V множества S остается безнадежно туманным, пока мы не интерпретируем S как множество формул исчисления высказываний. При такой интерпретации становится видно, что fi должно интерпретироваться как отношение eq, a V как множество общезначимых формул. В итоге описание отношения fi с помощью V сводится к следующему: две формулы s и t эквивалентны тогда и только тогда, когда эквиваленция s - W - общезначимая формула. Подозрение, что такая интерпретация множества S лежала в основе программы построения рассматриваемой формальной системы, вполне обосновано. [47]
Понятие общезначимости подчеркивает тот факт, что задаваемая формулами булева функция сохраняет свое значение истинности на всех значениях аргументов. Понятие тавтологии подчеркивает, что тождественно истинное утверждение является в некотором смысле тривиальным, не дающим никакой информации о взаимосвязи входящих в него высказываний. Действительно, если мы знаем, что А & В истинно, то мы знаем, что и Аи В являются истинными утверждениями. Однако же истинность утверждения AID AVB не налагает никаких связей на А и В. Таким образом, общезначимая формула характеризует скорее некоторое свойство входящих в него логических связок, проявляющее себя безотносительно не только к смысловому содержанию, но даже и к значениям истинности входящих в нее логических переменных. [48]
Если отрицание данной формулы противоречиво, то программа Гилмора в конце концов обнаруживает этот факт. Внимательное изучение его программы показало, что его метод проверки противоречивости пропозициональных формул неэффективен. Метод Гилмора был улучшен Деви-сом и Патнемом [1] несколько месяцев спустя после того, как был опубликован. Однако их улучшение было еще недостаточно. Многие общезначимые формулы логики первого порядка все еще не могут быть доказаны на вычислительной машине в разумное время. [49]
Словарь дает возможность строить сложные или составные высказывания из исходных ( простых, элементарных), соединяя последние связками. Правила построения описывают те выражения, которые являются объектами языка. Такие высказывания называют формулами. Семантика произвольной формулы исчисления высказываний полностью определяется ее таблицей истинности. Формула семантически выполнима или просто выполнима, если она допускает некоторую модель, т.е. ее можно интерпретировать со значением И. Формула общезначима, если она истинна независимо от истинностных значений, приписанных составляющим ее высказываниям. Общезначимые формулы исчисления высказываний часто называют тавтологиями. [50]
Множество ML всех финитно общезначимых пропозициональных формул замкнуто относительно ныноди-мости в интуиционистском исчислении высказываний п содержит нее формулы, выводимые в этом исчислении. Тем самым ML является промежуточной ( или суперннтупцноиистской, с уперконструктивной) логикой, паз. Эта логика содержит формулы, не выводимые в интуиционистском исчислении высказываний ( такова, напр. Логика Медведева обладает свойством дизъюнктивное: если формула вида A v Н финитно общезначима, то по крайней мере одна из формул / 1 пли Н финитно общезначима. Кели пропозициональная формула не содержит какого-либо пз логич. V, ID, то она финитно общезначима тогда п только тогда, когда выводима в интуиционистском исчислении высказываний. Все финитно общезначимые формулы выводимы н классич. [51]