Попереджання нормальна форма
Кажуть, що формула знаходиться в попереджання нормальній формі, якщо все квантори в ній винесені наліво, тобто якщо вона має вигляд
де - квантори загальності або існування, - змінні, а - бескванторная формула. Ця формула може мати параметри (якщо формула має параметри, відмінні від).
Основний результат цього розділу свідчить, що будь-яка формула (доказово) еквівалентна деякій формулі в попереджання нормальній формі (попереджання формулою). Ми доведемо його, одночасно побудувавши деяку класифікацію формул (в якомусь сенсі відображає їх "логічний складність"). В якості запобіжного складності можна було б взяти число кванторів в попереджання нормальній формі. Але правильніше враховувати число груп кванторів (вважаючи однойменні поруч стоять квантори за один).
Кажуть, що попереджання формула є - формулою, якщо її кванторная приставка містить груп кванторів, причому першими стоять квантори існування. Якщо першими стоять квантори загальності. говорять про класі. (Аналогічні позначення використовуються в теорії алгоритмів для класифікації арифметичних множин, см. [5]).
Приклад: формула належить класу, формула належить класу, а формула взагалі не знаходиться в попереджання нормальній формі.
103. Вказати формулу в попереджання нормальній формі, доказово еквівалентну останньої з перерахованих формул.
Нас цікавить, що відбувається з вимірюваної таким чином "логічної складністю" формули при логічних операціях. Почнемо з зовсім простих спостережень.
- Будь-яка формула з класу або доказовою еквівалентна формулі з класу, а також формулою з класу. Справді, якщо формула не має параметра, то вона буде доказовою еквівалентна формулами і (одна імплікація є аксіомою, інша виходить з за правилом Бернайса). Таким чином, можна додати фіктивний квантор в початок кванторного приставки або в її кінець; у другому випадку треба послатися на лемму 2.
- Заперечення будь-якої формули з класу доказово еквівалентно деякої формулою з класу і навпаки. Справді, ми бачили, що виводиться еквівалентно і навпаки, так що заперечення можна проносити всередину, змінюючи по ходу справи квантори на двоїсті.
Покажемо, що кон'юнкція двох формул з доказовою еквівалентна деякій формулі з. Наприклад, кон'юнкція доказово еквівалентна формулі. Справді, використовуючи аксіоми про квантор загальності, можна з вивести, а з вивести, тому з їх кон'юнкції виводиться, після чого можна навісити два квантора загальності. В іншу сторону: виводимо формулу, потім застосовуємо правило Бернайса і т. Д.
104. Покажіть, що можна заощадити один квантор і використовувати формулу.
Загальна міркування (для будь-яких двох формул з класу) майже настільки ж просто, треба лише перейменувати зв'язані змінні, користуючись теоремою 52.
Покажемо тепер, що кон'юнкція двох формул з класу доказово еквівалентна формулі класу і що диз'юнкція двох формул класу доказово еквівалентна формулі класу. Для цього треба скористатися еквівалентності виду
Зазначені еквівалентності, як легко бачити, загальнозначимі і тому виводяться. Це зовсім просто зрозуміти для першої з них (щоб знайти пару об'єктів із заданими властивостями, треба знайти окремо перший і другий члени пари). Друга еквівалентність трохи складніше - найпростіше помітити, що вона переходить в першу при додаванні заперечення. (Велика складність відображає той факт, що друга еквівалентність, на відміну від першої, не є інтуїционістському вірною.)
Тепер легко зрозуміти, що кон'юнкція і диз'юнкція двох формул з класу (або доказовою еквівалентні формулам з того ж класу. Справді, за допомогою зазначених вище еквівалентностей можна злити кванторние приставки. Наприклад, формула
доказово еквівалентна спочатку формулою
а потім формулою