§ 8. Правила за пермутация на квантори
Нека A е произволна предикатна логическа формула. Помислете за произволна, но фиксирана интерпретация. Веднага от дефиницията на кванторите получаваме, че когато x y A е вярно, y x A също е вярно и
обратно . Поради произволността на тълкуването следва, че
По същия начин получаваме това
По този начин, когато сменяте местата, стоящи наблизо
квантори, получаваме еквивалентни формули. И така, кванторите със същото име, стоящи един до друг, могат да бъдат пренаредени.
Известно е, че формули A и B са еквивалентни тогава и само тогава
е логически валидна формула (теорема 2.2). Тогава от
(2.16) и (2.17) получаваме, че формулите
x y A ≡ y x A и x y A ≡ y x A
са логически валидни.
Оказва се, че противоположните квантори не винаги могат да бъдат пренаредени.
Теорема 2.5. За всяка формула А и всеки предмет
формула за променливи x и y
логически валиден, а обратната импликация, т.е. формула
не винаги е логически валиден.
доказателство За да докажем логическата валидност на формула (2.18), фиксираме произволна интерпретация на формула A и от дефинициите на кванторите веднага получаваме, че формула (2.18) е вярна. По този начин, във всяка интерпретация, формула (2.18) е вярна, следователно, тя е логически валидна.
За да се докаже, че формула (2.19) не винаги е логически валидна, е достатъчно да се даде пример за формула А и нейната интерпретация, където формула (2.19) не е вярна. Нека областта на интерпретация M е набор от реални числа и формулата A означава предиката x>y, тогава
означава, че за всяко число y има число x, по-голямо от y. Това твърдение е вярно. Твърдението, получено от (2.20) чрез пренареждане на кванторите xy(x>y), означава, че има число x, по-голямо от всяко друго число и очевидно е невярно. Тогава импликацията е невярна: y x(x>y) x y(x>y). Следователно формула (2.19) не е вярна в дадената интерпретация, т.е. не е логически валиден. Теоремата е доказана.
Отбелязваме, че в конкретен случай формула (2.19) може да се окаже и логически валидна, например когато A е затворена формула. В този случай, както е известно (виж § 6), формулата A е еквивалентна на формулата Q 1 Q 2 . Q n A , където Q 1 , Q 2 . Q n е всяка колекция от квантори. Следователно формула (2.19) ще бъде логически валидна.
Въпреки това подчертаваме още веднъж, че за произволна формула пермутацията на различни квантори не винаги води до еквивалентни формули.
§ 9. Правила за преименуване на обвързани променливи
Разгледайте формулите xA(x) и yA(y). Очевидно във всяка интерпретация истинността на първото предполага истинността на второто и обратно, така че тези формули са еквивалентни: xA(x)
Така преименуването на променливата x на y в квантора и в обхвата на този квантор доведе до формула, еквивалентна на оригиналната.
Подобно правило има и в математическия анализ. Например промяната на променлива в интегралната функция на определен интеграл не променя стойността му:
cos x dx = ∫ cos y dy
По същия начин, в сумата, индексът на сумиране може да бъде преименуван:
Последният пример преименува n на k, но не можете да преименувате m, защото това е свободна променлива.
Във формулата xA (x) можете да замените променливата x с y. Ясно е, че ако x се замени с друга променлива, тогава получената формула ще бъде еквивалентна на оригиналната. Може да се покаже, че в произволна формула
преименуване (замяна) на обвързани променливи с всякакви другиводи до формула, еквивалентна на оригиналната. Имайки предвид бъдещи приложения, ще се придържаме към следното правило за преименуване на обвързани променливи.
Нека A е произволна предикатна логическа формула. Получаваме формулата A 0 от A, като заменим свързаните променливи с други променливи, които са различни от всички свободни променливи на формулата A, и заменената променлива във формула A трябва да се промени по същия начин навсякъде в обхвата на квантора, свързващ тази променлива, и в самия квантор. Тогава A 0 е еквивалентно на A .
Когато преименуваме обвързани променливи, ние не сме длъжни да ги преименуваме навсякъде, където влизат във формула A, а само променливата на избрания от нас квантор и в обхвата на този квантор. Това означава, че едни и същи променливи, за които кванторите, които ги свързват, имат различни обхвати, могат да бъдат преименувани по различни начини или една от тях може да бъде преименувана, докато другата не.
Разгледайте действието на горното правило с примери. Нека имаме
Преименувайки обвързаната променлива x на y, в първата предпоставка получаваме формула, еквивалентна на оригиналната:
От формула (3.21) чрез преименуване може да се получи формулата
В този случай всяка получена формула ще бъде еквивалентна на оригиналната формула
Обърнете внимание отново, че само обвързаните променливи се преименуват, а свободните не се докосват. По този начин във формула (2.21) последното срещане на x е свободно, така че остава непроменено при всяко преименуване.
Нека разгледаме още един пример. Нека формулата
x( yP(x, y) yQ(x, y) R(x)). (2.22)
Преименувайки променливата x в тази формула, трябва да я заменим по същия начин, където и да влезе, защото x във формулата (2.22) е или кванторна променлива, или е в обхвата на квантора. Например,преименувайки x на z, получаваме следната формула, еквивалентна на оригиналната:
Във формула (2.22) променливата y може да бъде преименувана в първата предпоставка, например в променливата v, и да остане непроменена във втората или да бъде заменена, например, с променливата u. В последния случай получаваме формулата: x( vР(х, v) uQ(х, u) R(х)). Като се има предвид преименуването
променлива x , тогава имаме: z( vР(z,v) uQ(z,u) R(z)) . Получените формули също са еквивалентни на оригиналната формула (2.22).
§ 10. Правила за поставяне в скоби на квантори. Пренекс нормална форма
Нека разберем как кванторите се изваждат извън скоби и в този случай ще получим и правилата за въвеждане на квантори в скоби.
Теорема 2.6. Нека A означава формула, която няма свободни срещания на променливата x, B (x) и C (x) формули, вероятно, и съдържа свободни срещания на x. Тогава: