Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 18
Текст из файла (страница 18)
произвольно выбранного) элемента а из универса. Из истинности Я(Ь) для произвольной константы 6 из универса следует, что ЧхЯ(х) истинно. Пусть дано высказывание Лх(ха + 2х — 3 = О), отсюда заключаем, что сушествует значение а (а именно, а = 1) такое, что аз + 2а — 3 = О. Обратно, если для конкретного значения а имеем аз + 2а — 3 = О, можно сделать вывод, что Зх(хз + 2х — 3 = О). Следующие два правила дают возможность установить связь между предикатами с конкретными значениями переменных и предикатами с навешенным квантором существования. Из истинности Зх5(х) следует, что 5(а) истинно для некоторого а из универса.
Из истинности Я(Ь) для некоторого Ь из универса следует, что ЗхЯ(х). Суммируя вышесказанное, получаем такие соотношения: 1) эниверсальная конкретизация Из истинности ЧхР(х) следует истинность Р(а) для произвольного а из универса. 118 ГЛЛВЛ 3. Логика, целые числа и доказательстве 2) Универсальное обобщение Если произвольное а из универса обеспечивает истинность Р(а), делаем вывод, что Чх(Р(х) истинно. 3) Экзиетенциональная конкретизация Из истинности ВхР(х) следует, что сушествует конкретное Ь такое, что Р(Ь) истинно. 4) Экзистенциональное обобщение Из сушествования конкретного с из универса, для которого Р(с) истинно, можно сделать вывод, что ВхР(х).
На основе этих соотношений можно доказать следующие утверждения. ТЕОРЕМА 3.1. Для произвольных предикатов Р(х) и Щх), имеющих одну предметную область, а) Чх(Р(х) А Я(х)) =ЧхР(х) Л ЧхЯ(х); б) Вх(Р(х)Ч Я(х)) эв ВхР(х) Ч БхЯ(х); в) из ЧхР(х) Ч ЧхЯ(х) следует, что Чх(Р(х) Ч Я(х)); г) из Вх(Р(х) д Я(х)) следует, что ВхР(х) д Зх(,)(х).
ДОКАЗАТЕЛЬСТВО. Чтобы доказать Чх(Р(х) д Я(х)) = ЧхР(х) л ЧхЯ(х), сначала предположим, что Чх(Р(х) лЯ(х)), откуда следует, что ЧхР(х) лЧхЯ(х). Из Чх(Р(х) д Я(х)), используя универсальную конкретизацию, заключаем, что для произвольного а имеет место Р(а) д Я(а). Следовательно, согласно правилу специализации (логики высказываний) можно сделать вывод, что для произвольного а имеет место как Р(а), так и Я(о). На основе универсального обобщения делаем вывод, что ЧхР(х) и ЧхЯ(х).
Таким образом, можно заключить, что ЧхР(х) л ЧхЯ(х), в силу правила конъюнкции (логика высказываний). Обратно, предположим, что ЧхР(х) д ЧхЯ(х). На основе правила специализации можно сделать вывод, что ЧхР(х) и ЧхЯ(х). Из правила всеобшей конкретизации следует, что для произвольного а имеют место Р(о) и Ща). Следовательно, используя правило конъюнкции, можно сделать вывод, что Р(и) д Я(а) для произвольного а. На основе универсального обобщения делаем вывод, что Чх(Р(х) д Я(х)). Оставшуюся часть доказательства предоставляем провести читателю.
Если р(х) — утверждение "х — студент", а утверждение 4(х) — "х учится усердно", то утверждение Чх(р(х) — д(х)) может быть интерпретировано как "Все студенты учатся усердно". Точно так же, если р(х) — утверждение "х— слон", а д(х) — утверждение "х предпочитает арахис в шоколаде", то выражение Вх(р(х) г о(х)) может быть сформулировано как "Некоторые слоны предпочитают арахис в шоколаде". Утверждение "Все люди смертны" логически может быть выражено как Чх(р(х) — о(х)), где р(х) — утверждение "х — человек", а д(х) — утверждение "х смертен". Аналогично, утверждение "Некоторые целые числа делятся на 5" может быть записано Вх(р(х) д д(х)), где р(х) — утверждение "х — целое число", а д(х) — утверждение "х делится на 5".
Обычно логические выражения, содержащие Чх, можно превратить в утверждения, содержащие "для РАЗДЕЛ 3. 7. Исчисление предокапюе 119 всех", а логические выражения, содержащие Бх, можно обратить в утверждения, содержащие "для некоторого". В силу такого характера перевода с языка логики на естественные языки и обратно, отрицание утверждения типа "для всех" есть утверждение типа "для некоторого", а отрицание утверждения типа "для некоторого" есть утверждение типа "для всех". Например, отрицание утверждения Все целые числа являются простыми есть утверждение Некоторые целые числа не являются простыми, а отрицание утверждения Некоторые люди любят есть репу есть утверждение Все люди не любят есть репу.
Для неформальной проверки правильности умозаключений, включающих утверждения типа "для всех" и "для некоторого", используются так называемые диаграммы Эйлера, которые состоят из кругов, изображающих множества. Например, утверждению "Все р есть т*' соответствует диаграмма, приведенная на рис. 3.1, где круг, изображающий множество р, содержится в круге, изображающем множество о. Утверждение "Некоторые р есть с" представляется диаграммой на рис.
3.2, где мы видим, что пересечение кругов, изображающих множества р и о, непусто. Для проверки умозаключения необходимо попытаться построить диаграмму Эйлера, в которой посылки истинны, а заключение ложно. Если такое построение осуществимо, то умозаключение неправильно, если же нет, то это доказывает правильность нашего умозаключения. Рис. 3.2 Рис.
3./ ПРИМЕР 3.2. Рассмотрим умозаключение Все студенты колледжа выдающиеся Все выдающиеся люди — ученые се студенты колледжа — ученые 120 ГЛя8Л 3. Логика, целые числа и доказательства В соответствии с посылками круг, изображающий студентов колледжа (СК), должен быть внутри круга, изображающего выдающихся людей (ВЛ), который, в свою очередь, должен быть внутри круга (У), изображающего ученых. Следовательно, круг студентов колледжа должен находиться внутри круга ученых, и умозаключение является правильным.
П ПРИМЕР 3.3. Рассмотрим умозаключение Все поэты счастливы Некоторые поэты ленивы екоторые ленивые люди счастливы В соответствии с посылками круг, изображающий поэтов (П), должен быть внутри круга, изображающего счастливых людей (СЛ), а пересечение поэтов и ленивых людей (ЛЛ) должно быть непусто. Но это пересечение содержится в круге, изображающем поэтов, так что пересечение ленивых и счастливых людей непусто.
Умозаключение правильно. П ПРИМЕР 3.4. Рассмотрим умозаключение Некоторые поэты неудачники Некоторые атлеты неудачники екоторые поэты являются атлетами Соответствующая диаграмма Эйлера изображена на рис. 3.3. Рис. З.З Мы видим, что возможно построить такую диаграмму Эйлера, в которой пересечение кругов поэтов (П) и неудачников (Н) непусто и пересечение кругов атлетов (А) и неудачников непусто, так что посылки истинны, но при этом круги поэтов и атлетов не пересекаются, так что следствие не является верным.
Следовательно, умозаключение не является правильным. П ПРИМЕР 3.5. Рассмотрим умозаключение Все гении нелогичны Некоторые политики нелогичны екоторые политики гении На рисунке слева круг для гениев (Г) содержится внутри множества нелогичных людей (НЛ), а пересечение круга политиков (П) и круга нелогичных людей непусто, но круги политиков и гениев не пересекаются. Следовательно, посылки истинны, но заключение ложно. Поэтому умозаключение не является правильным. П ° УПРАЖНЕНИЯ 1. Заданы предикаты х~+у~ > г у = (х — 4)Дх+ 4); (х — Ц < г; у — и а нравится Ь больше, чем с.
Р(х, у, з): Я(х, у): Л(х, т): о(п, у): Т(а, Ь, с): б) Я(8,2); г) о(4, 24); х +у =з еслиу =х, тох=у; 2 2 ((х) ) = (х); а<х~<Ь; а играет в теннис лучше, чем Ь. Р(х, у, а): Фх, у): Л(х): о'(а, Ь, х): Т(а, Ь): Запишите следующие высказывания: а) Р(3, 4, 5); б) Я( — 2,2); в) В(3.1416); г) о(0,4, — 3); д) Т(Джон, Фред). 3. Используя Р, Я, В, Я и Т из упражнения 1, запишите высказывания: а) (Зх)(Зу)Р(х,у,25); б) (Бх)Я(х,7); в) (Чг) (Зх) В(х, г); г) (Зп)(чу)о(п, у); д) (Чс)Т(Джон, Сью, с). 4. Используя Р, Я, В, о и Т из упражнения 1, запишите высказывания: а) (Чх)(Чу)(Зз)Р(х,у, з); б) (Чх)(Чу)Я(х, у); в) (чх) 11(х); г) (Чх)(За)(ЗЬ)о(а, Ь, х); д) (Ча)Т(а,'7ед).
Запишите следующие высказывания: а) Р(3,4,5); в) В(3, 7); д) Т(Джон, Сью, Мэри). 2. Заданы предикаты РАЗДЕЛ 3.1. Исчисление лрединетое 121 тгг ГПЯВА 3. Логика, целые числа и доказательства Запишите приведенные ниже утверждения в символической форме, введя предикаты. В случае необходимости укажите предметную область.
а) На каждой улице будет праздник. б) Некоторые машины умнее людей. в) Любой играет в теннис лучше Фрэда. г) Для каждого действия существует равное и противоположно направленное противодействие. д) Каждый игрок в гольф, в конце концов, будет обыгран более сильным игроком. Запишите приведенные ниже утверждения в символической форме, введя предикаты. В случае необходимости укажите предметную область.
а) Некоторые композиторы пишут симфонии лучше, чем другие. б) Для каждого п существует три целых числа таких, что п-я степень одного из них равна сумме п-ых степеней двух других. в) Существуют лошади, которые могут обогнать некоторых людей. г) Он лучший атлет в мире. д) Не существует совершенных героев. 7.
Ранее было показано, что если Я(х, у, г): хз + уз > гз, то утверждение ЧхЧуЧЩ(х, у, г) ложно. Если универс — множество положительных целых чисел, то что можно сказать об истинности а) ЧхЧухгЯ(х, у, г)? б) ЧхЗуЭЩ(х, у, г)? в) БхЧуЗгЯ(х, у, г)? г) ЯхЭуэгЯ(х, у, г)? д) 3хЗуЧЯ(х, и, з)? 8. Пусть известно, что Чп(п нечетно — (Зй)(п = 2й + 1)). а) Какое из этих утверждений истинно? 7 нечетно — (Зй)(7 = 2й + 1), 6 нечетно — (Вй)(6 = 2Й + 1). б) Какое из этих утверждений истинно и почему? (Бй)(7 = 2й + 1), (Бк)(6 = 2й+ 1). 9. Докажите, что из Чх Р(х) Ч Чх Я(х) следует, что Чх (Р(х)Ч Я(х)). 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
