Cтраница 3
Мы будем в дальнейшем пользоваться соглашением об опускании внешних скобок, принятом в § 2 главы 1, Заметим, что формулу исчисления высказываний можно рассматривать как формулу некоторой сигнатуры, если считать, что символы пропозициональных переменных являются нульместными предикатными символами. [31]
С этой целью достаточно заменить различные входящие в нее элементарные формулы различными функциональными переменными без аргументов и проверить, является ли полученная таким образом формула исчисления высказываний тождественно истинной. [32]
Заметим, что операция Rf ( Г), представляющая собой подстановку в формулу исчисления высказываний 2Т другой формулы 33, которая также является формулой исчисления высказываний, всегда выполнима. [33]
Все эти кирпичи, из которых строятся формулы системы 9, можно рассматривать как систему основных высказываний, и тогда формулы из 9Z превратятся в формулы исчисления высказываний. [34]
В этом утверждении мы можем заменить схемы формул, соответствующие тождественно истинным формулам, самими этими формулами, считая, что используемые в выводах схемы применяются к формулам исчисления высказываний, не содержащим знака дизъюнкции. Это вытекает из упомянутого в конце предыдущего параграфа результата, утверждающего, что выводы, производимые с помощью схем, применяемых к формулам исчисления высказываний, протекают совершенно аналогично выводам, применяемым к схемам формул, получающимся из соответствующих формул в результате замены формульных переменных буквами, обозначающими произвольные формулы. [35]
Теперь условимся, в пределах этой главы, что если мы употребляем слово формула, не указывая конкретного смысла, то это слово можно понимать и в смысле формулы исчисления высказываний, и в смысле формулы исчисления предикатов, которая будет определена в следующей главе, и в арифметическом смысле. [36]
В то же время совокупности выражений логики высказываний, с одной стороны, и теории контактных схем, с другой - можно рассматривать в качестве конкретных интерпретаций ( представлений, моделей, реализаций) исчисления высказываний, получаемых в результате приписываний бессодержательным формулам исчисления высказываний некоторого смысла: в первом случае в терминах высказывания ( предложений, суждений, утверждений) и форм высказываний, во втором - в терминах контактных электрических схем. [37]
Одно из этих значений, например 0, отождествляется с истинностным значением истина, другое - с истинностным значением ложь. Доказуемой формуле исчисления высказываний ( соответственно тождественно-истинной формуле логики высказываний или эквивалентной ей в указанном выше смысле электрической схеме) тогда будет соответствовать функция двух аргументов, тождественно равная нулю, а опровержимой ( соответственно тождественно-ложной, никогда не пропускающей ток) - функция, тождественно равная единице. [38]
Понятие доказательства ( в виде дерева) определяется обычным образом. ЛГ - формула исчисления высказываний, но, вообще говоря, не является формулой исчисления резольвент. [39]
В данном случае не все 2s возможных наборов из 1 и 0 использованы в качестве входных букв, и, следовательно, мы имеем дело с функциями алгебры логики, которые не всюду определены. Поскольку, как мы знаем, всякая формула исчисления высказываний задает функцию, всюду определенную, то, как отмечено в гл. I, § 3, аналитическое задание функций фх ( xlt х2, х3) и ра ( zj, x2, ха) предполагает доопределение таблицы путем включения в нее недостающих входных кодовых групп, которым сопоставлены определенные значения функций. Такое доопределение возможно многими способами, и, как отмечено в гл. I, надлежащим выбором этого способа удается иногда существенно упростить аналитическое представление таблично заданного оператора. [40]
Следует отметить, что звездочки у Венна встречаются только в одном примере. Диаграммы, не содержащие звездочек, изоморфны формулам исчисления высказываний. Звездочки на диаграммах появляются для выражения частных суждений, не формулируемых на языке формул исчисления высказываний. Однако введение звездочек не позволяет еще использовать диаграммы для выражения произвольных предложений логики классов. В третьей главе предлагается такое изменение диаграмм, которое позволяет выражать в них информацию, задаваемую произвольными формулами исчисления одноместных предикатов. [41]
Легко построить примеры, для которых алгоритмы Кузина и редукции ненамного эффективнее, чем тривиальный алгоритм. Точнее, установлено, что проблема выявления общезначимости ( или выполнимости) формулы исчисления высказываний NP-полна. Не вдаваясь в рассуждения, выходящие за рамки этой книги, отметим, что указанный факт означает ничтожность вероятности существования эффективного общего алгоритма для проверки выполнимости или общезначимости формул исчисления высказываний. [42]
Формула исчисления предикатов, не содержащая вхождений индивидных переменных, называется формулой исчисления высказываний. Тождественно истинные, или, как мы иногда для краткости говорим, тождественные формулы исчисления высказываний, среди прочих формул характеризуются при помощи следующей процедуры вычисления их значений. [43]
Как подчеркивалось в главе 2, надежность сети из не вполне надежных элементов может быть обеспечена за счет избыточности последних. Так как на одном формальном нейроне можно реализовать несколько неэквивалентных между собой формул исчисления высказываний ( без обратных связей число таких формул не превосходит 2 1 введение обратных связей позволяет увеличить их количество до 2n 1, см. § 4.4), то формальные нейроны можно использовать в качестве не вполне надежных элементов при конструировании надежных схем описанного во второй главе вида. [44]
Доказательство этого осуществляется на основании того же соответствия, в силу которого мы каждой фор муле 21 исчисления предикатов отнесли формулу исчисления высказываний. Из рассуждений § 5 вытен кает, что каждая формула, которой соответствует выво димая формула исчисления высказываний, может быт присоединена без противоречия к аксиомам исчисления; предикатов. [45]