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

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

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

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

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

Пусть 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. Выясним, является ли тождеством следующее выражение:

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

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

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

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

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

📽️ Видео

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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