Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Доказательства теоретико-множественных тождеств.

Читайте также:
  1. Доказательства из Сунны.
  2. ДОКАЗАТЕЛЬСТВА МОЕЙ ТЕОРИИ
  3. Доказательства ортодоксальной церкви
  4. Доказательства присутствия на Земле неземных цивилизаций
  5. Доказательства существования Бога
  6. ДОКАЗАТЕЛЬСТВА СУЩЕСТВОВАНИЯ ПАРОВОДЯНОГО КУПОЛА В ПРОШЛОМ
  7. Доказательства того, что обитатели Рая займут в нем разные ступени
  8. Доказательства эволюции. Микроэволюция. Макроэволюция
  9. Доктор Бреггин добавляет, что существуют доказательства того, что риталин может стать причиной необратимых нарушений и дисфункций в мозге ребенка.


Доказательства тождеств алгебры множеств можно проводить двумя путями.

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

b) Сводят всё к формуле математической логики и доказывают, что она есть тавтология.

Продемонстрируем оба способа на примерах.

Доказать тождество: А\(ВÈС)=(А\В)Ç(А\С)

a) Пусть некий элемент хÎА\(ВÈС). Тогда хÎА и хÏ(ВÈС). Значит он не принадлежит ни В, ни С. А тогда хÎА\В и хÎА\С, а значит, и их пересечению, т.е., всей правой части.
Итак, левая часть содержится в правой. Пусть теперь хÎ(А\В) Ç (А\С). Это значит, что хÎА и хÏВ, хÏС. Значит, хÎА и хÏ(ВÈС). А значит, он содержится в левой части.

b) Введём предикаты р(х): (хÎА) ; q(х): (хÎB; r(х): (хÎC). Тогда утверждение сводится к доказательству логической эквивалентности pÙØ(qÚr)~(p ÙØq)Ù(pÙØr) которая легко проверяется.

Доказать тождество: АÇВ=АÛАÌВ

a) (Þ) Опять, допустим хÎА. Так как АÇВ=А, то хÎАÇВ; Þ хÎВ. Итак, (хÎА)Þ(хÎВ). Значит, по определению, АÌВ. (Ü) Поскольку всегда АÇВÌА, то надо лишь доказать, что АÌАÇВ. Пусть хÎА. Так как АÌВ ,то хÎВ. Следовательно, хÎАÇВ.

b) В обозначениях предыдущего примера получим: ((pÙq~p))~(pÞq). Надо доказать, что это – тавтология. Используем упражнение 7 пункт i) из части 1. Преобразуем сначала внутреннюю эквивалентность и импликацию: ((pÙqÙp)Ú(ù(pÙq) Ùùp))~(ùpÚq). В левой части от знака эквивалентности делаем преобразования:
(pÙq)Ú((ùpÚùq)Ùùp); (дистрибутивность, идемпотентность, коммутативность)
pÙqÚ(ùpÙùqÚùp); (поглощение) pÙqÚùp;
Теперь снова применяем замену эквивалентности:
[(pÙqÚùp)Ù(ùpÚq)]Ú[ù (pÙqÚùp)Ùù(ùpÚq)].
По дистрибутивности в каждой из квадратных скобок получим:
[pÙqÙùpÚpÙqÙq Ú ùpÙùpÚùpÙq] Ú [(ùpÚùq)ÙpÙ(p Ùùq];
[FÚpÙqÚùpÚùpÙq]Ú[(FÚùqÙp) Ù(p Ùùq];
[pÙqÚùp] Ú[p Ùùq]; Итак, получили: pÙqÚ p ÙùqÚùp. Это (выносим р за скобку) эквивалентно
рÙ( qÚùq)ÚùpÛ рÙТÚùp ÛрÚùp Û Т.



c) (Þ): АÇВÌВ; А=АÇВÞАÌВ. (Ü): АÌА и АÌВÞАÌ(АÇВ), а так как всегда АÇВÌА, то АÇВ=А



Упражнение 7.
Докажите следующие тождества:


a) АÈВ=ВÛАÌВ

b) А\(ВÇС)= (А\В)È(А\С)

c) А\(А\В)=АÇВ

d) А\В=А\(АÇВ)

e) АÈВ=АÈ(В\А)

f) (АÇВ)ÌСÛАÌСÈВс

g) АÌ(ВÈС)ÛАÇВсÌС

h) (А\В)ÈВ=АÛВÌА


i) (АÇВ)ÈС=АÇ(ВÈС)ÛСÌА

j) АÈВ=АÇВÛА=В

k) АD(ВDС)=(АDВ)DС

l) АÇ(ВDС)=(АÇВ)D(АÇС)

m) АD(АDВ)=В

n) А\В=АD(АÇВ)


 


Дата добавления: 2015-09-14; просмотров: 27; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Диаграммы Венна. Формула включений-исключений. | Упражнение 8.
lektsii.com - Лекции.Ком - 2014-2020 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты