Пропозициональная формула

Cтраница 2

Очевидно, что если в пропозициональную формулу вместо всех пропозициональных переменных подставить какие-нибудь формулы языка первого порядка, то получится формула языка первого порядка. [16]

Теорема 6 была сформулирована в терминах пропозициональных формул. Но, в силу правила подстановки ( теорема 3, § 25), она применима и к формулам в других смыслах, лишь бы при этом А, В, Сд получались из пропозициональных формул одновременной подстановкой формул вместо пропозициональных букв. [17]

Этим доказана непротиворечивость исчисления высказываний в терминах пропозициональных формул. Если А и - i A - доказуемые формулы исчисления с другим понятием формулы, то, в силу обратного правила подстановки ( теорема 4 § 25), имеются доказуемые пропозициональные формулы А и - i А. Таким образом, непротиворечивость распространяется и на случаи формул в других смыслах. [18]

Программа, управляемая образцами, для автоматического доказательства теорем. [19]

Остается еще один вопрос: как преобразовать заданную пропозициональную формулу в конъюнктивную нормальную форму. [20]

Если при некотором применении правила вывода посылки являются тождественно истинными пропозициональными формулами, то и заключение является тождественно истинной пропозициональной формулой. [21]

Если А, В, Сд и Св - пропозициональные формулы, связанные друг с другом, как в предыдущем определении замены, то А-В ь - СА-СВ. [22]

Если А - пропозициональная формула, то - iA - пропозициональная формула. [23]

Булева функция и задающая ее формула. [24]

Любая булева функция п аргументов может быть записана в виде пропозициональной формулы. [25]

В § 3 главы 2 было введено понятие тавтологии как пропозициональной формулы, которая превращается в истинное высказывание при любой подстановке в нее конкретных высказываний вместо пропозициональных переменных. Распространим понятие тавтологии на формулы языка первого порядка. [26]

Очевидно, что истинностное значение высказывания, полученного подстановкой в пропозициональную формулу конкретных высказываний вместо пропозициональных переменных, зависит только от истинностных значений подставляемых высказываний. Поэтому довольно легко можно проверить, является ли данная пропозициональная формула тавтологией. Для этого достаточно перебрать всевозможные подстановки в эту формулу значений И и Л вместо пропозициональных переменных ( таких подстановок ровно 2П, где п - число переменных в формуле), и для каждой такой подстановки вычислить соответствующее значение формулы, пользуясь истинностными таблицами для логических операций. Формула является тавтологией тогда и только тогда, когда при любой подстановке она принимает значение И. [27]

Существует ли способ для выяснения в конечное число шагов тождественной истинности произвольной пропозициональной формулы. Как следует видоизменить определение пропозициональной формулы, чтобы все такие формулы можно было бы записывать словами конечного алфавита. [28]

Предположим, что методами § § 52 и 56 построена геделевская нумерация для пропозициональных формул с цифрами. Пусть Н ( а) а - геделевский номер формулы, принадлежащей FJ; тогда предикат Н рекурсивен. [29]

Предикатная формула с цифрами, не содержащая ни свободных, ни связанных переменных, называется пропозициональной формулой с цифрами. [30]

Страницы: 1 2 3 4