Кук Д., Бейз Г. - Компьютерная математика, страница 5

Д о к а а а т е л ь с т в о. х«еА П(ВОС) «.х~иА и х«а(ВОС) ° (Такая группировка необходима, так как скобки означают, что объедкяопие следует вычислить перед пересечением.) «хжА и (ха В или хжС)« ~(хеА в ха%В) кли (хиА и хиС)Ф ° «(ля А П В) или (з «вА П С) ~ л ж(А ПВ)0(А ПС), 26 Таким образом, А П(В 0 С) (А П В)0(А П С). Сейчас необходимо дока»ать включение яс в обратную сторону: хсв (А П В) 0 (А П С) ~.

«(х св А П В) или (х св А П С) .:. «(х си А и х «а В) или (х св А и х сн С) « «хсиА и (хжВ или хсвС)-« х си А и х сн В П С ~ х ы А П (В б С) . Следовательно, (А П В) О (А П С) ы А П(В ц С), Поэтому А П(В 0 С) (А П В) 0(А П С). г" В атом частном случае вторая часть докаэательства точно совпадает с первой, и, следовательно, можно за. писать хснА П(В ОС)«.«х«эА и хсиВ ОС и т. д.

Здесь символ «~ ° » («Р ~«. Ч») означает, что Р=. О и О «. Р. Ои может читаться как «тогда и только тогда» (иногда также читают «если и только если») и оэначает эквивалентность двух утверждений Р и (). Однако не всегда так просто обратить аргумент и следствие. В общем случае мы долясны провести докаэательства в обе стороны раадельно. Заметим также, что эквивалентность может быть легко получена (хотя и ие докаэана) иа подходящей диаграммы Венна, однако не всегда можно начертить диаграмму, относительно которой можно быть уверенным, что она настолько отвечает требованиям, насколько необходимо. Поэтому непосредственное доказательство необходимо.

Зто доказательство зависит от внутренних взаимосвяэей между эначевиями «и» и «или» и, следовательно, может быть выбрано для канского случая своим. Далее, когда будут определены некоторые алге. браические структуры, мы покажем, что это не составляет трудностей. Примеры 4.2 — 4.5 также испольэуют прямые докааательства, однако эти доказательства эаписаны в несколько другом виде. Пример 4.2. Относительно данного множества с» дополнение любого множества А(А ск«Т) единственно. Доказательство. Предположим, что существует два множества В и С, каждое из которых удовлетворяет требованиям дополненля Л, т, е. ВПА=СПА И и В0А С0А=В'.

Тогда В В П 3' В й(С 0 А) (В й С) 0 (В й Л) ° =(В й С) 0 И В П С; поэтому хжВ ' л~вВп хжС «.В~ В11С ~ВаВ и ВаС, Однако мы знаем, что Вы В, Поэтому отсюда следует, что ВшС, Аналогично (меняя ролямп В п С) получаем СыВ, откуда В ° С, т. е. В С А', и А' единственно. Х Приведенный выше пример содержит в себе основной математический подход, употребляемый для доказательства единственности,— сначала предполагается, что существуют два таких объекта, а затем доказывается, что они совпадают. В следующем примере мы опять прибегнем к предположениям об «или», чтобы иметь возможность написать выралсепие А 0В 0 С как Л 0(В 0 С) или (Л 0 В)0 С, когда это будет более удобно для требуемых преобразований.

Пример 4.3. Даны множества А, В и С такие, что А 0В0С д* и А, В н С попарно не пересекаются. Тоглз А' В0 С, В' Л 0 С и С' А 0 С. Д о к а а а т е л ь с т в о. А 0 В 0 С А 0 (В 0 С) Ю, А й(В 0 С) (А й В) 0(А () С) И 0 И И, Следовательно, В 0 С удовлетворяет условиям для А', которое единственно. Поэтому Л ' — В 0 С.

