Cтраница 3
Теорема 4.6. Для каждого п класс оп замкнут относительно операции ограниченного минимума. Отношения класса 1оп замкнуты относительно операций навешивания ограниченных кванторов и относительно операций исчисления высказываний. [31]
L может быть получен из L2 путем навешивания р-ограниченного квантора существования. Ясно, что такая машина распознает язык L за полиномиальное время. [32]
Пусть, наконец, Я есть ( п - Н) - местное отношение; тогда говорят, что ( п - Н) - местное отношение S получено из Я навешиванием ограниченного квантора общности2, если ( для любых р, j) Sp j имеет место тогда и только тогда, когда Vi j Rp, i. Если R Рекурсивно и S получается из Я навешиванием ограниченного квантора общности, то S Рекурсивно. [33]
Целесообразно обратить внимание на различие отношений сильной и слабой связи между агрегатами. Оно вытекает из различия равенств (8.19) и (8.25) - навешивание квантора общности на дизъюнкцию предикатов не эквивалентно навешиванию того же квантора на каждый из дизъюнктивных членов ( см. гл. Это различие хорошо интерпретируется на упомянутых графах. В отличие от сильно связанных агрегатов для слабо связанных агрегатов существование путей не обязательно, достаточно существование хотя бы одной цепи. [34]
Менее радикальный вариант состоит в том, чтобы разделить переменные на два типа - свободные и связанные. Тогда можно смело подставлять терм вместо свободной переменной, зато при навешивании квантора надо заменять свободную переменную на связанную. [35]
Мы говорим, что предикат S является рекурсивным, если S рекурсивно разрешим. Говорят, что S - арифметический предикат тогда и только тогда, когда S получен из некоторого рекурсивного предиката навешиванием кванторов. [36]
& замкнут относительно операций ограниченного суммирования и ограниченного умножения. Заметим, что, согласно следствию 1.2 и теореме 2.2 Ь, класс § замкнут относительно операций исчисления высказываний и операций навешивания ограниченных кванторов. [37]
Далее, х, х, х у, prime ( я), ехр ( л, y) t xNy, px суть функции и отношения класса §, поскольку они определены посредством функций и операций, о которых доказано, что они принадлежат Jf; это легко усмотреть из структуры их определений. Отсюда следует, что класс § замкнут относительно операции ограниченной рекурсии, так как в доказательстве теоремы 2.3 схема рекурсии была сведена к операциям ограниченного минимума, навешивания ограниченных кванторов и к функциям, описанным выше. [38]
Будем говорить, что S получено из R навешиванием ограниченного квантора существования. Аналогичным образом, любое отношение, полученное из Рекурсивного отношения навешиванием ограниченного квантора существования, Рекурсивно. [39]
Поставим себе задачу для каждой из 256 строк придумать такую двухместную высказывательную форму 51 ( А:, у), чтобы истинностные значения восьми высказываний ( 15) - ( 22), полученных навешиванием на нашу форму восьми возможных двухкванторных приставок, совпадали с соответствующими истинностными значениями рассматриваемой строчки. Разумеется, эта задача невыполнима. Заменим поэтому табл. 3 на табл. 4, в которой это свойство операции навешивания кванторов учтено. [40]