ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
1.7. Методы доказательства теоретико-множественных тождеств Равенство, левая и правая части которого представляют собой теоре- тико-множественное выражение, верное для любых входящих в них множеств, называют теоретико-множественным тождеством Рассмотрим различные методы доказательстватеоретико-множественных тождеств. 1.7.1. Метод двух включений Пусть левая часть теоретико-множественного тождества определяет множество X , а правая часть — множество Y . Чтобы доказать равенство множеств X и Y , достаточно доказать два включения X Y и Y X , те. доказать, что из предположения x X (для произвольного x) следует, что x Y , и, наоборот, из предположения x Y следует, что x X. Докажем этим методом тождество А В = А В – А В. 23 Пусть x А В. Тогда, согласно определению симметрической разности, x (A – B) (B – A). Это означает, что x (A – B) или x (В – А. Если x (A – B), то х Аи х В, тех Аи при этом х А В. Если же х (В - А, то х В их А, откуда х Аи х А В. Итак, в любом случае из х А – В (В – А) следует х Аи х А В, те. их (А В – А В. Таким образом, доказано, что А В (А В) – (А В. Покажем обратное включение (А В – А В) А В. Пусть х (А В – А В. Тогда х А В их А В. Из х А В следует, что х А или х В. Если х А, то с учетом х А В имеем х В, и поэтому х А – В. Если же х В, то опять- таки в силу х А В получаем, что х Аи х В – А. Итак, х А – Вили х В – А, тех (А – В) (В – А. Следовательно, А В – А В) А В. Оба включения имеют место и тождество доказано. Доказательство сложных теоретико-множественных тождеств методом двух включений часто бывает довольно громоздкими при построении доказательства ход рассуждений не всегда очевиден. 1.7.2. Метод эквивалентных преобразований Теоретико-множественные тождества можно доказывать, используя свойства операций надмножествами (см. п. Свойства операций надмножествами. Для этого нужно преобразовать левую часть в правую, или правую — в левую. Докажем этим методом тождество A (B C) = (A B) (A C). Преобразуем левую часть к правой. 1. По определению B C = (B – C) (C – В, поэтому A (B C) = A ((B – C) (C – B)). 2. Используя свойство дистрибутивности для и получим A (B – C) A (C – B). 3. Используя свойство дистрибутивности для и – получим ((A B) – (A C )) ((A C ) – (A B)). Это есть определение симметрической разности для (A B) и (A C ), те. A (B C) = (A B) (A C). Тождество доказано. 24 При использовании этого метода последовательность преобразований, применяемых при доказательстве, определяется только интуицией исследователя и, как правило, является сложной, творческой задачей попробуйте преобразовать правую часть вышеприведенного тождества в левую. Данный метод можно значительно упростить и формализовать, если левую и правую части тождества преобразовывать в некоторую третью, уникальную форму. Такой формой может быть совершенная НФК. Равенство двух множеств X = Y, в котором множества X и Y представлены в совершенной НФК, является теоретико-множественным тождеством, если совершенные НФК множеств X и Y содержат одинаковое количество конституент и каждой конституенте из совершенной НФК множества X найдется тождественная ей конституента из совершенной НФК множества Y. Две конституенты тождественны, если они состоят из одних и тех же первичных термов. Доказательство теоретико-множественного тождества с использованием совершенной НФК заключается в следующем левую и правую части равенства представить в совершенной НФК, и, если будет получено теоретико-множественное тождество, то и исходное равенство представляет собой теоретико-множественное тождество. Докажем этим методом тождество (A B) C = (A C) (B C). Левая часть C B A ) ( = C B A B A ) ( = Правая часть ) ( ) ( C B C A = C B C A C B C A = = C B C A C B C A ) ( ) ( = Совершенные НФК левой и правой части получены, каждая из них состоит из двух конституент, причем первой конституенте левой части тождественна первая конституента правой части, а второй конституенте левой части тождественна вторая конституента правой части, следовательно исходное равенство является теоретико-множественным тождеством. Метод характеристических функций Метод характеристических функций относится к методам, не требующим угадывания пути доказательства. 25 Арифметические характеристические функции Арифметическая характеристическая функция (АХФ) А множества А для х U определяется следующим образом А) = 1, если x A и А) = 0, если x A. Для АХФ А множества А справедливо тождество А = А. АХФ А В) пересечения множеств Аи В определяется произведением АХФ множеств Аи В А В) = А (x) В (x). Для получения АХФ А В) объединения множеств Аи В сложим АХФ множеств Аи В. Нов этом случае для элементов х А В такая сумма будет иметь значение 2, поэтому из этой суммы необходимо вычесть значение АХФ А В) пересечения множеств Аи В А В = А + В – А (x) В (x). АХФ х) дополнения множества А определяется формулой х) = 1 – А. АХФ А – В) разности множеств Аи В имеет вид А – В = А) – А (x) В (x), а для симметрической разности — А В = А + В – 2 А (x) В (x). Метод характеристических функций доказательства справедливости теоретико-множественного тождества заключается в выражении характеристических функций обеих его частей через характеристические функции входящих в него множеств. Тождества верны тогда и только тогда, когда характеристические функции левой и правой частей совпадают. Докажем этим методом тождество (A B) C = (A C) (B C). C одной стороны, (A B) х = (A B) (х) C (х) = х + В (х)-2 A (х) В (х)) С (х) = = A (х) С (х) + В (х) С (х) – 2 A (х) В (х) С (х). С другой стороны, (A C) (B C) (x) = A C (x) + B C (x) - 2 A C (x) B C (x) = = A (x) C (x) + B (x) C (x) – 2 A (x) C (x) B (x) C (x) = = A (x) C (x) + B (x) C (x) – 2 A (x) B (x) C (x). A A 26 АХФ левой и правой частей тождества совпадают. Следовательно, тождество верно. Логические характеристические функции Логическая характеристическая функция (ЛХФ) А множества А для х U определяется следующим образом А) = TRUE, если x A и А) = FALSE, если x A. ЛХФ А В) пересечения множеств Аи В определяется конъюнкцией ЛХФ множеств Аи В А В) = А) В. ЛХФ А В) пересечения множеств Аи В определяется дизъюнкцией ЛХФ множеств Аи В А В) = А) В. ЛХФ х) дополнения множества А определяется отрицанием ЛХФ множества Ах ) (x A ЛХФ А В) симметрической разности множеств Аи В определяется сложением по модулю 2 ЛХФ множеств Аи В А В) = А) В. ЛХФ А – В) разности множеств Аи В определяется формулой А – В) = А) Доказательство методом ЛХФ проводится также, как и методом АХФ. Для проверки равенства ЛХФ можно использовать их таблицы истинности. Докажем этим методом тождество (A B) C = (A C) (B C). Для левой части (A B) C (x) = A B (x) С (x) = = (А) В) С (x). Для правой части (A C) (B C) (x) = (A C) (x) (B C) (x) = = АСА) С (x). Составим таблицу истинности для ЛХФ левой и правой части табл. В этой таблице «1» соответствует значению TRUE, а «0» — значению FALSE. Таблицы истинности ЛХФ левой и правой части совпадают, следовательно, тождество верно. A A 27 Таблица 1.3 Таблица истинности А (x) B (x) C (x) ЛХФ левой части ЛХФ правой части 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1.7.4. Теоретико-множественный метод Метод основан на вычислении теоретико-множественного тождества при определенных значениях входящих в него множеств, и, если при этих значениях множеств теоретико-множественное тождество истинно, то оно истинно и при любых других значениях входящих в него множеств. Сначала рассмотрим этот метод на примере. Пусть равенство содержит не более трех исходных множеств, например. Множества, определяемые левой и правой частью равенства, можно изобразить графически на кругах Эйлера, и, если эти множества изображаются одинаково, то равенство представляет собой теоретико- множественное тождество. Круги Эйлера, соответствующие множествами, находящимся в общем положении, разбивают плоскость на восемь непересекающихся областей (соответствует разбиению универсума на восемь подмножеств. Пронумеруем эти области так, как показано на рис. Каждое из исходных множеств (A, B и C) теперь можно представить как множество, состоящее из четырех непересекающихся областей и считать, что A = {1, 3, 5, 7}, B = {2, 3, 6, 7} и C = {4, 5, 6, 7}. Для того, чтобы найти множество областей, соответствующих множеству, определяемому левой частью равенства, подставим полученные значения множеств A, B ив левую часть равенства и вычислим его значение (A ∆ B) C = ({1, 3, 5, 7} ∆ {2, 3, 6, 7}) {4, 5, 6, 7} = = {1, 2, 5, 6} {4, 5, 6, 7} = {5, 6}. Следовательно, множество, соответствующее левой части равенства, определяется на кругах Эйлера областями 5 и 6. 28 А 1 3 2 В 5 7 6 0 4 С Рис. Разбиение универсума множествами А, В и Сна подмножества Аналогично определим множество областей, соответствующих множеству, определяемому правой частью равенства (A C) ∆ (B C) = =({1, 3, 5, 7} {4, 5, 6, 7}) ∆ ({2, 3, 6, 7} {4, 5, 6, 7}) = = {5, 7} ∆ {6, 7} = {5, 6}. Множества, соответствующие левой и правой части равенства, определяются на кругах Эйлера одинаковыми областями, следовательно, равенство является теоретико-множественным тождеством. Из рассмотренного примера следует, что для доказательства теоре- тико-множественного тождества достаточно вычислить значение соответствующего равенства на определенных значениях входящих в равенство множествах, и, если получим истинное значение, то теоретико- множественное тождество верно. Если количество n входящих в равенство множеств больше трех, то использование кругов Эйлера для нахождения значений множеств становится громоздкими ненаглядным. Количество областей в этом случае равно 2 n и каждой области можно поставить во взаимно-однозначное соответствие разрядный двоичный вектор, в котором й разряд соответствует i-му множеству равенства и равен 1, если область принадлежит этому множеству ив противном случае. Двоичный вектор, соответствующий й области, можно рассматривать как двоичное представление числа j. Для трех множеств сопоставление областям двоичных векторов представлено в табл. По такой таблице значение множества определяется следующим образом просматривается столбец, соответствующий множеству, и, если встречается единица, то номер строки (номер области) добавляется в множество. 29 Из рассмотренного выше следует, что для доказательства теоретико- множественного тождества, содержащего n множеств, необходимо построить таблицу двоичных разрядных векторов, состоящую из 2 n строк, по таблице определить значения входящих в равенство множеств, вычислить значение равенства на этих множествах, и, если получим истинное значение, то теоретико-множественное тождество верно. Таблица 1.4 Сопоставление областям универсума двоичных векторов Номер области Двоичный вектор C B A 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 1.7.5. Метод симметрической разности Пусть множества X ив равенстве X = Y представлены теоретико- множественными выражениями. Множества X и Y равны тогда и только тогда, когда X ∆ Y = , поэтому для доказательства теоретико- множественного тождества X = Y достаточно доказать X ∆ Y = Для доказательства X ∆ Y = можно множество X ∆ Y представить в НФК (см. выше) или применять разложение Шеннона и выполнять упрощения, используя свойства нуля и единицы и дополнения. Докажем этим методом тождество (A B) C = (A C) (B C). (A B) C (A C) (B C) = = )) ( ) ( ) (( C B C U C B U A )) ( ) ( ) (( C B C C B A = = )) ( ) (( C B C C B A )) ( ) (( C B C B A = = ))) ( ) (( )) ( ) (( ( C C C B C U C C U B A = = )) ( ) ( ( C C B C C B A = ) ( A = 30 1.8. Теоретико-множественные уравнения Теоретико-множественным уравнением (уравнением с множествами) называется равенство g ( X, A 1 ,…, A n ) = h ( X, A 1 ,…, где A 1 ,…, A n — известные исходные множества, A i U, U — конечный универсум X — неизвестное искомое множество X U; g ( X, A 1 ,…, A n ) и h ( X, A 1 ,…, A n )— теоретико-множественные выражения. Множество X, при котором равенство принимает истинное значение, называется частным решением уравнения, а множество всех частных решений образует общее решение Для решения уравнения приведем его к виду f ( X, A 1 ,…, A n ) = . Множество f ( X, A 1 ,…, A n ) пусто тогда и только тогда, когда множество) равно множеству h ( X, A 1 ,…, A n ), поэтому ( X, A 1 ,…, A n ) ∆ h ( X, A 1 ,…, A n ) = . Выполним разложение Шеннона левой части полученного уравнения по неизвестному множеству X: X X U = , где = f ( , A 1 ,…, A n ), U = f (U, A 1 ,…, A n ). Множества и определяются универсумом U, пустым множеством и известными исходными множествами, поэтому можно вычислить их значения. Это уравнение имеет решение, если и X U = Множество X пусто тогда и только тогда, когда X , или, тоже самое, X , а множество X пусто тогда и только тогда, когда X U , поэтому множество X должно быть подмножеством множества и надмножеством множества , те. X Решение этого неравенства является частным решением исходного уравнения, а множество всех его решений — общим решением уравнения. Уравнение имеет хотя бы одно решение, если U . Если = и U = U , то частным решением будет любое подмножество универсума, а общим решением — булеан универсума. Если уравнение имеет решение, то минимальным по мощности будет X = , а максимальным. Частным решением уравнения будет любое множество, являющееся подмножеством множества U и включающим в себя множество , те. X = i , где i U – . Следовательно, для получения общего решения уравнения необходимо породить все 31 подмножества множества U – и каждое из них объединить с множеством Рассмотрим пример решения теоретико-множественного уравнения при A = {3, 4, 5, 6, 8, 10}, B = {1, 2, 7, 8, 9, 10}, C = {1, 2, 3, 4, 5, 10} и U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. 1. Преобразуем исходное уравнение в уравнение с пустой правой частью. Выполним разложение Шеннона левой части уравнения по неизвестному множеству X: где , ) ( ) ( B A A C B ) ( ) ( U B U A A C U B U 3. Упростим и U , используя свойства нуля, единицы и дополнения. Вычислим и U при заданных исходных множествах }, 6 , 5 , 4 , 3 { } 10 , 9 , 8 , 7 , 2 , 1 { } 10 , 9 , 8 , 7 , 2 , 1 { } 10 , 8 , 6 , 5 , 4 , 3 { } 10 , 5 , 4 , 3 , 2 , 1 { } 10 , 9 , 8 , 7 , 2 , 1 { U } 6 , 5 , 4 , 3 { } 10 , 8 , 6 , 5 , 4 , 3 { } 9 , 8 , 7 , 6 { } 10 , 9 , 8 , 7 , 2 , 1 { } 6 , 5 , 4 , 3 { } 10 , 9 , 7 , 6 , 5 , 4 , 3 { } 6 , 5 , 4 , 3 { } 10 , 8 , 6 , 5 , 4 , 3 { } 9 , 8 , 7 { }. 8 , 6 , 5 , 4 , 3 , 2 , 1 { } 10 , 9 , 7 { 5. Множество = {3, 4, 5, 6} является подмножеством множества U = {1, 2, 3, 4, 5, 6, 8}, следовательно, уравнение имеет решения. 6. Минимальным по мощности частным решением является множество, а максимальным — U = {1, 2, 3, 4, 5, 6, 8}. 7. Для получения общего решения необходимо каждое подмножество множества U – = {1, 2, 8} объединить с = {3, 4, 5, 6}. Общее решение {{3, 4, 5, 6}, {3, 4, 5, 6, 1}, {3, 4, 5, 6, 2}, {3, 4, 5, 6, 1, 2}, {3, 4, 5, 6, 8}, {3, 4, 5, 6, 1, 8}, {3, 4, 5, 6, 2, 8}, {3, 4, 5, 6, 1, 2, 8}}. Самостоятельно выполните проверку решения. |