Cтраница 3
Теорема полноты для классической логики высказываний утверждает, что множество теорем классического исчисления высказываний совпадает с множеством тождественно истинных пропозициональных формул, В модальной логике аналогом понятия тождественной истинности служит понятие общезначимости на шкале Монтегю. Так как на разных шкалах могут оказаться общезначимыми разные формулы, возникает большое число разнообразных исчислений и теорем о полноте. [31]
Если при некотором применении правила вывода посылки являются тождественно истинными пропозициональными формулами, то и заключение является тождественно истинной пропозициональной формулой. [32]
Для того чтобы показать, что ДНФ-тавтологии Р - сводится к D3, предположим, что А - пропозициональная формула в дизъюнктивной нормальной форме. Таким образом, мы уменьшили число конъюнкций в BI, и этот процесс можно повторять до тех пор, пока в конце концов - не найдем формулы, которая имеет не больше трех атомов в каждой конъюнкции. Ясно, что весь процесс ограничен по времени некоторым полиномом от длины А. [33]
Покажите, что все правила вывода для F-зависимостей переходят в корректные логические правила вывода, если F-зависимости интерпретируются как пропозициональные формулы. [34]
ПРОПОЗИЦИОНАЛЬНОЕ ИСЧИСЛЕНИЕ, и с ч и с ленив высказывани и, - логическое исчисление, в к-ром выводимыми объектами являются пропозициональные формулы. [35]
Как говорят, мы имеем здесь одиннадцать схем аксиом; из каждой схемы можно получить различные конкретные аксиомы, заменяя входящие в нее буквы на пропозициональные формулы. [36]
Доказать интерполяционную теорему: если пропозициональная формула Л D В - тавтология, и формулы - ( А и В не являются тавтологиями, то существует пропозициональная формула С, содержащая только те переменные, которые входят как в А, так и в Б, такая, что формулы A D С и С D Б суть тавтологии. [37]
Показано, что любая проблема распознавания, решаемая на недетерминированной машине Тьюринга за полиномиально ограниченное время, может быть сведена к проблеме распознавания того, является ли некоторая пропозициональная формула тавтологией. Здесь сведена означает, грубо говоря, что первая проблема может быть решена детерминирование за полиномиальное время при условии, что имеется оракул для решения второй. Исходя из этого понятия сводимости, определены полиномиальные степени трудности и показано, что проблема определения тавтолргичности имеет ту же самую полиномиальную степень, что и проблема определения того, верно ли, что первый из двух заданных графов изоморфен некоторому подграфу второго. Обсуждаются и другие примеры. Вводится и обсуждается также метод измерения сложности процедур вывода для исчисления предикатов. [38]
Покажите, что все правила вывода для одних MV-зависимостей и для F-зависимостей совместно с MV-зависимостями переходят в корректные логические правила, когда F - и MV-зависимости интерпретируются как пропозициональные формулы. [39]
Покажите, что все правила вывода для одних MV-зависимостей и для F-зависнмостей совместно с MV-зависимостями переходят в корректные логические правила, когда F - и MV-зависимости интерпретируются как пропозициональные формулы. [40]
Один способ реализации этой процедуры состоит в формировании так называемой общей развертки F над универсумом из р элементов с последующим предъявлением ее на вход процедуры, распознающей выполнимость пропозициональных формул. [41]
Следующий простой факт дает некоторое свидетельство в пользу того, что при описанном выше соответствии F-зависимостей и формул отношения следования для зависимостей и формул совпадают: все правила вывода для F-зависимостей переходят в корректные логические правила, если F-зависимости интерпретировать как пропозициональные формулы ( см. упр. [42]
С другой стороны, при ( обычной) логической интерпретации пропозициональные буквы рассматриваются как независимые переменные, пробегающие некоторую область предложений. Пропозициональная формула выражает тогда общее предложение, что истинными являются все те предложения, которые она дает при различных выборах предложений из этой области в качестве значений ее независимых переменных. Эта логическая интерпретация связывается с арифметической, если поставить предложения из рассматриваемой области в такое много-однозначное соответствие с двумя предметами t, f, что предложения, соответствующие t, истинны, а предложения, соответствующие f - ложны. Предложение, выраженное формулой при этой интерпретации, не эквивалентно никакому метаматематически определимому свойству этой формулы, за исключением случаев, когда в качестве значений пропозициональных букв допускаются лишь предложения из некоторых специальным образом ограниченных областей. [43]
Пропозициональная формула называется тавтологией, если она превращается в истинное высказывание при любой подстановке конкретных высказываний вместо переменных; каждая тавтология является схемой истинных высказываний и в этом смысле выражает некоторый логический закон. Приведем примеры логических законов: ( Р V - Р) - закон исключенного третьего; ( - i - iP Р) - закон двойного отрицания; - i ( P & - iP) - закон противоречия; ( ( ( Р D Q) D Р) D Р) - закон Пирса. [44]
Остается доказать, что эта процедура должна закончиться. Но пропозициональная формула Е имеет только конечное число подформул, и имеется только конечное число k способов, которыми эти формулы могут входить в антецедент и входить в сукцедент. Следовательно, не может существовать несводимого доказательства секвенции - Е, содержащего более чем k уровней; поэтому можно исчерпать все возможности найти такое доказательство, если довести процедуру ( самое большее) до k - то уровня включительно. [45]