Длина - формула
Cтраница 1
Длина формулы, получаемой в результате описанной выше замены, превосходит длину исходной формулы не более чем в постоянное число раз. Таким образом, по данной формуле Е в КНФ можно найти, применяя описанное выше преобразование к каждой сумме, формулу Е в 3 - КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула. [1]
Простой индукцией по длине формулы можно показать, что определения ограниченной и неограниченной переменных в формуле непротиворечивы. [2]
Доказательство проводится индукцией по длине формулы а. Если а - пропозициональная переменная, то теорема 5.6 выполняется, поскольку а не будет ни тавтологией, ни интуиционистской тавтологией, Пусть а - не пропозициональная переменная. [3]
Доказательство проводится индукцией по длине формулы а. Если а - пропозициональная переменная, то теорема 5.6 выполняется, поскольку а не будет ни тавтологией, ни интуиционистской тавтологией, Пусть а - не пропозициональная переменная. В первом случае 3 и у ие содержат U и ф и, по предположению индукции, будут тавтологиями в том и только в том случае, когда они являются интуиционистскими тавтологиями, С другой стороны, ( Р П) является тавтологией ( интуиционистской тавтологией) в том и только в том случае, когда обе формулы р, у являются тавтологиями ( интуиционистскими тавтологиями) согласно общей теореме VI, 10.8. Таким образом, ( р П) - тавтология в том и только в том случае, когда ( р П) - интуиционистская тавтология. [4]
Несложное доказательство ( индукцией по длине формулы а) предоставляется читателю. [5]
 |
Последовательность преобразований для различных трудных задач. [6] |
Число узлов в G, очевидно, меньше длины формулы F, а число ребер не превосходит квадрата числа узлов. Поэтому граф G можно закодировать в виде цепочки, длина которой ограничена полиномом от длины формулы F, и, что еще важнее, такой код можно найти за время, ограниченное полиномом от длины F. Мы покажем, что G содержит g - клику тогда и только тогда, когда формула F выполнима. [7]
Доказательство равенства ( 5) ведется индукцией по длине формулы ГУ. [8]
Общий случай т степеней свободы почти ничем не отличается от приведенного, за исключением длины формул. [9]
Мы сводим - к сингулярному классу Ак-кермана так, чтобы сохранить выполнимость и увеличить длину формулы с п до ( в худшем случае) cn / los n, где с - константа. Совмещая это сведение с разрешающей процедурой из разд. [10]
Несложное доказательство ( 5) на основе теоремы IV, 1 4), проводимое индукцией по длине формулы а, мы здесь опускаем. [11]
Это завершает сведение 5 к 3 V3 - Sat. А так как длина формулы F будет О ( n log я), где п и, таким образом теорема будет доказана. [12]
Язык Jfa получается из Ьыы добавлением нового квантора Qa. Истинность формулы определяется индукцией по длине формулы. При этом формула ( Qax) ( B ( х) истинна в модели А, если мощность множества а а. [13]
Отображение а й понимается здесь, как в X, § 2, стр. Доказательство ( 7) ( индукцией по длине формулы а) опускается. [14]
Отображение alR понимается здесь, как в X, § 2, стр. Доказательство ( 7) ( индукцией по длине формулы а) опускается. [15]
Страницы: 1 2