Колмогоров, Драгалин - Введение в математическую логику (947386), страница 17
Текст из файла (страница 17)
Допустим еше, что А/~ ) В, и получим противоречие. Из первоге допущения следует, что а) 1А или Ь) В, а из второго — 1то А и ~В. В случае а) имеем противоречие А и 1 'А, а в спучае Ь) — проти.воречие В и 1 В. Наконец, есть еще способ установить 1аш логический закон. Достаточно формально проверить, 1то наша формула как булева комбинация А и В является пропозициональной тавтологией: -] А ~/ В =~ -1 (А /~ -) В) о О 1 О О о О' 1 О 1 1 ' 1 1 о о о о о о о о о о Покажем теперь ) ~х 1А 'ухА.
Нашу формулу можно рассматривать гак булеву комбинацию формул ~х ~4, '(гхА, но она не является пропознциональной тавтологией: ~х 1А => ~хА о ' о о о Допустим М 1= Нх 1 (АО) Тем не менее. это — логический закон, что мы и установим, ' учитывая кванторную структуру формулы. Итак, пусть М вЂ” произвольная модель языка, а 0 — произвольная оценка для нашей формулы. Переменная х не входит свободно в нашу формулу, так что можно считать оот О=Рч(А)'~ (х). Проделав подстановку по правилам п. 2 $ 2, можно считать, что необходимо доказать М~ ~~ х 1(АО) =з)Ух(АО). и докажем М 1='ух(А8), т. е.
что для всякого объекта аеиР, М)=(А0);. Предположим противное,'т. е, что для некоторого,а~Р„неверно, что М~ю(А0)",. Тогда для этого я имеем.М~ 1(А0)", и, значит,М)=~х 1(А0), что, однако, противоречит первому допущению. Пусть Р— двуместная атомарная буква некоторого языка. Докажем, что формула )~х~ уР(х, у):з Д уу)хР(х, у) яе является логическим законом. С этой целью нужно подобрать модель и оценку, в которой эта формула ложна. Об оценке можно пока не беспокоиться, так как наша формула замкнута, является предположением и сама по себе, как известно, является оцененной формулой (строго говоря, можно взять пустую оценку) Модель же должна быть такова, чтобы посылка была истинной, а заключение — ложным (тогда и вся импликация будет ложной).
Пусть х и у пробегают натуральные числа, а Р(х, у) интерпретируется как х у. Тогда, очевидно, е М)Ух5уР(х, у) и неверно, что ы)=3 ц ~ хР(х, у). Упражнение. Покажите, что следующие формулы не являются логическими законами. Здесь Р, Я, Р(х, у)' суть атомарные формулы. ОР= Е .а 'Р, 2) Д хР(х):э~ хР(х), 3) )ух~ уР(х, у):э~ у)ухР(х, у), 4) З хР(хВ ЗхЕ(х) =. Зх(Р(х) Л О(х)), 5) у'х(Р(х) ~у Я(х)):эЦ хР(х) ~/)т'хЦ(х), б) )УхР (х, х):э ~ х\~ уР (х, у), У) Эх3уР(х, у) ~3хР(х, х), 8) Р(х) ~ЪУхР(х), 9) 3 хР-(х):» Р(х), 10) )АР (х, у) ж )~ у Р ( у, у), И) ЭхР(х, у)= — ~уР(у, у). 8Т 3.
Две формулы А и В называются логически эквивалент' ными, если АмвВ есть логический закон. Мы будем инсат ' А В вместо «А логически эквивалентно В», т. е. вмест А — В. Как доказать А В? Следует установить два факта: )= А:эВ, )=В~А, т. е. для произвольной модели М и оцен, ки й для формулы А~В следует, допустив ММ Аб, доказат МПВО, а затем, допустив М= В0, доказать М~=АО. 4. Упомянем о некоторых логических законах. Вывод и предоставляется читателю.
Законы де Моргана: 1. ~(А~/В) — 1А Л 1В, 2. 1(А Л В) — ~ А ~/ т) В, 8. ~)УхА -~х 1А, 4. ~ ~ хА - у' х ) А. Закон контрапозиции: б. А:э — ~В:з ~А. Формула 1 В~ |А называется коятрапозицией формулы А~В. Закон двойного отрицания: б. 1 1А — А. В следующих восьми эквивалентностях формула А не содержит свободно переменной х. Одностороннее пронесение' ,нванторов: 7 АЛ~хВ(х) — ~ух(АЛВ(х)), 8. А~/)ухВ(х) ~х(А~/В(х)), У. А Л ДхВ;(х) 3 х(АЛВ(х)), 10. А~/Д хВ(х) — ~ х(А ~/ В(х)), 11.
А ~ 3 х В (х) — 3 х (А ~ В (х)), И. А ~)ухВ(х) — ~х(А~В(х)), 13. '1гхВ(х) ~А — Я х (В(х) ~А), И. ~хВ(х) ~А — ~х(В(х)'=)А). Если допустить, что формула А мбжет содержать свобод- но переменную х, то законы пронесения кванторов уже не имеют столь совершенного вида: 18. ~/хА(х) М~хВ(х)' — )Ух(А(х) Л В(х)), вз 16. ~ х А (х) ~1 ~ х В (х) — ~ х (А (х) ~„' В (х)), 17.
~Эх(А(х) ЛВ(х)) ~3хА,(х) д ~хВ(х), 1В. )=~хА(х) ~1)Ух В(х) ~ ~х(А (х) ~1 В(х)). Пусть теперь А — формула, х,-у — различные перемен- ные одного сорта, причем у не входит свободно в А. Тогда имеют место следующие законы переименования кванторов: 19. 'фхА — у'у(А(х(у)), 20. ~ х А — ~ у (А (х ~ у)). Сокращенно такого рода законы записывают просто кам 'у'хА(х) у'уА(у).
Не следует, однако, забывать, что такая эквивалентность верна лишь при соблюдении сделанных выше оговорок. 5. Имеется также несколько важных, простых и интуи- . тивно очевидных правил, позволяющих преобразовывать эквивалентным образом формулы. Они могут быть, конечно, точно доказаны, исходя из точных определений, но мы не будем здесь на этом останавливаться.
21. Если А = В, то А — В. 22. Если А — В, то А(хт, ..., хЯ~~1„..., ~ь)— В(;,"..'.,'х,11,",...','1„). Далее, мы хотели бы получить аналогичный результат для замены внутри формулы некоторой подформулы на эк- вивалентную. Например, кажется, что следующие две фор- мулы эквивалентны: й(х) ~1 'фх ~~(х(~(х,х); Й(х) ~/~х Дх ~(~(х, х), так как они получаются заменой подчеркнутой формулы по закону де Моргана. Естественно считать, что, например, пер- вая из рассматриваемых формул получена из формулы т((х) ~l )у хР (и) путем подстановки вместо предикатной буквы Р формулы ~~хЯ(х, г), причем параметр 'г играет роль аргумента при подстановке. В общем случае подстав- ляемые формулы могут содержать и другие параметры, ос- тающиеся фиксированными при подстановке, и следует обычным образом избегать коллизии переменных.
Дадим точное индуктивное определение подстановки вместо преди'- катной буквы. Пусть А — формула и хь ..., хе — список различных пе- ременных сортов пь ..., па соответственно. Формальным пця- дикатом вида (яь ..., п~) назовем выражение х, ... хаА. 5 зах. Ф7В зз Переменные х; .назовем аргументными переменными фо мального предиката и будем рассматривать как свлзанн переменные, Здесь не исключается и случай й=О, т.
е. вс кая формула сама по себе является формальным предик ' том вида () без аргументных мест. Пусть  — формула, У=х, ... »»А — формальный пред ' кат вида (пь ..., пх), Р— цредикатная буква вида (пь ... ..., пэ). Индукцией по логической сложности ((В) определи формулу В(Р~!У) — результат правильной подстановки (за мены) Р в формуле В на формальный предикат У. А. Пусть В' есть атомарная формула Я(гь ...., г ). Есл Я отлична от Р, то В(Р1~0)=В.
Если же Я есть Р, т В(Р!1У) А(хь ..., ха~!гь ..., г ). В этЬм случае, конечно, й=гп. Б. В есть (САЬ), тогда В(П(У) =С(Щ(У)ЛП(Пи). В есть 1С, тогда В(РПУ)= 1 (С(Р!!0)).. В. В имеет вид Я»С. Здесь следует рассмотреть два слу- чая, 1) У не содержит свободно г, или Р не входит фактичес- ки в С. Напомним, что все вхождения х„..., хэ в У счита- ются связанными. В рассматриваемом случае В(ЩС) =Ог(С(пи)). 2) У содержит свободно г, и Р входит фактически в С. Выберем тогда новую переменную и и положим . В (Р!! У) = Яи ( (С;) (Р й У) ) . В соответствии с этим определением нетрудно увидеть, что формула Я(х)~/ 'рг )у хЯ(х, г) представима как ре- зультат правильной подстановки (Я(х)~/)Угр(г))(Р~(г ~)ухЯ(», г)). Теперь мы можем продолжить описание логических за- конов 23.
)='у»1 ...хэ(А=В) ~. С(Р~1», ...хэА)— СРх ...хВ. ( Й 1 ь ) 24. Если А В, то С(Р~~», ...хеА) С(Р!~х~ ...хэВ). Именно это правило и решает задачу, поставленную в начале п. 5. Логические законы можно использовать, заме-' няя эквивалентные подформулы внутри формулы. Формулу вида С(Рз»1 ...хэА) часто называют подстановочным примером, илн частным случаем формулы С. Мы видим, в частности, что если С есть логический закон, то.
всякий подстановочный пример формулы С также является логическим законом. й а. пРиложения теОРии лОГикО. МАТЕМАТИЧЕСКИХ ЯЗЫКОВ, ПРЕДВАРЕННАЯ ФОРМА. ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ, НОРМАЛЬНАЯ ФОРМА. ЯЗЫК ЛОГИКИ ВЫСКАЗЫВАНИЙ И ЛОГИКИ ПРЕДИКАТОВ 1.
Предваренной (или пренексной) формулой называется формула вида Я~х1 ... Япх 4, где Я; суть кванторы, а формула А (называемая матрикей предваренной формулы) уже кванторов не содержит. Таким образом, в предваренной формуле все кванторы находятся в начале формулы. В частности, мы не.нсключаем и случая п=О, бескванторная формула также считается предварениой. Если А — В и  — предваренная формула,.то В называют предваренной формой формулы А. ' Теорема (о предваренной форме). Для всякой формулы А существует предваренная формула В, А В.
Но лемме п. 7 $2 найдется формула С со свойством чистоты переменных А=С, и, следовательно, А С (см. п. 5, $ 5). Затем, используя одностороннее пронесение кванторов (п. 4 $ 5, законы 7 — 74), приводим С к предваренной форме. При этом мы пользуемся тем, что можно внутри формулы С заменять эквивалентные формулы, . т, е. пользуемся эквивалентностью при замене. Возможность одностороннего вынесения кванторов обеспечивается именно свойством чистоты переменных. 'Например, пусть дана формула Ч НЯР(,р) Ч (Е() НЯР(,р)). Соответствующая формула со свойством чистоты переменных такова: ~х 13цР(х, у) э~иЯ(и) ~ ~3оР(и, о)). Применяя логические законы, получим последовательно 'ух'ру ) Р(х, у):з'р'и )Г'о(Я(и) ~ 1Р(и, о)), Зх 3у 'р'и)7о( '1Р(х, у) ~Я(и) ~ 1Р(и, о))). Обратите внимание на два момента: 1) в матрице результирующей формулы логические связки расположены в том же порядке', что и в первоначальной формуле; 2) кванторы можно выносить в разном порядке (сначала из посылки, а потом из заключения или наобороту; так что вид кванториой приставки зависит от способа получения предваренной формы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
