Cтраница 2
Тесно связанное с постоянством ( непостоянством) различие между двумя типами эмплиативных функций состоит в их отношении к композиции: все функционально-составные эмплиативные функции перестановочны друг с другом: ( Л о В В о А), а функции - т неперестановочны ни друг с другом, ни с истинностными функциями. [16]
Тесно связанное с постоянством ( непостоянством) различие между двумя типами эмплиативных функций состоит в их отношении к композиции: все функционально-составные эмплиативные функции перестановочны друг с другом: ( Л о В В о Л), а функции - г неперестановочны ни друг с другом, ни с истинностными функциями. [17]
А теперь мы определим функцию Ф5 ( / и), которая в том случае, когда т является номером формулы, построенной из символа V с помощью связок исчисления высказываний, принимает значение 0 или 1 в зависимости от того, чему равно ( V или - ] V) истинностное значение этой формулы, получающееся в результате естественного истолкования связок исчисления высказываний как истинностных функций. [18]
Существует 22 различных истинностных функций от п йеременных. Из шестнадцати функций истинности, соответствующих л 2, мы выделяем четыре. [19]
Хотя внешне осмысленность и истинность выражений формальной системы, казалось бы, не играет никакой роли, в действительности аксиомы и правила вывода формулируются так, что всегда существует их приемлемая интерпретация. Интерпретацией для исчисления высказываний может служить теория истинностных функций, в которой переменные рассматриваются как пропозициональные переменные, принимающие значения из множества истина, ложь, а связки рассматриваются как функции. Тогда в качестве аксиомы выбирают выражения, определяющие тождественно истинные функции - функции, принимающие значение истина на всех наборах. Может быть показано, что всякая теорема исчисления высказываний определяет тождественно истинную функцию и всякая формула, определяющая тождественно истинную функцию, является теоремой исчисления высказываний. Отметим, что формальная система с таким множеством теорем не единственна. [20]
В работе [2] Янов ввел простую абстрактную модель мантийной программы ( под названием схемы программы), основанную на представлении программы в виде конечной линейной последовательности операторов двух типов: вычислительных операторов и операторов условного перехода по одному из двух направлений. Команды перехода, управляющие порядком, в котором выполняются операторы, зависят от значения пропозициональных истинностных функций конечного числа переменных; значения последних ( истина или ложь) могут изменяться при выполнении того или иного вычисления. Ни один из вычислительных операторов и ни одна из булевых функций не интерпретированы ( т.е. их значения или-интерпретация отсутствуют), так что схема программы может быть представлена как семейство машинных программ, каждый член которого является допустимой интерпретацией схемы. Свойства абстрактных схем этого типа не зависят от какой-либо конкретной машины или языка программирования и выполняются в программах, записанных на любом языке, который обладает последовательност-ными и контролирующими характеристиками, предполагаемыми в модели. Основные результаты, полученные Яновым, заключаются в существовании двух алгоритмов: алгоритма, который для любой пары схем устанавливает, представляют ли они при всех интерпретациях одни и те же программы ( т.е. являются эквивалентными) или нет, и алгоритма, переводящего схему в эквивалентную ей простую каноническую форму. [21]
А истинностное значение этой формулы вычисляется в соответствии с нашим пониманием связок исчисления высказываний как истинностных функций. [22]
S есть элемент из S и каждые конъюнкция, дизъюнкция, импликация и эквиваленция двух любых элементов множества S является элементом из S. Поскольку было условлено, что два элемента множества S будут считаться неразличимыми, если они дают одинаковые истинностные функции ( это отношение eq для формул), и поскольку было показано, что каждая формула эквивалентна такой, в которой нет других связок, кроме не и и, мы можем принять ( и примем), что S есть просто замыкание множества 50 по отношению к этим связкам. [23]
Как мы знаем, при истолковании формул исчисления высказываний, получающемся на основе понимания связок исчисления высказываний как истинностных функций, любая формула равнозначна некоторой конъюнкции, члены которой являются либо формульными переменными, либо отрицаниями формульных переменных - выражения этих двух типов мы будем называть п р и-марными вы р ажен и ями3), - либо дизъюнкциями, состоящими из нескольких примарных выражений. При этом упомянутая равнозначность имеет место в том смысле, что соответствующая конъюнкция задает ту же самую истинностную функцию, что и первоначальная формула. [24]
Эти функции на самом деле являются таблицами истинности, имеющими требуемые значения О, 1 для значений О, 1 переменных: функция а, связанная с доказуемым предложением А, удовлетворяет доказуемому равенству а 0 ( доказуемому, например, в исчислении равенств) и, обратно, предложение А доказуемо ( в некоторой формализации логики предложений), если равенство й 0 доказуемо. Обратно, если равенство а 0 доказуемо, то предложение Л, соответствующее а, доказуемо, ибо функция а является истинностной функцией для А, которая имеет значение О ( истина) для всех значений ( включая О, 1) своих переменных, а всегда верное предложение доказуемо. [25]
Так как в формализме ( Z) после добавления к нему вычислимых функций все элементарные формулы будут по-прежнему являться равенствами), то мы должны будем рассмотреть только такие нумерические формулы, которые строятся из нумерических равенств с помощью связок исчисления высказываний. Для такого рода формул их истинностные значения однозначно получаются из истинностных значений составляющих их элементарных формул на основе понимания связок исчисления высказываний как истинностных функций. Подобно тому, как это делалось раньше2), формулу без связанных индивидных и без формульных переменных мы будем называть верифицируемой, если она при любой подстановке цифр вместо всех входящих в нее свободных индивидных переменных переходит в истинную нумерическую формулу. [26]
Условимся теперь называть формулу А эквивалентной ( равносильной) формуле В ( символическая запись: A eq Б), если они равны как истинностные функции для перечня переменных Рх, Р2 / я гДе каждое Р входит в качестве простого компонента по меньшей мере в одну из формул А и В. Если пользоваться истинностными таблицами, то приведенное определение сводится к следующему. [27]
Истинностное значение любой такой формулы вполне определяется нашим способом вычисления функциональных выражений, строящихся с помощью знаков, , и б, на основе выделенного распределения истинностных значений для равенства, а также нашей трактовки связок исчисления высказываний как истинностных функций. [28]
Теперь, прежде чем перейти к арифметизации понятия вывода, мы рассмотрим вопрос о том, как с помощью арифметического перевода может быть оформлена процедура вычисления тех истинностных значений бескванторных формул, которые получаются в результате произвольного приписывания каждой элементарной формуле одного из значений истина или ложь и истолкования связок исчисления высказываний как истинностных функций. [29]
Очевидно, что каждая истинностная функция, если она построена с помощью принятых здесь обозначений, задает формулу в смысле данного выше определения и, наоборот, каждую формулу можно рассматривать как истинностную функцию. Далее, должно быть ясно, что для того, чтобы приписать истинностное значение формуле А при данных истинностных значениях простых компонентов формулы Л, нужно рассмотреть структуру составной формулы А как функции. Когда это будет удобно, мы будем считать себя вправе рассматривать формулу как истинностную функцию. В таком случае простые компоненты ( символы-высказывания) будут рассматриваться как переменные, могущие принимать истинностные значения Тир. [30]