Доказательство теоретико множественных тождеств и решение теоретико множественных уравнений

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

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

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

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

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

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

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

(p ÙØq)Ù(pÙØr) которая легко проверяется.

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

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

b) В обозначениях предыдущего примера получим: ((pÙq

(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.
Докажите следующие тождества:

Видео:Множества и операции над нимиСкачать

Электронная библиотека

Пусть U – произвольное множество, «универсум». Мы будем рассматривать теоретико-множественные выражения, которые получаются из символов с помощью операций над множествами, например:

2) если H – теоретико-множественное выражение, то – теоретико-множест­венное выражение;

Наша цель – научиться решать уравнения

Для всякого теоретико-множественного выражения H(X, A₁, …, A_n) существуют такие теоретико-множественные выражения

что для любого XÍU следующие условия равносильны:

В условиях предыдущего предложения, уравнение H(X, A₁, …, A_n)= Æ будет иметь решения тогда и только тогда, когда будут выполнены соотношения:

Метод решения уравнения

Здесь A₁, …, A_n и B₁, …, B_m – некоторые заданные множества. Обозначим символом 0 пустое множество.

Это уравнение сначала приводят к уравнению

Потом для полученного уравнения находим формулы для R, S, T из предыдущего предложения. И, наконец, применим предыдущее следствие. Разберем этот метод решение на следующем примере.

Рассмотрим, например, уравнение:

Оно равносильно уравнению вида:

Следующим шагом решения будет преобразование левой части к объединению пересечений множеств. Это достигается с помощью формул:

После применения этих формул получим:

А после применения формул де Моргана приходим к уравнению:

С помощью закона дистрибутивности получаем уравнение:

то это уравнение примет вид:

Последнее равенство выполняется тогда и только тогда, когда X удовлетворяет системе уравнений:

Первое уравнение равносильно включению , а второе – . Отсюда вытекает следующий ответ:

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Видео:Операции над множествамиСкачать

Метод характеристических функций в теории множеств

Доказательство сложных теоретико-множественных тождеств методом двух включений часто бывает довольно громоздким, и при построении доказательства ход рассуждений не всегда очевиден. Одним из методов, не требующих «угадывания» пути доказательства, является метод характеристических функций.

Характеристическая функция множества есть функция, отображающая универсальное множество в двухэлементное множество

Из определения характеристической функции множества вытекает справедливость тождества

Выразим характеристическую функцию пересечения множеств и через характеристические функции и этих множеств. Из определения пересечения следует, что искомая характеристическая функция должна принимать значение 1 для тех элементов , которые принадлежат множествам и одновременно, и значение 0 в противном случае. Легко видеть, что функция

удовлетворяет этому требованию.

Можно предположить, что характеристическая функция объединения множеств и будет равна сумме характеристических функций множеств. Однако так ее определить нельзя, поскольку для элементов такая сумма будет иметь значение 2. Введем «поправку» и в результате получим искомую формулу:

Непосредственно из определения — дополнения множества — следует, что

Для разности характеристическая функция имеет вид

а для симметрической разности —

Отметим, что последнюю формулу можно получить, опираясь на свойство 19 и тождество (1.10), а также на характеристические функции для пересечения, объединения и разности:

С учетом равенства (1.10) полученную формулу можно записать в виде

Метод характеристических функций доказательства справедливости теоретико-множественного тождества заключается в выражении характеристических функций обеих его частей через характеристические функции входящих в него множеств. Тождество верно тогда и только тогда, когда характеристические функции левой и правой частей совпадают.

Пример 1.22. Используя метод характеристических функций, выясним, справедливо ли тождество

С одной стороны,

С другой стороны,

Характеристические функции левой и правой частей тождества совпадают. Следовательно, тождество верно.

Пример 1.23. Выясним, является ли тождеством следующее выражение:

С одной стороны,

С другой стороны,

Легко видеть, что получены разные характеристические функции. Например,при и имеем

Таким образом, доказано, что .

Отметим, что метод характеристических функций не является универсальным. Так, его нельзя использовать при доказательстве тождеств, содержащих декартово произведение множеств, в частности, тождеств для соответствий (бинарных отношений).

📹 Видео

3.10 Пример - доказательство равенства двух множествСкачать

Доказать равенства при помощи диаграмм Эйлера-Венна. Действия над множествами.Скачать

практика доказательство равенства множествСкачать

Доказательство тождеств в теории множеств. Алгебраический методСкачать

Метод включений для доказательства тождествСкачать

Доказать равенства при помощи диаграмм ВеннаСкачать

Множества. Доказательство равенстваСкачать

Множества. Операции над множествами. 10 класс алгебраСкачать

Конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание. На примерах из жизни. Логика.Скачать

9 класс, 2 урок, Множества и операции над нимиСкачать

Математика без Ху!ни ! ;) Математическая индукция. Метод доказательства формул.Скачать

Пересечение множеств. Объединение множеств. 5 класс.Скачать

Круги Эйлера. Логическая задача на множества. Иностранные языкиСкачать

Информатика. Алгебра логики: Теория множеств. Центр онлайн-обучения «Фоксфорд»Скачать

Подмножество. Операции над множествами (пересечение, объединение множеств) – 8 класс алгебраСкачать

Преобразование логических выражений / Упрощение выражений (практика) [Алгебра логики] #6Скачать