Cтраница 3
Любая конъюнкция общезначима тогда и только тогда, когда общезначимы ее сомножители, в данном случае, A ID В и В А. Другими словами, если уметь выводить общезначимые формулы вида A ID В и располагать правилом вывода если выводимы А и В, то выводимо А & В, то все общезначимые формулы, которые можно трактовать как эквивалентности, будут выводимы. Таким образом, в отличие от других логических операций, мы трактуем знак не как фундаментальную логическую связку, смысл которой раскрывается независимыми аксиомами, а как обозначение более сложной конструкции, вводимое ради сокращения письма. [31]
Целью логики предикатов является описание класса всех общезначимых формул. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. [32]
Важно также свойство непротиворечивости, суть которого сводится к тому, что исходная система аксиом и правил вывода не должна давать возможность выводить формулы, не принадлежащие заданному множеству формул с выбранными свойствами. Например, полные системы аксиом и правил вывода в классическом исчислении предикатов первого порядка позволяют получить любую общезначимую формулу из множества общезначимых формул и не дают возможности получить какие-либо формулы, не обладающие этим свойством. [33]
Целью логики предикатов является описание класса всех общезначимых формул. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. [34]
Приведенное описание отношения л с помощью подмножества V множества S остается безнадежно туманным, пока мы не интерпретируем S как множество формул исчисления высказываний. При такой интерпретации становится видно, что fi должно интерпретироваться как отношение eq, a V как множество общезначимых формул. В итоге описание отношения fi с помощью V сводится к следующему: две формулы s и t эквивалентны тогда и только тогда, когда эквиваленция s - W - общезначимая формула. Подозрение, что такая интерпретация множества S лежала в основе программы построения рассматриваемой формальной системы, вполне обосновано. [35]
Важно также свойство непротиворечивости, суть которого сводится к тому, что исходная система аксиом и правил вывода не должна давать возможность выводить формулы, не принадлежащие заданному множеству формул с выбранными свойствами. Например, полные системы аксиом и правил вывода в классическом исчислении предикатов первого порядка позволяют получить любую общезначимую формулу из множества общезначимых формул и не дают возможности получить какие-либо формулы, не обладающие этим свойством. [36]
Общезначимые формулы в логике предикатов играют ту же роль, что тавтологии в логике высказываний. Между ними есть и формальная связь: если взять любую тавтологию и вместо входящих в нее пропозициональных переменных подставить произвольные формулы сигнатуры а, получится общезначимая формула. Тогда каждая из подставленных формул станет истинной или ложной, а значение всей формулы определяется с помощью таблиц истинности для логических связок, то есть по тем же правилам, что в логике высказываний. [37]
Любая конъюнкция общезначима тогда и только тогда, когда общезначимы ее сомножители, в данном случае, A ID В и В А. Другими словами, если уметь выводить общезначимые формулы вида A ID В и располагать правилом вывода если выводимы А и В, то выводимо А & В, то все общезначимые формулы, которые можно трактовать как эквивалентности, будут выводимы. Таким образом, в отличие от других логических операций, мы трактуем знак не как фундаментальную логическую связку, смысл которой раскрывается независимыми аксиомами, а как обозначение более сложной конструкции, вводимое ради сокращения письма. [38]
В следующей теореме дается перечень некоторых основных общезначимых формул. Поскольку формулы теоремы 2.4 распространяются и на исчисление предикатов, мы будем нумеровать помещаемые ниже формулы как продолжение формул, приведенных в указанной теореме, чтобы подчеркнуть, что здесь вводятся дополнительные общезначимые формулы исчисления предикатов. [39]
В самом деле, термы в У исчерпываются свободными индивидными переменными. Однако ни одна из формул р ( х) не является теоремой в У, ибо легко определить семантическую модель для 7 -, в которой р ( х) не будет общезначимой формулой. С другой стороны, теория Т сильно проста. [40]
Чтобы проверить, является ли формула тавтологией, достаточно подставить в нее все возможные наборы значений переменных. Хотя этот процесс может быть на практике невыполним ( наборов слишком много), теоретически мы имеем простой алгоритм проверки, является ли формула тавтологией. Для общезначимых формул в общем случае такого алгоритма не существует ( теорема Черча; ее доказательство можно прочесть в [5]); он есть только для очень ограниченных классов формул. Чуть более сложен случай с одноместными предикатами. [41]
Квантор общности в формуле yxF ( x) рассматривается в этом случае как сокращение для бесконечной конъюнкции F ( tj) & F ( t2) &... Так, законам де Моргана соответствуют общезначимые формулы классич. [42]
Целью логики высказываний является описание класса всех общезначимых формул при данной интерпретации. Одним из способов такого описания является построение В. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. Наиболее часто при построении В. [43]
Целью логики высказываний является описание класса всех общезначимых формул при данной интерпретации. Одним из способов такого описания является построение В. При этом в качестве аксиом выбираются нек-рые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы. Наиболее часто при построении В. [44]
Кроме того, определяются - в точности так же, как в § 2.7, - понятия связанного вхождения и свободного вхождения переменной в формулу и понятия переменной, связанной в формуле и свободной в формуле. Вводится также понятие подстановки одной переменной вместо другой. Наконец, на описываемое исчисление переносится описанная в § 2.8 процедура оценки, приводящая к понятию общезначимой формулы. [45]