§ 8. Правила перестановки кванторів
Нехай А – довільна формула логіки предикатів. Розглянемо А довільну, але фіксовану інтерпретацію. Відразу з визначення кванторов отримуємо, що там, де істинно х у А , істинно і у х А , і
навпаки. Через довільність інтерпретації слід, що
Точно також отримуємо що
чином, при зміні місць, що стоять поруч
Кванторів отримуємо рівносильні формули. Отже, однойменні квантори, що стоять поряд, можна переставляти місцями.
Відомо, що формули А та В рівносильні тоді і тільки тоді, коли
є логічно загальнозначущою формулою (теорема 2.2). Тоді з
(2.16) та (2.17) отримуємо, що формули
х у А ≡ у х А і х у А ≡ у х А
є логічно загальнозначущими.
Різноіменні квантори, виявляється, можна переставляти не завжди.
Теорема 2.5. Для кожної формули А та будь-яких предметних
змінних х і у формула
логічно загальнозначима, а зворотна імплікація, тобто. формула
не завжди є логічно загальнозначущою.
Доведення . Для доказу логічної загальнозначимості формули (2.18) фіксуємо довільну інтерпретацію формули А , і з визначень кванторів одразу отримуємо, що формула (2.18) є істинною. Таким чином, у будь-якій інтерпретації формула (2.18) істинна, отже, вона є логічно загальнозначущою.
Щоб довести, що формула (2.19) не завжди є логічно загальнозначущою, достатньо навести приклад формули А та інтерпретації для неї, де формула (2.19) не є істинною. Нехай область інтерпретації M - безліч дійсних чисел і формула А означає предикат х, тоді
означає, що для будь-якого числа у існує число х більше, ніж у . Цей вислів істинний. Висловлювання, отримане з (2.20) перестановкою кванторів ху(х>у) , означає, що існує число х більше будь-якого іншого числа і, очевидно, є хибним. Тоді помилкова імплікація: у х(х) х у(х). Отже, формула (2.19) не істинна наведеної інтерпретації, тобто. не є логічно загальнозначущою. Теорему доведено.
Зауважимо, що в окремому випадку формула (2.19) може виявитися і логічно загальнозначущою, наприклад, коли А є замкнутою формулою. У цьому випадку, як відомо (див. § 6), формула А дорівнює формулі Q 1 Q 2 . Q n А де Q 1 ,Q 2 . Q n будь-яка сукупність кванторів. Тому формула (2.19) буде логічно загальнозначущою.
Проте підкреслимо вкотре, що з довільної формули перестановка різноіменних кванторов який завжди призводить до рівносильним формулам.
§ 9. Правила перейменування пов'язаних змінних
Розглянемо формули хА(х) та уА(у) . Очевидно, що в кожній інтерпретації з істинності першої слідує істинність другої, і навпаки, тому ці формули рівносильні: хА(х)
Таким чином, перейменування змінної х на у кванторі і в області дії цього квантора призвело до формули рівносильної вихідної.
У математичному аналізі є аналогічне правило. Наприклад, заміна змінної у підінтегральному вираженні певного інтегралу не змінює його величини:
cos x dx = ∫ cos y dy
Так само в сумі індекс підсумовування можна перейменовувати:
В останньому прикладі перейменовується n на k, але не можна перейменовувати m, бо це вільна змінна.
У формулі хА(х) можна замінити змінну х на у. Зрозуміло, якщо х замінити будь-який інший змінної, то отримана формула буде рівносильна вихідної. Можна показати, що й у довільній формулі
перейменування (заміна) пов'язаних змінних на будь-які іншіпризводить до формули рівносильної вихідної. Маючи на увазі подальші програми, дотримуватимемося наступного правила перейменування пов'язаних змінних.
Нехай А – довільна формула логіки предикатів. Формулу А 0 отримаємо з А заміною пов'язаних змінних іншими змінними, відмінними від усіх вільних змінних формули А , причому змінна змінна, що замінюється, у формулі А повинна змінюватися однаковим чином всюди в області дії квантора, що зв'язує дану змінну і в самому кванторі. Тоді А 0 рівносильна А .
При перейменуванні пов'язаних змінних ми повинні перейменовувати їх усюди, де вони входять у формулу А , лише змінну обраного нами квантора й області дії цього квантора. Це означає, що однакові змінні, котрим пов'язують їх квантори мають різні області дії, можуть перейменовуватися по-різному чи одне їх може перейменовуватися, іншу ні.
Розглянемо дію наведеного правила на прикладах. Нехай маємо
Перейменувавши пов'язану змінну х на у , у першій посилці отримаємо формулу, рівносильну вихідній:
З формули (3.21) перейменуванням можна отримати формулу
При цьому кожна отримана формула буде рівнозначною вихідною формулою
Зазначимо ще раз, що перейменовуються лише пов'язані змінні, а вільні не чіпаються. Так, у формулі (2.21) останнє входження х вільно, тому за будь-яких перейменування вона залишається незмінною.
Розглянемо ще один приклад. Нехай задана формула
х(уР(х,у) уQ(х,у) R(х)). (2.22)
Перейменовуючи в цій формулі змінну х, ми повинні замінити її однаковим чином усюди, де вона входить, бо х у формулі (2.22) є або змінною квантора, або знаходиться в дію квантора. Наприклад,перейменувавши х на z отримаємо наступну формулу, рівносильну вихідної:
У формулі (2.22) змінну можна перейменувати в першій посилці, наприклад, на змінну v , а в другій залишити без зміни, або замінити, наприклад, змінної u . У разі отримаємо формулу: х( vР(х,v) uQ(х,u) R(х)). Якщо врахувати ще перейменування
змінної х , маємо: z( vР(z,v) uQ(z,u) R(z)) . Отримані формули теж рівні вихідній формулі (2.22).
§ 10. Правила винесення кванторів за дужки. Попередня нормальна форма
З'ясуємо, яким чином виносяться квантори за дужки, при цьому отримаємо правила внесення кванторів під дужки.
Теорема 2.6. Нехай А позначає формулу, що не має вільних входження змінної х, В (х) і C (х) формули, можливо, і містять вільні входження х. Тоді: