Игошин Математическая логика и теория алгоритмов (1019110), страница 42
Текст из файла (страница 42)
Далее, тождественная истинность предикатов А(х) и В(х) равносильна, ввиду определения 20.1, истинности высказываний (вхНА(х)) и (~хНВ(х)) соответственно, что равносильно истинности их конъюнкции (~ухНА(х)) а (чхНВ(х)). Итак, левая и правая части эквивалентности (1) одновременно истинны и одновременно ложны, что дает истинность всего высказывания (1) и тождественную истинность доказываемой формулы. Тождественную истинность формул б) и в) предлагается доказать в качестве упражнения.
171 г) В этой формуле Д вЂ” нульместная предикатная переменная. Поэтому полставим в ланную формулу вместо Р(х) конкретный одноместный предикат А(х), определенный на некотором множестве М, а вместо Ц вЂ” конкретное высказывание В. Формула превратится в высказывание (ЗхНА(х) л В) +-» (ЗхНА(х)) л В. (2) Докажем его истинность. Действительно, на основании определения 20.3 высказывание (ЗхНА(х) л В) истинно тогда и только тогда, когда предикат А(х) л В выполним. Последнее возможно, если и только если предикаты А(х) и В выполнимы. (Напомним, что в конце предыдущего параграфа было условлено под выполнимостью нульместного предиката (высказывания) понимать его истинность.) Далее, выполнимость предиката А(х) и истинность высказывания В равносильны истинности высказываний (ЗхНА(х)) и В, а значит, и истинности их конъюнкции (ЗхНА(х)) л В. Следовательно, высказывание (2) истинно для лю- бык А(х) и В, а поэтому рассматриваемая формула — тавтология.
П Полезно проанализировать и сопоставить между собой тавтологии, связанные с пронесением кванторов через различные логические операции, представленные в теоремах 21.11 и 21.! 2. Особая важность этих тавтологий будет обнаружена в 5 22, где рассматриваются равносильные преобразования формул логики предикатов. Здесь же мы имеем следующее. Квантор общности безоговорочно проносится через конъюнкцию, а также выносится из обоих членов конъюнкции (эта процедура важна для будущих равносильных преобразований формул), а квантор существования— через дизъюнкцию (теорема 21.11, а, б). Проблемы начинаются при столкновении квантора общности с дизъюнкцией и квантора существования с конъюнкцией. Здесь общезначимыми являются формулы не с эквивалентностями, а с импликацией (см. Задачник, М 943, в, г): ~ (ЗхНР(х) л Д(х)) — » ((ЗхНР(х)) л (ЗхНД(х))); (3) ~ ((ЧхНР(х)) «(ЧхНД(х))) -+ ('сГхНР(х) «Д(х)). (4) Оставив читателю проведение доказательств общезначимости приведенных формул, укажем примеры предикатов, которые показывают необщезначимость формул, являющихся обратными импликациями по отношению к данным.
Для формулы (3) такими предикатами могут служить, например, следующие предикаты, заданные над множеством всех вещественных чисел Рс «х < 1» и «х > 2». Они посылку обратной импликации превращают в истинное высказывание (ЗхНх < 1) л (ЗхНх > 2), а заключение — в ложное высказывание (ЗхНх < 1 л х > 2). Для формулы (4) подойдут предикаты, также заданные над А: «х < О» и «х > О», превращающие посылку 172 ('Фх)(А(х) -+ В(у)) +-» ((Лх)(А(х)) — » В(у)) опровержим, т.е.
обращается в ложное высказывание при подста- новке вместо предметной переменной у некоторого конкретного предмета Ь е М,: Х[(йх)(А(х) -+ В(Ь)) <-» ((Лх)(А(х)) -» В(Ь))] = О. Эквивалентность ложна, если ее члены принимают разные значения истинности, т.е. здесь могут представиться две возможности: первая Х[(Чх)(А(х) -+ В(Ь))] = 1; Х[(Лх)(А(х)) -+ В(Ь)] = 0 (1) (2) и вторая Х[(Ъх)(А(х) — » В(Ь))] = 0; Ц(Зх)(А(х)) — » В(Ь)] = 1. (3) (4) Рассмотрим первую возможность. Из формулы пению !.7 импликации, имеем Х[(Зх)(А(х))] = 1; 1[В(Ь)] = О. (2), по опреде- (5) (6) !73 обратной импликации в истинное высказывание (ох)(х < 0 ы х > 0), а следствие — в ложное высказывание ('Фх)(х < 0) ы ('Фх)(х > 0).
Отметим, что тем не менее равносильное пронесение квантора общности через дизъюнкцию и квантора существования через коньюнкцию возможно. Это тот случай, когда один из членов дизъюнкции или конъюнкции не зависит от той предметной переменной, квантор по которой проносится (см. теорему 21.11, в, г). Теорема 21.12 (законы пронесения кванторов через импликацию). Следующие 4ормулы логики предикатов являются тавтологиями: а) ('с~х)(Р(х) -+ Д) +-» ((Лх)(Р(х)) -+ О); б) (Зх)(Р(х) — » 0) +-» (('Фх)(Р(х)) -+ Д); в) (»Ух)(0 -» Р(х)) с-» (0 — » (~Ух)(Р(х))); г) (Зх)(0 -+ Р(х)) с-» Я -+ (Лх)(Р(х))).
До казател ьств о. Отметим, что предикатная переменная (г в этих формулах может быть не только нульместной, но и любой п-местной, важно лишь, чтобы в нее не входила предметная переменная х. Итак, пусть 0 есть Д(уп ..., у„). Будем считать для краткости, что 0 есть одноместная предикатная переменная 0(у). Тогда: а) предположим, что данная формула не является тавтологией. В этом случае существуют такие конкретные предикаты А(х) и В(у), определенные на множествах М и М, соответственно, что предикат (от у) и, во-вторых, когда Х[(ЗхНВ(Ь) — » А(х))] = 0; (3) 1[В(Ь) -+ (ЛхНА(х))) = 1.
(4) Рассмотрим первый случай. Из соотношения (2), по определению 1.7 импликации, заключаем: ЦВ(Ь)) = 1; Ц(ЛхНА(х))] = О. (5) (6) Далее, из формулы (5) и по определению 20.3 квантора существования заключаем, что предикат А(х) выполним, т.е. ЦА(а)] = 1 (7) для некоторого а е М. Вернемся к соотношению (1). По определению 20.1 квантора общности предикат А(х) — » В(Ь) тождественно истинен. В частности, если вместо предметной переменной х подставить а е М, то получим истинное высказывание 1[А(а) -+ — » В(Ь)] = 1. Но, учитывая (6) и (7), получаем )4А(а) — » В(Ь)] = = ),[А(а)] -» ЦВ(Ь)] = 1 — » 0 = О. Противоречие.
Рассмотрим вторую возможность, выраженную в соотношениях (3), (4). Из формулы (3), на основании определения 20.1 квантора общности, следует, что предикат А(х) -» В(Ь) опровержим, т. е. 1[А(а) — » В(Ь)] = 0 для некоторого а е М. Тогда по определению импликации 1.7 получим ЦА(а)) = 1, ЦВ(Ь)] = О. (8) Учитывая второе из соотношений (8), из соотношения (4) заключаем, что Х[(ЗхНА(х))) = О. Последнее означает тождественную ложность предиката А(х) (см. определение 20.3). В частности, для предмета а е М имеем ЦА(а)) = О, что противоречит первому из соотношений (8).
Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данная формула — тавтология. г) Предположим, что данная формула не является тавтологией. Тогда существуют такие конкретные предикаты А(х) и В(у), определенные на множествах Ми М, соответственно, что предикат (от у) (ЗхНВ(у) -+ А(х)) <-» (В(у) — » (ЛхНА(х))) опровержим, т.е.
обращается в ложное высказывание при подстановке вместо предметной переменной у некоторого конкретного предмета Ь из М,: Ц(3хНВ(Ь) — » А(х)) +-» (В(Ь) -+ (ЛхНА(х)))] = О. Эквивалентность ложна в двух случаях. Во-первых, когда Ц(ЗхНВ(Ь) — » А(х))] = 1; 1[В(Ь) -» (ЛхНА(х))) = О, 174 Соотношение (6) свидетельствует о том, что предикат А(х) тождественно ложен (определение 20.3).
Далее, соотношение (1) показывает„на основании того же определения 20.3, что преликат В(Ь) — > А(х) выполним. Учитывая соотношение (5), получаем: существует такой элемент а в М, что )4А(а)) = 1. Последнее противоречит доказанной выше тождественной ложности предиката А(х). Получить противоречие во втором случае, выраженном в соотношениях (3), (4), предлагается самостоятельно.
Таким образом, рассматриваемая формула — тавтология. Докажите тождественную истинность двух оставшихся формул. П Проанализируем теперь ситуацию, связанную с пронесением кванторов через импликацию, а также с их вынесением за знак импликации. В случаях, когда один из членов импликации (посылка или заключение) не зависит от той предметной переменной, по которой проносится квантор, равносильность также возможна. Но ситуация здесь несколько отличается от той, которая имеет место в случаях конъюнкции и дизъюнкции. Если от предметной переменной, стоящей под знаком квантора, не зависит посылка импликации, то соответствуюший квантор без изменения проносится к заключению импликации (теорема 21.12, в).
Если же от предметной переменной, стоящей под знаком квантора, не зависит заключение импликации, то соответствующий квантор при пронесении его к посылке импликации переворачивается, т.е. меняется на противоположный: квантор обшности — на квантор существования, а квантор существования — на квантор общности (теорема 21.12, а, б).
В ситуации с импликацией имеет место одна интересная тавтология: если оба члена импликации зависят от переменной, стоящей под знаком квантора, то через импликацию можно равносильным образом пронести квантор существования, но при постановке его перед посылкой он поменяется на квантор общности (см.
Задачник, М 9.45, з): ~ (Зх)(Р(х) -+ Д(х)) с-» (('Фх)(Р(х)) -» (Лх)(Д(х))). В то же время, если мы рассмотрим аналогичную формулу для квантора общности: (чх)(Р(х) -+ Д(х))»» ((Зх)(Р(х)) — > (~х)(Д(х))), то она уже не будет тавтологией. Тавтологией будет лишь импликация: ~ ((Зх)(Р(х)) -+ ('Фх)(Д(х))) -+ ('с~х)(Р(х) -» Д(х)). Докажите это самостоятельно.
То, что обратная импликация не будет тавтологией, подтверждает пример двух предикатов Р(х): »х делится на 4» и Д(х): «х четно», заданных над множеством натуРальных чисел (см. Задачник, Хю 9.45, л). Отметим далее, что, используя импликацию, квантор общности можно следующими двумя способами пронести через импли- 175 кацию предикатов, каждый из которых зависит от переменной, стоящей под знаком квантора (см. Задачник, М 9.45, д, е): ('ФхНР(х) — > Ц(х)) -+ (('ФхНР(х)) -+ ('ФхНО(х))); (»хНР(х) -+ Ц(х)) — э ((ЗхНР(х)) — э (ЗхНЩх))). Проверьте, что формулы действительно являются тавтологиями, а обратные импликации таковыми не являются. В то же время аналогичная конструкция с квантором существования (ЗхНР(х) -+ Ц(х)) -+ ((ЗхНР(х)) -+ (ЗхН(г(х))) уже не будет тавтологией (см.
Задачник, Ж 9.45, ж). Пример: Р(х): «х— четно», (2(х): «х < 1», х в Х Не будет тавтологией и обратная импликация. Пример: Р(х): «х> 2», Д(х): «х < 1», ха Я. Теорема 21.13 (законы удаления квантора общности и введения квантора существования). Следующие формулы логики лредикатов являются тавтологиями: а) (ч'хНР(х)) -+ Р(у)' б) Р(у) -+ (ЗхНР(х)).
Доказательство. Проверим, что формула а) тождественно истинна (соответствующую проверку для формулы б) выполнить самостоятельно). Предположим, что формула а) не тождественно истинна. Эго значит: существует такой предикат А(х), определенный на некотором множестве М, что предикат (от у) (»хНА(х)) -э -+ А(у) опровержим, т.е.
превращается в ложное высказывание при подстановке вместо у некоторого а е М: Х[(1гхНА(х)) -+ А(а)[ = О. Последнее означает, что 2,[('сгхНА(х))1 = 1; (1) 2,[А(а)[ = О. (2) Из соотношения (1) заключаем, что предикат А(х) тождественно истинный. Но это противоречит соотношению (2). Следовательно, сделанное предположение неверно, и данная формула— тавтология. П Теорема 21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
