Cтраница 1
Истинностная функция от п переменных задается таблицей из 2 строк. [1]
Ка всех истинностных функций из - Р2 д образует полную в Q систему. Как отмечалось в § 3.5, класс Т25ка является конечно порожденным. Применяя теорему I, получаем, что множество [ Ru ] можно расширить до предполного в Q класса. [2]
Таким образом, любая истинностная функция может быть представлена дизъюнктивной и конъюнктивной нормальной формой. [3]
Очевидно, что каждая истинностная функция, если она построена с помощью принятых здесь обозначений, задает формулу в смысле данного выше определения и, наоборот, каждую формулу можно рассматривать как истинностную функцию. Далее, должно быть ясно, что для того, чтобы приписать истинностное значение формуле А при данных истинностных значениях простых компонентов формулы Л, нужно рассмотреть структуру составной формулы А как функции. Когда это будет удобно, мы будем считать себя вправе рассматривать формулу как истинностную функцию. В таком случае простые компоненты ( символы-высказывания) будут рассматриваться как переменные, могущие принимать истинностные значения Тир. [4]
Ясно, что такие функции, составленные из истинностных функций, снова являются истинностными функциями. [5]
Убедимся в том, что пропозициональная форма D порождает истинностную функцию / Возьмем произвольное распределение значений для букв и, соответственно, для переменных. Пусть это распределение в истинностной таблице для / образует / - - ю строку. Следовательно, значение Л примет и их дизъюнкция, то есть форма D. [6]
В самом деле, при понимании импликации, конъюнкции и отрицания как истинностных функций каждая из этих пяти замен ни при каком наборе истинностных значений формульных переменных не меняет значений преобразуемого выражения. [7]
А тл связки /, &, v, и которая порождает данную истинностную функцию. [8]
Иными словами, функция а ( х, у, z) есть истинностная функция g высказывания x - - y z, равная 1, когда оно верно, и 0, когда оно ложно. [9]
Ясно, что такие функции, составленные из истинностных функций, снова являются истинностными функциями. [10]
Всякое такое распределение истинностных значений для постоянных элементарных формул, если связки исчисления высказываний истолковывать как истинностные функции, естественным образом порождает распределение и для любых постоянных формул. При этом всякая постоянная формула однозначным образом оказывается либо истинной, либо ложной, а всякая постоянная формула, являющаяся результатом подстановки в тождественно истинную формулу исчисления высказываний, оказывается истинной. [11]
Как мы знаем, при истолковании формул исчисления высказываний, получающемся на основе понимания связок исчисления высказываний как истинностных функций, любая формула равнозначна некоторой конъюнкции, члены которой являются либо формульными переменными, либо отрицаниями формульных переменных - выражения этих двух типов мы будем называть п р и-марными вы р ажен и ями3), - либо дизъюнкциями, состоящими из нескольких примарных выражений. При этом упомянутая равнозначность имеет место в том смысле, что соответствующая конъюнкция задает ту же самую истинностную функцию, что и первоначальная формула. [12]
С учетом определений, данных нами для вычисления значений арифметических функций, а также истинностных значений равенств между цифрами и значений истинностных функций, всякая выводимая формула без переменных является истинной. [13]
Очевидно, что каждая истинностная функция, если она построена с помощью принятых здесь обозначений, задает формулу в смысле данного выше определения и, наоборот, каждую формулу можно рассматривать как истинностную функцию. Далее, должно быть ясно, что для того, чтобы приписать истинностное значение формуле А при данных истинностных значениях простых компонентов формулы Л, нужно рассмотреть структуру составной формулы А как функции. Когда это будет удобно, мы будем считать себя вправе рассматривать формулу как истинностную функцию. В таком случае простые компоненты ( символы-высказывания) будут рассматриваться как переменные, могущие принимать истинностные значения Тир. [14]
Для нашего доказательства непротиворечивости достаточно показать, что каждая выводимая формула без переменных при естественном распределении истинностных значений, складывающемся из выделенного распределения истинностных значений для равенства, рекурсивной процедуры вычисления постоянных сумм и произведений и из истолкования связок исчисления высказываний как истинностных функций, является истинной. Поэтому для нашего доказательства достаючно будет рассматривать только выводы формул без переменных. [15]