EssayAI
Блог
Блог
Естественные науки

Характеристическая функция множества: определение и примеры

8 ноября 2026Время чтения: 8 минут
#характеристическая функция#индикатор множества#теория множеств#битовая маска#логические операции
Характеристическая функция множества: определение и примеры

Как записать множество так, чтобы компьютер мог быстро проверять принадлежность и выполнять операции над его элементами? Один ответ - сопоставить каждому элементу универсального множества число: единицу, если он выбран, и ноль в противном случае. Получается характеристическая функция множества, или его индикатор. Попробуйте менять элемент в калькуляторе: он покажет сразу четыре ответа для двух множеств, их пересечения и объединения.

Определение: принадлежность как функция

Пусть задано универсальное множество UU и его подмножество A⊆UA\subseteq U. Характеристическая функция AA определена на всём UU:

χA(x)={1,x∈A,0,x∉A.\chi_A(x)=\begin{cases}1,& x\in A,\\0,& x\notin A.\end{cases}

Вместо χA\chi_A часто пишут 1A\mathbf{1}_A или [x∈A][x\in A]. Последняя запись называется скобкой Айверсона: утверждению ставится в соответствие единица, когда оно истинно, и ноль, когда ложно. Все три записи описывают одну идею; важно лишь заранее объявить область определения.

На видео указатель проходит по элементам UU: единица появляется в строке индикатора именно под элементами множества AA.

Указатель проходит по восьми элементам и связывает каждый элемент со значением его индикатора: единицей для элементов A и нулём для остальных.

Функция полностью определяет подмножество: A={x∈U:χA(x)=1}A=\{x\in U:\chi_A(x)=1\}. И наоборот, любая функция из UU в {0,1}\{0,1\} задаёт такое подмножество. Это взаимно однозначное соответствие позволяет переводить задачи о множествах на язык функций и обратно.

Пример на восьми элементах

Возьмём U={1,2,3,4,5,6,7,8}U=\{1,2,3,4,5,6,7,8\}, A={2,3,5,8}A=\{2,3,5,8\} и B={3,4,5,7}B=\{3,4,5,7\}. Для x=3x=3 обе функции равны единице: элемент находится в обоих множествах. Для x=4x=4 получаем χA(4)=0\chi_A(4)=0, но χB(4)=1\chi_B(4)=1. Число 66 не входит ни в одно из них, а значит, оба индикатора для него равны нулю.

При фиксированном порядке элементов удобно выписать все значения подряд. Для AA получается вектор (0,1,1,0,1,0,0,1)(0,1,1,0,1,0,0,1), а для BB - (0,0,1,1,1,0,1,0)(0,0,1,1,1,0,1,0). Позиция в векторе соответствует элементу UU: первая - единице, вторая - двойке и так далее. Это соглашение необходимо, иначе одна и та же последовательность битов может означать другое множество.

Из таблицы видно, что A∩B={3,5}A\cap B=\{3,5\} содержит два элемента, а A∪B={2,3,4,5,7,8}A\cup B=\{2,3,4,5,7,8\} - шесть. На каждой позиции строки получены независимо друг от друга.

Таблица индикаторов двух множеств и их пересечения и объединения для элементов от одного до восьми
Таблица индикаторов двух множеств и их пересечения и объединения для элементов от одного до восьми

Выбор для каждого из восьми элементов независим: он либо входит в подмножество, либо нет. Поэтому возможных индикаторов, как и подмножеств UU, ровно 28=2562^8=256. Объяснение этого подсчёта есть в статье о числе подмножеств множества.

Операции над множествами через нули и единицы

Пусть a=χA(x)a=\chi_A(x) и b=χB(x)b=\chi_B(x). Произведение abab равно единице только тогда, когда оба сомножителя равны единице. Поэтому пересечению соответствует формула

χA∩B(x)=χA(x)χB(x).\chi_{A\cap B}(x)=\chi_A(x)\chi_B(x).

Для объединения подходит выражение a+b−aba+b-ab: если оба индикатора равны единице, вычитание убирает двойной счёт. Дополнение берётся относительно выбранного UU; его индикатор меняет ноль на единицу и наоборот. В итоге получаем:

χA∪B=χA+χB−χAχB,χU∖A=1−χA.\chi_{A\cup B}=\chi_A+\chi_B-\chi_A\chi_B,\qquad \chi_{U\setminus A}=1-\chi_A.

Равенства понимаются поточечно: для каждого x∈Ux\in U подставляются значения в этой точке. Например, при x=3x=3 имеем 1+1−1⋅1=11+1-1\cdot1=1; простая сумма дала бы 22, а это уже не индикатор объединения. Для разности A∖BA\setminus B аналогично выходит χA(1−χB)\chi_A(1-\chi_B): элемент должен входить в первое множество и не входить во второе.

Ещё один способ проверить формулы - перебрать четыре пары (a,b)(a,b): (0,0)(0,0), (0,1)(0,1), (1,0)(1,0), (1,1)(1,1). Пересечение даёт последовательность 0,0,0,10,0,0,1, объединение - 0,1,1,10,1,1,1. Эти же правила известны как логические операции И и ИЛИ. Для двух индикаторов также верны записи min⁡(a,b)\min(a,b) и max⁡(a,b)\max(a,b) соответственно.

От индикатора к битовой маске

Если UU конечно и его элементы упорядочены, значения индикатора можно хранить как массив битов. Битовая маска представляет то же подмножество, но в форме, удобной для поразрядных операций. Поразрядное И двух масок строит пересечение, ИЛИ - объединение, а исключающее ИЛИ - элементы, входящие ровно в одно множество.

Например, для наших AA и BB поразрядное И векторов (0,1,1,0,1,0,0,1)(0,1,1,0,1,0,0,1) и (0,0,1,1,1,0,1,0)(0,0,1,1,1,0,1,0) даёт (0,0,1,0,1,0,0,0)(0,0,1,0,1,0,0,0). Единицы на третьей и пятой позициях указывают на {3,5}\{3,5\}. Чтобы получить дополнение, инвертируют биты только на позициях, соответствующих UU. В машинном слове могут быть дополнительные биты, поэтому после инверсии их нужно ограничить маской допустимых позиций.

Битовый вектор полезен, когда универсум сравнительно невелик или операции над многими элементами выполняются вместе. При очень большом разреженном универсуме хранение всех нулей может быть неудобным; тогда используют другие структуры данных. Логический смысл индикатора при этом не меняется. Если элементы - упорядоченные пары, их можно брать из декартова произведения множеств: индикатор отношения показывает, входит ли конкретная пара в отношение.

Суммы индикаторов и подсчёт

Для конечного UU сумма значений индикатора просто считает выбранные элементы:

∣A∣=∑x∈UχA(x).|A|=\sum_{x\in U}\chi_A(x).

В нашем примере сумма 0+1+1+0+1+0+0+1=40+1+1+0+1+0+0+1=4. Если подставить формулу объединения и просуммировать по UU, получится правило включений и исключений для двух множеств:

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=4+4−2=6.|A\cup B|=|A|+|B|-|A\cap B|=4+4-2=6.

Каждый общий элемент сначала посчитан дважды, поэтому его надо вычесть один раз. В программном коде тот же принцип встречается при подсчёте записей, удовлетворяющих условиям: индикатор превращает каждый ответ «да» или «нет» в число, которое можно суммировать. В задачах случайного выбора индикатор события становится случайной величиной; его математическое ожидание равно вероятности события. Более общий смысл ожидания разобран в статье о математическом ожидании биномиального распределения.

Индикаторы помогают и при фильтрации таблицы. Пусть AA - строки, где выполнено первое условие, а BB - строки, где выполнено второе. Сумма произведений ∑x∈UχA(x)χB(x)\sum_{x\in U}\chi_A(x)\chi_B(x) считает строки, удовлетворяющие обоим условиям. Если требуется хотя бы одно, вместо произведения используют формулу объединения. Важно, что xx здесь обозначает строку целиком, а не обязательно число: элементы универсума могут быть файлами, пользователями или другими объектами. Нулевой результат означает, что подходящих строк в выбранном конечном наборе нет.

Граница множества и область определения

На числовой прямой та же конструкция работает для бесконечных множеств. Например, для A=[2,5)A=[2,5) индикатор равен единице при 2≤x<52\le x<5 и нулю в остальных точках R\mathbb R. Именно скобки определяют значения на концах: χA(2)=1\chi_A(2)=1, а χA(5)=0\chi_A(5)=0. Рисуя график ступенькой, отмечают включённую и исключённую точки по-разному.

Область определения тоже имеет значение. Для одного и того же AA дополнение в U={1,2,3}U=\{1,2,3\} и в V={1,2,3,4}V=\{1,2,3,4\} различается, поскольку во втором случае появляется элемент 44. Формула 1−χA1-\chi_A применима на том универсуме, на котором задана функция. Пустое множество имеет индикатор, всюду равный нулю, а всё UU - всюду равный единице.

Не путайте этот индикатор с характеристической функцией случайной величины. Названия совпадают, но в теории вероятностей под вторым объектом обычно понимают комплекснозначное преобразование распределения, а не проверку принадлежности элемента множеству.

Как решать задачу по шагам

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

Затем переведите операции над множествами в операции над индикаторами. Для пересечения проверьте оба условия, для объединения достаточно хотя бы одного, для разности первое должно выполняться при невыполнении второго. Проверьте результат на элементе из обоих множеств и на элементе вне обоих: эти крайние случаи часто обнаруживают ошибку со сложением или дополнением.

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

Частые ошибки

  • Забывать универсум. Без него не определено, относительно чего берётся дополнение и где функция принимает значения.
  • Считать сумму индикаторов индикатором объединения всегда. В общей точке сумма равна двум; необходимо вычесть произведение.
  • Путать элемент и позицию бита. Сначала фиксируют порядок элементов UU, затем читают вектор в этом порядке.
  • Терять концы интервала. В [2,5)[2,5) число 22 входит в множество, а 55 - нет.
  • Распространять конечную сумму без условий. Для бесконечного множества обычная конечная формула подсчёта требует отдельного рассмотрения сходимости.

FAQ

Может ли индикатор принимать значение 0,5?

Нет. Характеристическая функция обычного множества принимает только ноль и единицу. Значения между ними могут появляться в других моделях, например в функциях принадлежности нечётких множеств, но смысл там иной.

Чем индикатор отличается от самого множества?

Множество состоит из элементов, а индикатор - функция, определённая на UU. При фиксированном универсуме каждый из этих объектов однозначно восстанавливается по другому.

Когда произведение индикаторов равно нулю всюду?

Тогда и только тогда, когда AA и BB не пересекаются: нигде нет элемента, для которого оба индикатора равны единице.

Коротко

Характеристическая функция кодирует принадлежность элемента множеству числами 00 и 11. Произведение индикаторов задаёт пересечение, формула a+b−aba+b-ab - объединение, а 1−a1-a - дополнение относительно выбранного универсума. Для конечного множества эти значения образуют битовый вектор и позволяют считать элементы суммированием.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Арифметико-логическое устройство АЛУ: функции

Арифметико-логическое устройство АЛУ: функции

Что делает арифметико-логическое устройство: операции над битами, сложение с переносом, флаги и пример четырёхразрядного АЛУ с интерактивным расчётом.

8 ноября 20268 минут
Частично упорядоченное множество: примеры и диаграмма

Частично упорядоченное множество: примеры и диаграмма

Разбираем частично упорядоченное множество: свойства отношения, сравнимые элементы, диаграмму Хассе и отличие максимального элемента от наибольшего на примерах.

8 ноября 20269 минут
Нечёткое множество: функция принадлежности и примеры

Нечёткое множество: функция принадлежности и примеры

Что такое нечёткое множество и функция принадлежности: разбираем пример температуры, операции, альфа-срезы и отличие степени принадлежности от вероятности.

8 ноября 20268 минут
Релейно-контактная схема: чтение и примеры

Релейно-контактная схема: чтение и примеры

Релейно-контактная схема простыми словами: как читать контакты и катушки, составлять таблицу состояний, переводить соединения в логику и разбирать цепь Пуск и Стоп.

8 ноября 20268 минут
Вполне упорядоченное множество: определение и примеры

Вполне упорядоченное множество: определение и примеры

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

8 ноября 20268 минут
Импликация и эквивалентность: таблица истинности

Импликация и эквивалентность: таблица истинности

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

8 ноября 202610 минут