Cтраница 1
Формула исчисления высказываний называется реализуемой, если реализуема всякая арифметическая формула, получающаяся из нее путем подстановки. [1]
Формулы исчисления высказываний представляют собой конечные последовательности символов описанных категорий. [2]
Формулу исчисления высказываний, которая строится из формульных переменных с помощью одних только символов импликации и конъюнкции, мы будем называть 1 - К-формулой. [3]
Как и формулы исчисления высказываний, формулы исчисления предикатов делятся на три класса: общезначимые формулы, которые истинны при всех интерпретациях, невыполнимые, которые ложны при всех интерпретациях, и нейтральные ( или просто выполнимые), которые истинны только при некоторых интерпретациях. В противоположность тому, что имело место для исчисления высказываний, эти три класса не являются рекурсивными: не существует детерминированного алгоритма, который определял бы, к какому классу принадлежит произвольная формула исчисления предикатов. Вполне естественно, что формула исчисления предикатов выполнима, если она истинна хотя бы при одной интерпретации. [4]
В дальнейшем формулы исчисления высказываний будут обозначаться буквами Ф, W, X, а пропозициональные переменные - буквами Р, R, причем Ф, Y X, Р, R, могут иметь индексы. [5]
Тем самым каждая формула исчисления высказываний в указанном смысле равнозначна такой конъюнкции, у которой каждый член является либо примарным выражением, либо отрицанием конъюнкции примарных выражений. [6]
Элементы из Ф сейчас называем формулами исчисления высказываний. [7]
Как мы знаем, при истолковании формул исчисления высказываний, получающемся на основе понимания связок исчисления высказываний как истинностных функций, любая формула равнозначна некоторой конъюнкции, члены которой являются либо формульными переменными, либо отрицаниями формульных переменных - выражения этих двух типов мы будем называть п р и-марными вы р ажен и ями3), - либо дизъюнкциями, состоящими из нескольких примарных выражений. При этом упомянутая равнозначность имеет место в том смысле, что соответствующая конъюнкция задает ту же самую истинностную функцию, что и первоначальная формула. [8]
Первые десять аксиом представляют собой просто десять формул исчисления высказываний, объявляемых тождественно истинными по определению. Такая подстановка, по определению, не нарушает тождественной истинности формулы ( аксиомы), подвергшейся этой подстановке. [9]
В § 8 мы уже отметили, что формулы исчисления высказываний могут быть интерпретированы как формулы алгебры высказываний. [10]
Из 1 - 4 видно, что все формулы исчисления высказываний являются также формулами исчисления предикатов. В самом деле, в числе формул исчисления предикатов находятся переменные высказывания, и мы можем, исходя из них, образовывать формулы, пользуясь теми же операциями, что и в исчислении высказываний. [11]
Мы показали, таким образом, что всякая формула исчисления высказываний, выводимая в исчислении предикатов, является выводимой формулой исчисления высказываний. [12]
Если теперь считать, что локальная теорема для формул исчисления высказываний доказана, то, опираясь на приведенные построения, можно заключить, что она верна и в общем случае. [13]
Легко видеть, что применение этих схем к формулам исчисления высказываний дает только тождественно истинные формулы. [14]
В силу установленного соответствия между диаграммами Венна и формулами исчисления высказываний можно говорить о графическом ( диаграммном) построении исчисления высказываний. [15]