Докажите что операция симметрическая разность ассоциативна

Фундаментальная система циклов

По этой ссылке вы найдёте полный курс лекций по математике:

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

Симметрическая разность множеств Симметрической разностью множеств А и В называют множество Фундаментальная система циклов Операция нахождения симметрической разности коммутативна: А Д В = В Д А (это очевидно) и ассоциативна: (попробуйте доказать это с помощью рис. 22). В силу ассоциативности при записи симметрической разности нескольких множеств скобки (указывающие порядок выполнения данной операции над множествами) можно не расставлять. А АВ Рис. 22.

Симметрическая разность двух и трех множеств Пусть А — произвольное множество. Множество всех подмножеств А с операцией симметрической разности (/3(Л), Д) образует коммутативную группу; в роли нейтрального элемента группы выступает пустое множество, каждый элемент группы является обратным самому себе. Лемма 3. При произвольном натуральном п симметрическая разность п множеств состоит в точности из тех элементов данных множеств, которые принадлежат нечетному их числу.

Доказательство проводится индукцией по числу множеств. База индукция очевидна. Индукционный шаг. Пусть доказываемое утверждение справедливо для всех п ^ к. Симметрическая разность к + 1 множеств имеет вид причем p,q ^ к, p + q = k+1. Множество В состоит из элементов, принадлежащих В\ (значит, по индуктивному предположению, принадлежащих нечетному числу множеств из) и не принадлежащих Bi (то есть входящих в четное число множеств из или, наоборот, не принадлежащие В\ и принадлежат** В2 (т. е. принадлежащих четному числу множеств из А\. АР и нечетному числу множеств из Ар+1. yAp+q).

Возможно вам будут полезны данные страницы:

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

Лемма 4. Для любого натурального п сиюлетринеская разность п псевдоциклов есть псевдоцикл. м Доказательство ведется индукцией по п. База индукции (утверждение для п = 1) очевидна. Обоснование индукционного шага сводится к рассмотрению случая двух псевдоциклов. Пусть С\ и — псевдоциклы. Для произвольной вершины v графа обозначим через S,(tj) множество ребер цикла С,, инцидентных v (t = 1,2). Степени вершины v в графах ) равны мощностям множеств S\(v), соответственно.

Множество всех циклов такого вида <Се \ е е Е \ Г>будем называть фундаментмьной системой циклов графа G = (V, Е) относительно стягивающего дерева (V,T). Пример см. на рис.23. Теорема 14. Произвольный цикл С связного графа G = (V,E) представим в виде симметрической разности некоторых циклов из фундаментальной системы циклов G относительно любого стягивающего дерева (V, Т). Такое представление единственно и имеет вид: Мы докажем даже более сильное угверждение, считая С псевдоциклом. Пусть — связный граф, (V, Т) — некоторое фиксированное стягивающее дерево G. Ребра этого дерева будем называть ветвями, а остальные ребра графа G — хордами.

Заметим, что каждый цикл Се содержит ровно одну хорду, а именно — е. Поэтому в симметрической разности (различных) фундаментальных циклов, равной С, должны присутствовать все циклы, отвечающие хордам из С\Г, и только они. Таним образом, если представление псевдоцикла С в виде симметрической разности фундаментальных циклов существует, то оно единственно и имеет вид (1). Докажем теперь, что равенство (1) действительно имеет место.

Пусть По лемме 4 В — псевдоцикл; как уже показано, из хорд В содержит только хорды, принадлежащие С. Применяя леммы 3 и 4, получаем, что симметрическая разность ВАС — псевдоцикл, не содержащий хорд (так как каждая хорда одновременно либо принадлежит, либо не принадлежит В и С, т. е. число се вхождений в данные два множества четно); стало быть, В АС СТ. Осталось доказать, что в В Л С нет и ветвей.