Аналогично проводятся доказательства для В' и С', К 28 Пример 4.4. Для произвольных множеств Х и У справедливо соотношение (Хй Г)'-(Хй Г')0(Х'й Г)0(Х й У). Доказательство, Предположим, что мы имеем множества А, В и С иэ примера 4.3 и С Р0Е и РйЕ И, (Диаграмма Ванна на рис.

1.9 может раэбпть 8', как требуется.) Тогда множества Л, В, Р и Е взаимно не пересекающиеся и А0В0Р0Е 8', й Более того, л а Ю Л' В0С, поэтому Е А' В0Р0Е. Сейчас легко показать, что если положить А Хйу, В Хйу; Рвс. 1.Э Р ХйГ и Е * Х' й У', то требуемые условия будут выполнены, и поэтому нужный реэультат немедленно следует иэ предыдущих рассмотрений. л' Пример 4.5. Для любых множеств Х и У верно соотношение (Х й У)' Х'0 У', Докаэательство.

хш(Хй У)' е~хы(Хй Г)'0(Х'й У)0(Х'й У')~=а. ~. х ш (Х й У) ' 0 (Х' й У') 0 (Х' й У) 0 (Х' й У') с-.э. (Один член вдесь продублирован. Это разрешается, так как Л * А 0 А для любого А.) е~ х ш((Х й У ) 0 (Х' й У ) ) 0 ((Х' й У) 0 (Х' й Г ) ) се. ((ХОХ') й Г') 0(Х'й(Г0 У)) хш(юй Г') 0 0(Х'йа') шУ'0Х' х=Х'0Г. Следовательно, (Х й У) Х' 0 У'.

л Реэультат, полученный в примере 4.5, и подобные ему (см, упражнение 4.5) наэывают ваконалси де Мориака, 29 Опи играют важную роль в математической логике. Наиболее пепосродствеппые приложения к вычислениям находятся в области комбинаторпых цепей в логике. Последовательность примеров 4.1 — 4.5 иллюстрирует, как можно развивать математическую теорию путем последовательности доказательств простых теорем и выводить такие важные результаты, как законы де Моргана. Перед тем как перейти к ааключительной части этой главы, попытаемся переписать доказательства задач, разобранных в примерах 4.2 — 4.5, формальным образом, как зто делалось в примере 4.1. В частности, каждый шаг должен быть проверен ссылкой на доказанный результат из предыдущих работ или же непосредственно выведен.

Позднее мы введем необходимую терминологию, которая позволит использовать более краткие обозначения. Дадим сначала два определения. Определение. говорят, что дза множества А и В яеэквиваяснтны, если они не зквивалектпы. Зто свойство равносильно тому, что одно из множеств А~В или В~А непусто.

Определение. Множество всех подмножеств данного множества Х назовем степенью множества Х и будем обозначать через У(А). (Некоторые авторы используют обозначение 2з; причина зтого будет ясна немного позднее, когда мы разберем несколько примеров.) Формально У(Х) = (1' Уы Х). В частности, заметим, что поскольку 8 — Х и Х вЂ” Х, то д~ ы У(Х), Пример 4.6. Пусть А = (1, 2, 3). Тогда У(А) (и, (И, (21, (3), (1, 2), (1, 3), (2, 3), А). Х Завершим зтот параграф упоминанием о двух косвенных методах доказательства. Первый из них — доказательство от противного. Вспомним парадокс Рассела (пример 1А): РиР=~.РФР и РФР~Р~БР, Если обозначить утверждение Р ж Р через Р, то получки Р справедливо ч.Р ложно и Р ложно Р справедливо.

Основой математики является предположение о том, что не может быть утверягдепия, которое является истинпым и ложным одновременно (т. е. логическая система долнзна быть содержательной; мы отвергаем множество Рас- 30 села потому, что его определение несостоятельно в рассматриваемом смысле), и мы используем это положение как основу доказательства от противного. Предположкм, что мы имеем совокупность высказываний Рн Рн ..., Р и хотим доказать (Р, истинно и Рз истинно и... и Р„истинно) ~ Д истинно, или же более просто (Р| н Рз и... п Р„)~ Д.

Коли мы допустим высказывание (Р, и Рзи...и Р. и не ~)), т. е. что Рн ..., Р„истинно, а Ч ложпо, и отсюда сможем вывести некоторое утверждение Р, которое одновременно является и истинным. и ложным, то логическая система, основанная на (Р1 н Рз и... и Р. и не () ), является недопустимой.

Таким образом, доказано, что если имеет место (Р1п Рзи...иР„), то мы можем заключить, что (Р1 иРз и... и Р„) ~ (7, так как предположение не Д приводит к противоречию. Для иллюстрации вышесказанного, рассмотрим пример. Пример 4.7, Докажем, что для произвольных множеств А и В имеет место соотношение А ж В ~е- В' а А'. Д о к а з а т е л ь с т в о.

Допустим, что свойства (т. е. определения) множеств д', О п т. д. выполнены и что А еВ и В'Ф А. (Б терминах описанной выше общей ситуации ч' это  — А'.) Тогда А а В ~ если х е Л, то х е В; (") В' фА' ~ существует некоторый элемент у такой, что уеВ' и уФА . Из (е) следует соотношение уеЛ= уеВ~уеВ' н уеВ уеВ РВ=6 (противоречие), Следовательно, полученное утверждение В' ф Л' ложно, н поэтому В' е А'. Аналогично монсно покааагь, что В'.ю ЕА' ~ Л вЂ” В, н, следовательно, А е В с=~ В' е А'.

Г Этот пример таки'е распростракяетсл и иа второй метод косвеппого доказательства. Пример 4.8. Пусть Р озиачает высказывание «сегодня четверг», а ч — «сегодпя день недели». Тогда (Р «- Г>) оапачает «если сегодня четверг, то зто день недели», а (не Ч ь ие Р) означает «если сегодпя ие день недели, то это пе четверге. Следует убедиться, что эти два высказывания эквивалентны (т. е.

что оии оба одновременно являются либо истинными, либо ложными). Х С этой точки зрения, хотя диаграммы Венка могут использоваться для прояспенпя ситуации, все результаты долины быть выведены из предположений, данных в задаче. Следует помнить, что если какое-либо утверждение истинко, то мы должны быть в состоянии доказать его. Если это действительно очевидно, то мы легко докажем его, если же иет, то, по-видимому, это ие так очевидно, как мы думали, и вполне возмон'но, что это даже неверие.

У п раж некие $4. 1. Доказать, что А П(В П С) =(А П В) П С. 2. Пусть дапы множества А, В и С; С ы В. Доказать, что: а) АПС вЂ” АПВ; б) ЛОС>кАОВ: в) А~В ы А~С; г) С~Л ы В~Л; л) В ~А ы С ~Л 3. Доказать, что если А к> В, то У(Л)>и В>(В). 4. Показать спрзведчпвость равенства А 0(В П С) (А 0 В)П(А 0 С). 5. Доказать, что (Л 0 В)' Л' П В'. (Указание; показать, что (А ОВ)0(Л'ПВ')=Ю и (А ОВ)П П (Л ' П В') = >«>,) б. Доказать эквивалентность следующпх утверждений т. е.

что из кая«лого следует другов: а) АОВ 8';б) А'ыВ;в) А'ПВ' Я>. 7. Какао кз следу>ощих утверждений справедливы: а) Ою л>; б) (я>) и> >в; в) я> ез(я>); г) а >яд'; д) (а) к> Ца))1 Сравните ответы па этот вопрос с ответами к упражпе. ипю >.2,Г>. Существует связь между символами «з и >и однако это ие одно и то же, Как апалогия «портфели« связана с символом ':-3 8. Показать, что для конечного множества А ~2л( 2ао (Указание: выписать множество А (аь ..., а„) и рассмотреть его подмножества.) $5.