Докажите тождество двумя способами аналитически
Очень часто в задачах по дискретной математике, а именно в теории множеств, требуется доказать равенство множеств. Напомним, что равенство множеств $M=N$ означает выполнение взаимного включения, то есть $M\subseteq N$ и $N\subseteq M$. Следовательно, для доказательства равенства $M=N$ множеств $M,\ N$ нужно показать выполнение этих включений. Делать это можно различными способами:
- по определению теоретико-множественных операций;
- с помощью законов алгебры множеств;
- построением диаграмм Эйлера-Венна;
- построением таблиц принадлежности;
- используя индикаторные функции.
Продемонстрируем каждый из этих способов на конкретном примере.
Доказать равенство множеств:
$$\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$$
1. Равенство двух множеств $M=N$ эквивалентно двум включениям $M\subseteq N,\ N\subseteq M$.
Докажем, что $\left(A\cap B\right)\backslash C\subseteq \left(A\backslash C\right)\cap \left(B\backslash C\right)$. Пусть $x\in \left(A\cap B\right)\backslash C$, тогда по определению разности множеств $x\in \left(A\cap B\right)$ и $x\notin C$. По определению пересечения множеств $x\in \left(A\cap B\right)$ тогда и только тогда, когда $x\in A$ и $x\in B$. Так как $x\in A$ и $x\notin C$, то $x\in A\backslash C$. Так как $x\in B$ и $x\notin C$, то $x\in B\backslash C$. По определению пересечения получаем, что $x\in \left(A\backslash C\right)\cap \left(B\backslash C\right)$. Что доказывает то, что $\left(A\cap B\right)\backslash C\subseteq \left(A\backslash C\right)\cap \left(B\backslash C\right)$.
Докажем, что $\left(A\backslash C\right)\cap \left(B\backslash C\right)\subseteq \left(A\cap B\right)\backslash C$. Пусть $x\in \left(A\backslash C\right)\cap \left(B\backslash C\right)$, тогда по определению пересечения множеств $x\in \left(A\backslash C\right)$ и $x\in \left(B\backslash C\right)$. По определению разности множеств $x\in A$, $x\notin C$ и $x\in B,\ x\notin C$. По определению пересечения получаем, что $x\in \left(A\cap B\right)\ и\ x\notin C$, то есть $x\in \left(A\cap B\right)\backslash C$. Что доказывает то, что $\left(A\backslash C\right)\cap \left(B\backslash C\right)\subseteq \left(A\cap B\right)\backslash C$. Из доказанных включений следует, что $A\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$.
2. Докажем справедливость соотношения $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$, используя основные законы алгебры множеств.
Операцию разность $X\backslash Y$ произвольных множеств $X,\ Y$ можно записать, как $X\backslash Y=X\cap \overline
3. Видим, что диаграммы множеств $\left(A\cap B\right)\backslash C$ и $\left(A\backslash C\right)\cap \left(B\backslash C\right)$ полностью совпадают, значит, равенство $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$ верно.
4. Построим таблицу принадлежности для левой и правой частей данного равенства $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$.
\begin
Видим, что $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)=\left(00000010\right)$.
5. Докажем справедливость соотношения $\left(A\cap B\right)\backslash C=\left(A\backslash C\right)\cap \left(B\backslash C\right)$ с помощью индикаторных функций. Индикаторная функция для левой части соотношения:
$$\ <\chi >_<\left(A\cap B\right)\backslash C>\left(x\right)=<\chi >_
Источник
Дискретная математика 03
I. Дискретные множества
Докажите тождества двумя способами:
А) используя определения равенства множеств и операций над множествами;
Б) с помощью алгебры логики.
А) 
Б) 
. Преобразуем левую часть по формулам алгебры логики:
, что и требовалось доказать.
II. Функции алгебры логики. Многочлены Жегалкина
Для заданной булевой функции трех переменных:
А) Постройте таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ,
Б) Найдите двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная булева функция линейной,
В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.
А) Составим таблицу истинности:
Двоичная форма функции: 01010011.
СДНФ: 
.
СКНФ: 
.
Б) Преобразуем данную функцию к многочлену Жегалкина:
Функция линейной не является.
Построим полином Жегалкина методом неопределенных коэффициентов. Общий вид полинома Жегалкина:
Функция примет вид:
.
Итак, 
.
Оба метода дали один и тот же результат.
В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.
I. Дискретные множества
Докажите тождества двумя способами:
А) используя определения равенства множеств и операций над множествами;
Б) с помощью алгебры логики.
А) 
Б) 
. Преобразуем левую часть по формулам алгебры логики:
, что и требовалось доказать.
II. Функции алгебры логики. Многочлены Жегалкина
Для заданной булевой функции трех переменных:
А) Постройте таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ,
Б) Найдите двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная булева функция линейной,
В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.
А) Составим таблицу истинности:
Двоичная форма функции: 10101100.
СДНФ: 
.
СКНФ: 
.
Б) Преобразуем данную функцию к многочлену Жегалкина:
Функция линейной не является.
Построим полином Жегалкина методом неопределенных коэффициентов. Общий вид полинома Жегалкина:
Функция примет вид:
.
Итак, 
.
Оба метода дали один и тот же результат.
В) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ.
Источник
Тождество. Тождественные преобразования. Примеры.
Тождества в основном применяются для решения линейных уравнений.
Тождеством называется равенство, которое верно при всех значениях переменных.
Или другими словами, тождество — это равенство, которое выполняется на всём множестве значений переменных, входящих в него, например:
В этих выражениях при всех значениях a и b равенство верное.
2 выражения с равными значениями при всех значениях переменных являются тождественно равными.
Равенство x+2=5 может существовать не при всех значениях x, а лишь при x=3. Это равенство не будет тождеством, это будет уравнением. Кроме того, тождеством будет равенство, которое не содержит переменные, например 25 2 =625.
Тождественное равенство обозначают символом «≡» (тройное равенство).
Примеры тождеств.
— Тождество Эйлера (кватернионы);
— Тождество Эйлера (теория чисел);
— Тождество четырёх квадратов;
— Тождество восьми квадратов;
Тождественные преобразования.
Тождественное преобразование выражения (преобразование выражения) – это подмена одних выражений другими, тождественно равными друг другу.
Для тождественных преобразований используют формулы сокращенного умножения, законы арифметики и другие тождества.
Выполним тождественные преобразования с такой дробью: 
.
Полученное тождество, при х ≠ 0 и х ≠ 1 (недопустимые значения), т.к. знаменатель левой части не может быть равен нулю.
Доказательство тождеств.
Для того, чтоб доказать тождество нужно сделать тождественные преобразования обеих или одной части равенства, и получить слева и справа одинаковые алгебраические выражения.
Например, доказать тождество:
Вынесем х за скобки:
Это равенство есть тождество, при х≠0 и х≠1.
Чтоб доказать, что равенство не является тождеством, нужно найти 1-но значение переменной (которое допустимо) у которой числовые выражения (которые были получены) станут не равными друг другу.
5−1 ≠ 5+1 — подставим, к примеру, 5.
Это равенство не тождество.
Разница между тождеством и уравнением.
Тождество верно при всех значениях переменных, а уравнение – это равенство, которое верно только при одном либо нескольких значениях переменной.
Это выражение верно лишь при х = 10.
Тождеством будет равенство, которое не содержит переменных.
Источник