не пуст, то согласно следствию 4 теоремы 9 он имеет не менее двух висячих вершин, в то же время — по определению псевдоцикла — он не содержит висячих вершин. Итак, мы выяснили: 2? Д С = 0, что равносильно совпадению множеств В = Д Се и С. Теорема доказана. На множестве всех псевдоциклов связного графа можно ввести структуру линейного пространства над полем GF<2), где в роли «сложения» выступает симметрическая разность, а умножение на скаляр определяется естественным образом — для произвольного псевдоцикла С имеем:

Если электрической цепи сопоставить граф, ребра которого соответствуют источникам ЭДС, сопротивлениям, индуктивностям и т.д., а вершины — узлам соединений элементов цепи, то при использовании закона Кирхгофа для напряжений, гласящего: сумма падения напряжений вдоль цикла равна нулю, необходимо найти фундаментальную систему циклов. Уравнения, отвечающие этим циклам, не будуг зависеть друг от друга, в то же время их выполнение будет гарантировать выполнение уравнений для всех циклов графа.

Возможно эта страница вам будет полезна:

Присылайте задания в любое время дня и ночи в ➔

Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.

Все авторские права на размещённые материалы сохранены за правообладателями этих материалов. Любое коммерческое и/или иное использование кроме предварительного ознакомления материалов сайта natalibrilenova.ru запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

Источник

Доказать ассоциативность симметрической разности

1. Разности:

A B = A (A B) и A (B C)=(A B) (A C).

Важно.

Операция разности определяется только для двух множеств. Эта операция двухместная и не коммутативная: .

2. Свойство симметрической разности:

.

Доказательство.

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

Пусть , что по определению симметрической разности означает, что x (AB) (B A). Здесь возможны два варианта: либо x (A B), либо x (B A). В первом случае мы получаем: x (A B) (x A и x B) (x A B и x A B), откуда очевидно следует, что x . Ситуация, когда x (B A), рассматривается аналогично.

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

Пусть x (x A B и x A B). Здесь возможны две ситуации: либо и , либо и . Рассмотрим первый случай: пусть и , . Откуда .Второй случай доказывается аналогично.

Важно.

Итак, мы полностью доказали заявленное свойство. При доказательстве подобных утверждений огромную роль играет то свойство, что если некоторый элемент x принадлежит некоторому множеству X, то он, очевидно, будет принадлежать и объединению множества X с произвольным другим множеством.

Определение 5.

Множество U, такое, что все рассматриваемые множества являются его подмножествами, называется универсальным.

То есть это множество, которое по предположению содержит все используемые нами множества. Обозначается не кругом, а прямоугольником (рис. 5).

Определение 6.

Множество U A называется дополнением множества A (до универсального множества) и обозначается через .

На кругах Эйлера это определение представлено на рис. 5.

Принцип двойственности

Теорема двойственности

Теорема 1 (двойственности или де-Моргана).

Пусть A_k, k = 1. n – некоторые подмножества универсального множества U, тогда имеют место следующие равенства:

; . (5)

Эти равенства, связывающие операции пересечения и объединения множеств и их дополнений до универсального множества, называют соотношениями принципа двойственности.

Доказательство.

.

Заметим, что в приведенном доказательстве все утверждения об элементе x соединены знаками , что позволяет одновременно строить доказательство утверждения в обе стороны.

Определим следующие множества: A – множество четных натуральных чисел; B – множество нечетных натуральных чисел; C – множество натуральных чисел, не больше 10. В качестве универсального множества мы будем рассматривать множество натуральных чисел N. Наша задача состоит в том, чтобы описать следующие множества:

.

– это множество нечетных натуральных чисел, т.е. множество B.

2. Каждое натуральное число является либо четным, либо нечетным, поэтому = .

3. = . Следовательно, = N.

Базис операций

Если теперь считать, что в нашем распоряжении имеется универсальное множество U, то операции , , и можно определять друг через друга и фактически ввести некоторый базис операций в алгебре множеств.

1. .

2. .

3. .

Определение 7.

Операции называются булевыми операциями над множествами.

В не может быть подмножеством А.

