Математика · объяснение и практика
Как восстановить множество по дельте изменений и отменить повторные переключения
Как симметрическая разность позволяет восстановить прежний набор, объединить последовательность переключений и увидеть, почему два одинаковых изменения отменяются, а объединение списков не подходит.

В теме Множества, отношения и математическая логика · Учебная карта
В маршруте Множества, отношения и мощности · 10 тем
Главная мысль
Если дельта D задаёт элементы, чьё присутствие переключается, новое множество равно B=A△D. Прежнее состояние восстанавливается тем же действием: A=B△D. Для нескольких таких дельт складывают их симметрической разностью; два одинаковых переключения каждого элемента взаимно отменяются.
Дельта описывает переключение, а не новое полное состояние
Зададим точную модель: каждый номер либо включён в набор, либо отсутствует. Дельта содержит номера, у которых этот признак нужно изменить. Присутствующий номер удаляется, отсутствующий добавляется. Такое переключение выражается симметрической разностью. Это отдельный договор о значении данных, а не свойство любого списка с названием «изменения».
Пусть исходно A={1,4,7}, а D={4,6}. Применив дельту, получаем B={1,6,7}: четвёрка исчезла, шестёрка появилась. Размер набора остался равным трём, хотя само множество изменилось. Поэтому одно сравнение размеров не восстанавливает изменения. Для поставленной задачи сохраняют конкретные номера и правило их переключения.
Восстановить исходный набор тем же действием
При повторном переключении всех номеров D каждый возвращается в прежнее состояние. Элементы вне D оба раза не затронуты. Отсюда (A△D)△D=A. В нашем примере {1,6,7}△{4,6} снова даёт {1,4,7}. Направление добавления или удаления не требуется хранить отдельно: его определяет известное текущее состояние.
Если последовательно применены D₁ и D₂, конечное состояние равно A△D₁△D₂. Для восстановления можно применить обе дельты ещё раз. Их общая дельта равна D₁△D₂, а не обычному объединению. Общий номер переключается дважды и потому не должен оставаться в итоговом списке переключений.
Пример
Пусть A={1,2}, D₁={2,4}, D₂={4,5}. Найдите общее изменение и конечный набор.
Общая дельта равна {2,5}: номер4 встретился дважды и отменился. По шагам получаем {1,4}, затем {1,5}. Сразу A△{2,5} даёт то же {1,5}. Номер4 нельзя оставить как итоговое добавление.
Проверить условия обратимости модели
Доказательство можно провести для каждого номера отдельно: ноль обозначает отсутствие, единица — присутствие. Переключение меняет одно значение на другое, а два переключения возвращают исходное. Поэтому при известной полной дельте новое состояние однозначно определяет старое. Ассоциативность позволяет группировать эти операции; порядок не влияет на окончательное множество в данной модели.
Если сообщение содержит новое полное состояние вместо дельты, повторное применение уже не обязано отменять действие. Команды «добавить» или «удалить» тоже отличаются от переключения. Например, повтор команды добавления не удаляет номер обратно. Для списков с кратностями нужна иная модель. Перед восстановлением следует установить смысл сообщения, полноту записей и одинаковые обозначения номеров, иначе красивая формула решит другую задачу.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли заменить общую дельту объединением списков?
Нет. При объединении общий элемент остаётся, а два последовательных переключения должны отмениться. Нужна симметрическая разность дельт.
Достаточно знать только число переключённых номеров?
Нет. Разные дельты одинакового размера дают разные исходные наборы. Для точного восстановления нужны сами элементы дельты и известное текущее состояние.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Чем «ровно одно» отличается от обычного математического «или»
Как читать условие «или» в математике, отличать ровно одно событие от хотя бы одного и переводить словесное исключение в точную логическую формулу.
Открыть темуПочему дополнение объединения превращается в пересечение дополнений
Как превратить условие «не входит в объединение» в пересечение дополнений, выбрать общее универсальное множество и не потерять область отрицания.
Открыть тему