Cтраница 3
Точное доказательство основано на таких же аргументах, как доказательство аналогичных утверждений для модальных пропозициональных исчислений ( см, стр. [31]
Точное доказательство основано на таких же аргументах, как доказательство аналогичных утверждений для модальных пропозициональных исчислений ( см. стр. [32]
Этот параграф аналогичен IX, § 5, где та же проблема иссле-девалась для пропозициональных исчислений. [33]
TQ ( k) было бы примерно эквивалентным нахождению нижней границы для проблемы разрешения пропозиционального исчисления В частности, теорема ЗА стала бы очевидной и тривиальной. [34]
Этот результат применим почти ко всем известным разрешимым теориям в логике, за исключением пропозиционального исчисления и исчисления чистого равенства. [35]
Этот параграф аналогичен IX, § 5, где та же проблема исследовалась для пропозициональных исчислений. [36]
Описанный процесс редукций на самом деле дает нам эффективный метод решения проблемы истинности в пропозициональном исчислении. NP) требует экспоненциального времени. [37]
Метод истинностных таблиц является хорошо известной эффективной процедурой для решения вопроса об общезначимости произвольного предложения пропозиционального исчисления. [38]
Априори ниоткуда не следует, что охарактеризованное подобным формальным путем множество всех тождественно истинных формул пропозиционального исчисления будет совпадать с множеством всех тождественно истинных формул, определенных выше содержательно. Поскольку формальная тождественная истинность формул устанавливается некоторой процедурой вывода или доказательства, их называют также ( формально) доказуемыми формулами, или ( формальными) теоремами. [39]
Пропозициональная связка Э используется в дальнейшем как инструмент для получения логических следствий из тех или иных формул пропозиционального исчисления и других, более высоких логических исчислений. Такие следствия должны быть истинными при истинности исходных формул. Поэтому конструкция вывода обязательно должна исключить возможность ( указанием на свою ложность в этом случае) получения ложных следствий при истинности исходных формул. В то же время при ложности исходных данных получение любых следствий ( как истинных, так и ложных) не свидетельствует, разумеется, о ложности самой конструкции вывода. Это обстоятельство и находит свое конкретное выражение в таблице истинности для формулы А Э В. [40]
Доказав бесконечную версию теоремы Рамсея, мы теперь выведем из нее с помощью теоремы компактности ( исключительно для пропозиционального исчисления) некоторое утверждение, из которого немедленно следует конечная версия. [41]
После всех наших предварительных замечаний перейдем к построению собственно исчисления высказываний, или, как его еще иногда называют, пропозиционального исчисления. [42]
В 1936 году Черч показал, что доказуемость ( и, следовательно, истинность) в исчислении предикатов неразрешима в отличие от более простого пропозиционального исчисления. [43]
Интуитивный смысл теорем 9.3 и 9.4 состоит в том, что как классическое, так и интуиционистское пропозициональное исчисление можно интерпретировать как часть модального пропозиционального исчисления. [44]
Следующая теорема, называемая теоремой о полноте для модальных пропозициональных исчислений 9 & й, tfj, является модальным аналогом теоремы о полноте VII, 2.1 для классических пропозициональных исчислений и теоремы о полноте IX, 3.1 для интуиционистских пропозициональных исчислений. [45]