Необходимо обратить внимание на то, что операция вычитания некоммутативная и неассоциативная, подобно операции вычитания чисел в арифметике. Отсутствие коммутативности очевидно: и.

Докажежем отсутсвие ассоциативности. Покажем, что (А-В)-С не равно А-(В-С). Множество, стоящее в левой части, состоит из элементов множества А, не являющизся при этом элементами ни множества В, ни множества С, т.е. совпадает со множеством А-(В U C) Множество, стоящее в правой части, состоит из элементов множества А, не являющихся при этом элементами множества В, но при этом элементы, являющиеся пересечением множеств А,В и С, входят в это множество, т.е. это множество совпадает со множетсвом А-ВU(A&B&C) .

5.Симметрическая разность, определения и свойства.

B — A .

Это обозначается как C = A /_ B.

Заметим, что A/_ B = (A UB) (B U A), т.к. симметричная разность состоит из тех элементов множеств A и B, которые не принадлежат A и B одновременно. Результатом является множество элементов этих множеств, принадлежащих только одному из них. Увидим, что А /_ B=(AUB)-(A&B), так как симметрическая разность состоит из тех элементов А и В, которые не принадлежат А иВ одновременно.

Доказательство: ⇒ АΔВ⊂(А∪В)(А∩В), ∀x, x∈(АВ)∪(ВА) → x∈AB или х∈ВА → (х∈А и х∉В) или (х∈В и х∉А) → 1) х∈А и х∉А∩В, 2) х∈В и х∉А∩В → х∈(А∪В)(А∩В); в обратную сторону доказывается аналогично.

Заметим, что эта операция является и коммутативной и ассоциативной.

Не знаю, что тут ещё можно написать!

6.Операция дополнения множеств, принцип двойственности.

Дополнение множества А, обозначаемое А’ — это множество элементов универсума, которые не принадлежат А. Следовательно,

Если основное множество обозначить за S, то дополнением множества A называется разность S A (рис. 8). Это обозначается как CA или A с чертой сверху.

Pис. 8 Дополнение множества А

Пример. Если в качестве основного множества S рассмотреть множество всех целых чисел, а в качестве A множество четных чисел, то дополнением множества A будет множество нечетных чисел.

Сформулируем принцип двойственности.

1) дополнение объединения двух множеств равно пересечению дополнений этих множеств:

Не (A UΒ) = (не А) & (не В)

2) дополнение пересечения двух множеств равно объединению дополнений этих множеств:

Не (А & В) = (не А) U(не В)

Докажем равенство (1).

Пусть (x принадлежит (не (А UВ)), т.е. (х не принадлежит (АUB)), таким образом, х не принадлежит ни множеству А, ни множеству В, следовательно (х принадлежит (не А)) и (х принадлежит (не В)), что и означает что (х принадлежит (не А) & (не В)). И так мы доказали.

Архив

Ещё один пример из теории множеств

Формулировка

В одном из предыдущих постов я выбрал некоторые задачки для того, чтобы на их решениях проиллюстрировать, как работать с Мицаром. Сегодня мы возьмём задачку, где требуется доказать следующую цепочку эквивалентностей:

где — симметрическая разность множеств.

Наброски обычного доказательства

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

которая способен легко визуализировать любой, проведший хотя несколько сеансов медитации на математические доказательства. Доказательство первой импликации — просто цепочка равенств

Дальше идёт в ход мантра «циклическая перестановка переменных».

Доказательство на Мицар

Что было использовано в ходе «обычного» доказательства? Коммутативность и ассоциативность симметрической разности, то, что пустое множество для неё играет роль, аналогичную нулю при сложении, а также то, что симметрическая разность множества с самим собой есть пустое. Статья XBOOLE_1 содержит доказательства того, что (X + X = <>, теорема 92) и ассоциативность симметрической разности (теорема 91).

Что касается коммутативности симметрической разности, то если приглядеться к её определению, то можно заметить в нём ключевое слово commutativity. Это одно из возможных так называемых свойств (properties), о которых говорится в статье Наумовича и Былинского Improving MIZAR Texts with Properties and Requirements. Суть свойств в том, что будучи однажды доказаны для какой-либо операции (отношения), они могут применяться в дальнейшем без ссылок на определение, то есть, например, утверждение вроде X + Y = Y + X будет принято при проверке статьи на Мицаре без доказательства. К сожалению, пока из свойств бинарных операций реализованы только коммутативность и идемпотентность, поэтому на доказательство ассоциативности придётся ссылаться явно.

Второе усовершенствование — так называемые требования (requirements), рассматриваемые в вышеуказанной статье, аналогичны свойствам в том смысле, что позволяют на этапе проверки принимать какие-то вещи без доказательств при подключенных требованиях. Подключаются требования в разделе environ директивой requirements. Каждое из существующих сейчас в Мицар требований соответствует одноимённой статье в MML, все теоремы в которой понимаются без ссылок. Также некоторые требования существенно обогащают возможности языка Мицар. Нас сегодня будет интересовать требование BOOLE. Легко видеть, что в статье BOOLE содержится ряд различных тождеств, в частности то, что пустое множество играет для симметрической разности ту же роль, что и ноль для сложения.

Теперь можно привести текст статьи, в которой и производится доказательство нашего нашей незамысловатой цепочки эквивалентностей.

Комментарий к доказательству

Используются словарь XBOOLE_0, где хранятся символы для пустого множества и симметрической разности, конструкторы и нотации из XBOOLE_0 для этих символов (а также коммутативность симметрической разноси из определения), теоремы 91 и 92 из статьи XBOOLE_1 и требования BOOLE (последний шаг доказательства, <> + A = A).

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

Пример доказательства теоретико-множественного тождесва

Эту цепочку утверждений можно читать сверху вниз или снизу вверх (для доказательства вложения или соответственно. Переход между третьей и четвёртой строчками происходит просто по правилам алгебры логики, а между любыми двумя другими — по определениям соответствующих теоретико-множественных операций. На Мицаре это доказательство выглядит более чем аналогично:

Мы используем здесь два остова доказательства: для квантора общности и эквивалентности. Легко заметить, что в блоке hereby и в блоке утверждений, следующем сразу после него, предложения расположены одни и те же, просто в обратном порядке. Ссылки на определения расположены также в обратном порядке. По сути, такое доказательство можно было бы вообще сгенерировать автоматически. Это и неудивительно, потому что сложно представить себе что-то более тривиальное и безыдейное, чем доказательство этого и аналогичных теоретико-множественных тождеств.

Остовы доказательств в Мицар

Остовы доказательств (proof skeletons) играют роль своего рода мантр в Мицар. По сути это некоторые фразы, которые приговариваются в процессе доказательства для пущей убедительности. Я долго пытался понять их логику, но пришёл к выводу, что скорее их нужно запомнить, благо их немного. В любом случае, их можно сгенерировать автоматически.

Форма утверждения задаёт форму его доказательства

В принципе, на этой нехитрой идее и зиждутся все остовы. С одним из них мы уже встречались в предыдущем посте (доказательством импликации)

В этом посте опять же шапка будет общей для всех примеров. Далее, есть остов для доказательств отрицания (приведением к абсурду):

Здесь вместо ключевого слова thesis используется ключевое слово contradiction, обозначающее тождественную ложь. not contradiction, соответственно, является тождественной истиной, в частности, можно написать примерно следующее

Также есть остов доказательства для конъюкции (пример бессодержательный, иллюстрирующий только сам остов)

Остов для эквивалентности

использует ключевое слово hereby, которое выполняет функции одновременно thus и now (то есть в качестве утверждения после ключевого слова thus выступает целый блок now … end;)

На основе остова для импликации и правил классической логики можно получить остов для дизъюнкции

Есть также остовы для квантифицированных предложений. Простой для всеобщности:

И несколько более сложный (по смыслу) для существования:

В случае доказательства существования предложение, начинающееся с ключевого слова set, не входит в остов доказательства. Оно нужно просто для того, чтобы указать, какое именно x имеется в виду в предложении take x; Вообще, ключевое слово set может быть использовано для введения новых переменных и по сути мало чем отличается от оператора присвоения в обычных языках программирования. О ключевом слове set и разными вещами, с ним связанными, поговорим в следующем посте.

Структура доказательства в Мицар

Общий вид формализованного доказательства

Я помню, как на первом курсе пробовал читать «Элементы теории множеств»་ Николя Бурбаки. Там я и познакомился с первым в своей жизни понятием формализованного доказательства. (Да, я затеял написать этот пост после неудачной попытки описать доказательство одного теоретико-множественного тождества.) По сути, оно сводилось к следующему: формализованное доказательство — это последовательность утверждений (по одному на каждой строке, например) таких, что либо утверждение есть аксиома, либо оно выводимо по определённому правилу из одного или нескольких предыдущих. Фактически то же самое можно сказать и о доказательствах в Мицар. Разница состоит лишь в том, что утверждение может начинаться с метки, например

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

(Все дальнейшие примеры кода на Мицаре можно вставлять просто ниже этого текста — «шапку» менять не придётся. Все они прошли проверку на версии Мицар 7.12.01 и MML версии 4.166.1132.) В принципе, здесь может быть не три строчки, а три тысячи, все в одном и том же стиле, едва ли удобном для прочтения человеком.

Первое усовершенствование

В математических рассуждениях часто ссылают на только что доказанные утверждения или только что сделанные предположения (это делается обычно со словами «следовательно», «тогда» или похожими). В Мицар тоже, если нужно сослаться на непосредственно предшествующее утверждение, нет нужды даже давать ему метку, а можно использовать ключевое слово then. В частности, первые две строчки из предыдущего примера можно заменить на

Означает это ровно то же самое, но чуть более человекочитаемо.

Сначала доказательство, а формулировка… А кому-то ещё непонятна формулировка?

Часто бывает, что в математическом тексте утверждения доказываются походя. Просто что-то предполагается, а потом из этих предположений что-то вытекает. Иногда ввиду простоты утверждения совершенно неважно выделять его формулировку в виде классического «Если A, то B». В Мицар такое тоже бывает. Для этого используются операторные скобки now … end; Между этих скобок вообще можно ничего не писать:

либо сделать какой-нибудь вывод, используя ключевое слово thus:

либо ввести какое-нибудь предположение с использованием ключевого слова assume:

Ну и, наконец, можно сделать предположение, а на его основе всё-таки уж что-нибудь да и доказать:

В данном примере уместно спросить, а нельзя ли написать then thus, чтобы избавиться от необходимости ссылаться на метку B? Можно, конечно, но только вместо двух ключевых слов подряд необходимо использовать одно — hence. Тогда этот же пример перепишется следующим образом:

Стандартный формат лемм

Конечно же, есть в Мицар и классические доказательства, где сначала формулируется утверждение, а потом уже оно доказывается. В качестве знаков начала и конца доказательства используются ключевые слова proof … end;

В предыдущем параграфе мы нещадно эксплуатировали одно и то же доказательство одного и того же утверждения, вытекающего из аксиомы фундирования (или аксиомы регулярности, если угодно). Только что мы его же переписали, но с использованием других ключевых слов. Здесь есть знакомые уже нам assume и thus. Важно помнить, что точка с запятой после формулировки леммы не ставится. Конечно же, здесь есть место и слову hence:

Более того, какая же классическая лемма без триумфальных «ч. т. д.» или QED? В Мицаре есть некоторый аналог. Вместо того, чтобы писать формулировку леммы, можно просто использовать ключевое слово thesis:

Чем лемма отличается от теоремы?

На этот волнующий всех школьников вопрос в Мицаре даётся вполне прозаический ответ: теорема — это утверждение, перед которым написано ключевое слово theorem. Ключевое слово это нужно, однако, не для красоты, а для того, чтобы выделить те утверждения, которые будут доступны для ссылок извне статьи. Ссылка TARSKI:1 — это ссылка точно на самое первое утверждение в статье с именем TARSKI, которое помечено ключевым словом theorem. TARSKI:10 — соответственно, на десятое такое утверждение в порядке их следования в тексте статьи. Мы тоже можем сделать две теоремы, на которые благодарные потомки, возможно, будут ссылаться как на HELLO:1 и HELLO:2

Дальше нужно составить некоторое представление об остовах доказательств, то есть о том, чем, собственно, заполнять пространство между словами proof и end; кроме бесконечных цепочек ссылающихся друг на друга утверждений. Об этом — следующий пост.

Теория множеств для первокурсников в Мицар

Источник задачек

Подумав, как лучше продолжить рассказ о Мицаре, я решил привести на нём решения некоторых тривиальных задач, которые изначально предназначались для решения людьми. В качестве таковых были выбраны задачки, предлагавшиеся в 2010 году первокурсникам бакалавриата факультета математики ГУ ВШЭ.

Как вообще на ЭТОМ (!) можно писать.

На самом деле, все необходимые определения для нашей формулы есть в статье XBOOLE_0. Процесс поиска нужной информации может быть иным, но в любом случае все указанные источники: аннотаци, журнальные статьи на английском и гипертекстовые статьи на Мицаре — очень полезны для понимая того, что и как формализовано. Писать на Мицаре наше тождество можно примерно так:

Почему ничего не компилируется.

vocabulary: XBOOLE_0
O 32

Это означает, что — операция (на это указывает символ O), и что её порядок предшествования — 32, а лежит она в словаре XBOOLE_0. Нам повезло, что это совпало с названием той статьи, в которой лежат определения операций. Могло и не повезти. Итак, в секцию environ нужно добавить директиву vocabularies XBOOLE_0; Тогда статья после проверки примет следующий вид:

То есть теперь Мицар жалуется не на незнакомое слово, а на то, что он не знает, как его трактовать в таком контексте. Для того, чтобы помочь ему, нужно использоваться так называемые конструкторы и нотации. На самом деле, это примерно одно и то же и хранится оно в тех статьях, где словам даются определения. После добавления нужных директив (ссылок на статью XBOOLE_0, которую мы просматривали в предыдущем абзаце; именно на статью, а не одноимённый словарь — это очень важно!) и запуска проверки получаем следующее

То есть теперь Мицар всё понимает, то считает, что вывод безоснователен.

Ну и как это теперь доказывать?

Да, в общем-то, так же, как мы бы стали это доказывать и без Мицара. С помощью определения равенства множеств. В Mizar mode for Emacs есть замечательный сервис генерации остовов доказательств. Чтобы воспользоваться им, нужно просто выделить строчку, для которой нужно получить остов доказательства и нажать Ctrl+C S. Если это проделать с последней строчкой, убрав предварительно с её конца точку с запятой, то получим следующее

Скобки proof … end; обозначают начало и конец доказательства, а слово thus обозначает начало утверждения, которое нужно доказать (или его часть, если утверждение обладает структурой позволяющей его доказывать по частям). После слова thus можно просто написать thesis вместо того, чтобы дублировать доказываемое утверждение, которое предшествует слову proof. Есть ещё несколько полезных сокращений. Вывод

(Здесь имеется в виду, что не нужно указывать метку, когда для доказательства следующего утверждения ссылаешься на непосредственное предшествующе.), аналогично

Поскольку мы хотим воспользоваться аксиомой равенства множеств, то следует подключить к теоремам соответствующую статью, а также сформулировать переход, который мы планируем сделать:

Теперь можно снова вызвать генерацию остова доказательства и получить примерно следующее:

Неожиданно завершение

Дойдя до этого места, пожалуй стоит заметить, что хотя может быть интуитивно понятно, что такое proof и hereby, а также в целом структура доказательства, но всё-таки лучше о формализованных доказательствах поговорить отдельно. Этому и будет посвящён следующий пост.

Источник