Коллоквиумы по курсу ДМ
Найдено определений: 106
Коллоквиум 1 · Вопрос № 1

Определение Множества (любое из трех)

  1. Определение Георга Кантора (1895 г.): Множество есть объединение в одно целое определенных, вполне различимых объектов нашего восприятия или нашей мысли (которые называются элементами множества).
  2. Определение наивной теории множеств: Неопределяемое первичное понятие математики, обозначающее совокупность уникальных объектов произвольной природы (элементов), мыслимую как единое целое.
  3. Аксиоматическое определение (система Цермело–Френкеля, ZFC): Множество — это абстрактный объект теории, для которого задано первичное бинарное отношение принадлежности ∈\in («быть элементом»), подчиняющееся аксиомам ZFC (аксиоме объемности, выделения, степени, объединения и др.).
Примеры, свойства и пояснения:

Множество натуральных чисел N={1,2,3,… }\mathbb{N} = \{1, 2, 3, \dots\}; пустое множество ∅\varnothing; {a,b,c}\{a, b, c\}.

Коллоквиум 1 · Вопрос № 2

Способы задания множеств

Существуют три основных способа задания множеств:

  1. Явным перечислением элементов (списком): A={x1,x2,…,xn}A = \{x_1, x_2, \dots, x_n\} (применимо для конечных множеств);
  2. Характеристическим предикатом (свойством): A={x∈U∣P(x)}A = \{x \in U \mid P(x)\}, где P(x)P(x) — логическое условие, истинное в точности для элементов множества AA;
  3. Порождающей процедурой (индуктивно / рекурсивно): задаются базовые элементы (базис индукции) и правила построения новых элементов из уже имеющихся (индукционный шаг).
Примеры, свойства и пояснения:

Список: A={2,4,6}A = \{2, 4, 6\}; предикат: B={x∈Z∣x≡0(mod2)}B = \{x \in \mathbb{Z} \mid x \equiv 0 \pmod 2\}; индуктивно: 0∈N00 \in \mathbb{N}_0, и если n∈N0n \in \mathbb{N}_0, то n+1∈N0n+1 \in \mathbb{N}_0.

Коллоквиум 1 · Вопрос № 3

Подмножество и отличие собственных и несобственных подмножеств

  • Множество AA называется подмножеством множества BB (A⊆BA \subseteq B), если каждый элемент множества AA является элементом множества BB:
    ∀x  (x∈A  ⟹  x∈B)\forall x \; (x \in A \implies x \in B)
  • Несобственными подмножествами множества AA называются пустое множество ∅\varnothing и само множество AA (A⊆AA \subseteq A по рефлексивности).
  • Собственным (строгим) подмножеством (A⊂BA \subset B или A⊊BA \subsetneq B) называется такое подмножество, которое не совпадает со всем BB:
    A⊂B  ⟺  A⊆B∧A≠BA \subset B \iff A \subseteq B \land A \ne B
Примеры, свойства и пояснения:

Для A={1,2}A = \{1, 2\}: несобственные — ∅\varnothing и {1,2}\{1, 2\}; собственные — ∅\varnothing, {1}\{1\}, {2}\{2\}.

Коллоквиум 1 · Вопрос № 4

Булеан множества

Булеаном (множеством всех подмножеств, степенным множеством / power set) множества AA называется семейство всех возможных подмножеств множества AA, обозначаемое P(A)\mathcal{P}(A) или 2A2^A:

P(A)={X∣X⊆A}\mathcal{P}(A) = \{X \mid X \subseteq A\}
Если множество AA конечно и содержит ∣A∣=n|A| = n элементов, то мощность булеана равна ∣P(A)∣=2n|\mathcal{P}(A)| = 2^n.

Примеры, свойства и пояснения:

Для A={a,b}A = \{a, b\}: P(A)={∅,{a},{b},{a,b}}\mathcal{P}(A) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}, ∣P(A)∣=22=4|\mathcal{P}(A)| = 2^2 = 4.

Коллоквиум 1 · Вопрос № 5

Объединение множеств

Объединением множеств AA и BB называется множество A∪BA \cup B, состоящее из всех элементов, принадлежащих хотя бы одному из множеств AA или BB:

A∪B={x∣x∈A∨x∈B}A \cup B = \{ x \mid x \in A \lor x \in B \}

Примеры, свойства и пояснения:

{1,2}∪{2,3}={1,2,3}\{1, 2\} \cup \{2, 3\} = \{1, 2, 3\}.

Коллоквиум 1 · Вопрос № 6

Пересечение множеств

Пересечением множеств AA и BB называется множество A∩BA \cap B, состоящее из всех элементов, которые одновременно принадлежат и множеству AA, и множеству BB:

A∩B={x∣x∈A∧x∈B}A \cap B = \{ x \mid x \in A \land x \in B \}

Примеры, свойства и пояснения:

{1,2,3}∩{2,3,4}={2,3}\{1, 2, 3\} \cap \{2, 3, 4\} = \{2, 3\}. Если A∩B=∅A \cap B = \varnothing, множества называют непересекающимися (дизъюнктными).

Коллоквиум 1 · Вопрос № 7

Дополнение множества

  • Относительное дополнение множества BB до множества AA — это разность A∖BA \setminus B.
  • Абсолютное дополнение множества AA (относительно универсального множества UU, где A⊆UA \subseteq U), обозначаемое A‾\overline{A} или AcA^c, — это множество всех элементов универсального множества, не принадлежащих AA:
    A‾=U∖A={x∈U∣x∉A}\overline{A} = U \setminus A = \{ x \in U \mid x \notin A \}
Примеры, свойства и пояснения:

Если U={1,2,3,4,5}U = \{1, 2, 3, 4, 5\} и A={2,4}A = \{2, 4\}, то A‾={1,3,5}\overline{A} = \{1, 3, 5\}.

Коллоквиум 1 · Вопрос № 8

Разность множеств

Разностью множеств AA и BB называется множество A∖BA \setminus B (или A−BA - B), состоящее из всех элементов множества AA, которые не принадлежат множеству BB:

A∖B={x∣x∈A∧x∉B}A \setminus B = \{ x \mid x \in A \land x \notin B \}

Примеры, свойства и пояснения:

{1,2,3,4}∖{3,4,5}={1,2}\{1, 2, 3, 4\} \setminus \{3, 4, 5\} = \{1, 2\}.

Коллоквиум 1 · Вопрос № 9

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

Симметрической разностью множеств AA и BB называется множество A△BA \triangle B (или A⊕BA \oplus B), состоящее из элементов, принадлежащих ровно одному из множеств AA или BB:

A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B)={x∣x∈A⊕x∈B}A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B) = \{ x \mid x \in A \oplus x \in B \}

Примеры, свойства и пояснения:

{1,2,3}△{2,3,4}={1,4}\{1, 2, 3\} \triangle \{2, 3, 4\} = \{1, 4\}.

Коллоквиум 1 · Вопрос № 10

Декартово произведение множеств

Декартовым (прямым) произведением двух множеств AA и BB называется множество всех упорядоченных пар (a,b)(a, b), в которых первый элемент принадлежит AA, а второй принадлежит BB:

A×B={(a,b)∣a∈A∧b∈B}A \times B = \{ (a, b) \mid a \in A \land b \in B \}
Для конечных множеств мощность ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|.

Примеры, свойства и пояснения:

{1,2}×{x,y}={(1,x),(1,y),(2,x),(2,y)}\{1, 2\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y)\}.

Коллоквиум 1 · Вопрос № 11

Прямое произведение четырех множеств

Прямым (декартовым) произведением четырех множеств A1,A2,A3,A4A_1, A_2, A_3, A_4 называется множество всех упорядоченных 4-кортежей (четверок) (a1,a2,a3,a4)(a_1, a_2, a_3, a_4), где каждый ii-й компонент принадлежит множеству AiA_i:

A1×A2×A3×A4={(a1,a2,a3,a4)∣a1∈A1,a2∈A2,a3∈A3,a4∈A4}A_1 \times A_2 \times A_3 \times A_4 = \{ (a_1, a_2, a_3, a_4) \mid a_1 \in A_1, a_2 \in A_2, a_3 \in A_3, a_4 \in A_4 \}
Мощность: ∣A1×A2×A3×A4∣=∣A1∣⋅∣A2∣⋅∣A3∣⋅∣A4∣|A_1 \times A_2 \times A_3 \times A_4| = |A_1| \cdot |A_2| \cdot |A_3| \cdot |A_4|.

Примеры, свойства и пояснения:

Если Ai={0,1}A_i = \{0, 1\}, то {0,1}4\{0, 1\}^4 — множество всех 4-битных двоичных слов.

Коллоквиум 1 · Вопрос № 12

Кортеж

Кортежем (упорядоченным набором, вектором, nn-кой) длины nn называется упорядоченная последовательность из nn элементов (x1,x2,…,xn)(x_1, x_2, \dots, x_n), где каждому элементу сопоставлен его фиксированный позиционный номер от 11 до nn. В отличие от множества, в кортеже порядок элементов строго фиксирован, а элементы могут повторяться.

Примеры, свойства и пояснения:

(1,2)≠(2,1)(1, 2) \ne (2, 1), тогда как {1,2}={2,1}\{1, 2\} = \{2, 1\}.

Коллоквиум 1 · Вопрос № 13

Равенство упорядоченных пар/кортежей

Два кортежа одинаковой длины равны тогда и только тогда, когда равны все их соответствующие по порядку координаты:

(a1,a2,…,an)=(b1,b2,…,bn)  ⟺  a1=b1∧a2=b2∧⋯∧an=bn(a_1, a_2, \dots, a_n) = (b_1, b_2, \dots, b_n) \iff a_1 = b_1 \land a_2 = b_2 \land \dots \land a_n = b_n
Для упорядоченных пар: (a,b)=(c,d)  ⟺  a=c∧b=d(a, b) = (c, d) \iff a = c \land b = d.

Примеры, свойства и пояснения:

(x,3)=(5,y)  ⟺  x=5∧y=3(x, 3) = (5, y) \iff x = 5 \land y = 3.

Коллоквиум 1 · Вопрос № 14

Свойство коммутативности

Операция ∗* называется коммутативной на множестве SS, если результат операции не зависит от порядка операндов:

∀A,B(A∗B=B∗A)\forall A, B \quad (A * B = B * A)
В алгебре множеств коммутативны объединение, пересечение и симметрическая разность:
A∪B=B∪A,A∩B=B∩A,A△B=B△AA \cup B = B \cup A, \quad A \cap B = B \cap A, \quad A \triangle B = B \triangle A
(Разность A∖BA \setminus B и декартово произведение A×BA \times B не коммутативны).

Примеры, свойства и пояснения:

{1}∪{2}={2}∪{1}={1,2}\{1\} \cup \{2\} = \{2\} \cup \{1\} = \{1, 2\}.

Коллоквиум 1 · Вопрос № 15

Свойство дистрибутивности

Операция ∗* называется дистрибутивной относительно операции ∘\circ, если:

A∗(B∘C)=(A∗B)∘(A∗C)A * (B \circ C) = (A * B) \circ (A * C)
В алгебре множеств справедлива взаимная дистрибутивность:

  1. Дистрибутивность ∩\cap относительно ∪\cup: A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C);
  2. Дистрибутивность ∪\cup относительно ∩\cap: A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C);
  3. Дистрибутивность ∩\cap относительно △\triangle: A∩(B△C)=(A∩B)△(A∩C)A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C).
Примеры, свойства и пояснения:

Аналог в арифметике: a⋅(b+c)=a⋅b+a⋅ca \cdot (b + c) = a \cdot b + a \cdot c.

Коллоквиум 1 · Вопрос № 16

Критерий равенства двух множеств (метод двух включений)

Два множества AA и BB равны тогда и только тогда, когда каждое из них является подмножеством другого:

A=B  ⟺  A⊆B∧B⊆AA = B \iff A \subseteq B \land B \subseteq A
Метод двух включений: для строгого доказательства равенства A=BA = B доказывают два утверждения:

  1. ∀x  (x∈A  ⟹  x∈B)\forall x \; (x \in A \implies x \in B), то есть A⊆BA \subseteq B;
  2. ∀x  (x∈B  ⟹  x∈A)\forall x \; (x \in B \implies x \in A), то есть B⊆AB \subseteq A.
Примеры, свойства и пояснения:

Доказательство равенства A∩(A∪B)=AA \cap (A \cup B) = A через проверку A∩(A∪B)⊆AA \cap (A \cup B) \subseteq A и A⊆A∩(A∪B)A \subseteq A \cap (A \cup B).

Коллоквиум 1 · Вопрос № 17

Равные множества (определение)

Два множества AA и BB называются равными (A=BA = B), если они состоят из одних и тех же элементов (аксиома объемности / экстенсиональности):

∀x  (x∈A  ⟺  x∈B)\forall x \; (x \in A \iff x \in B)
Порядок записи элементов и их повторы в множестве не имеют значения.

Примеры, свойства и пояснения:

{1,2,3}={3,1,2,2,1}\{1, 2, 3\} = \{3, 1, 2, 2, 1\}.

Коллоквиум 1 · Вопрос № 18

Свойство ассоциативности

Бинарная операция ∗* называется ассоциативной (сочетательной), если группировка скобок при последовательном применении операции не влияет на результат:

∀A,B,C((A∗B)∗C=A∗(B∗C))\forall A, B, C \quad ((A * B) * C = A * (B * C))
В алгебре множеств ассоциативны операции ∪\cup, ∩\cap и △\triangle:
(A∪B)∪C=A∪(B∪C),(A∩B)∩C=A∩(B∩C),(A△B)△C=A△(B△C)(A \cup B) \cup C = A \cup (B \cup C), \quad (A \cap B) \cap C = A \cap (B \cap C), \quad (A \triangle B) \triangle C = A \triangle (B \triangle C)

Примеры, свойства и пояснения:

({1}∪{2})∪{3}={1}∪({2}∪{3})={1,2,3}(\{1\} \cup \{2\}) \cup \{3\} = \{1\} \cup (\{2\} \cup \{3\}) = \{1, 2, 3\}.

Коллоквиум 1 · Вопрос № 19

Законы поглощения

Законы поглощения (Absorption laws) в алгебре множеств связывают операции объединения и пересечения:

  1. A∪(A∩B)=AA \cup (A \cap B) = A
  2. A∩(A∪B)=AA \cap (A \cup B) = A
    Множество AA «поглощает» выражение с пересечением или объединением.
Примеры, свойства и пояснения:

Если B={1,2,3}B = \{1, 2, 3\}, A={1}A = \{1\}, то A∩B={1}A \cap B = \{1\}, а A∪(A∩B)={1}∪{1}={1}=AA \cup (A \cap B) = \{1\} \cup \{1\} = \{1\} = A.

Коллоквиум 1 · Вопрос № 20

Законы склеивания

Законы склеивания (Consensus / Adjacency laws) объединяют множества, отличающиеся на один операнд и его дополнение:

  1. (A∩B)∪(A∩B‾)=A(A \cap B) \cup (A \cap \overline{B}) = A
  2. (A∪B)∩(A∪B‾)=A(A \cup B) \cap (A \cup \overline{B}) = A
    Являются теоретической основой минимизации булевых функций и метода Куайна.
Примеры, свойства и пояснения:

В логике: xy∨xy‾=x(y∨y‾)=x⋅1=xx y \lor x \overline{y} = x (y \lor \overline{y}) = x \cdot 1 = x.

Коллоквиум 1 · Вопрос № 21

Законы де Моргана

Законы двойственности Огастеса де Моргана связывают дополнение с операциями объединения и пересечения:

  1. Дополнение объединения равно пересечению дополнений:
    A∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B}
  2. Дополнение пересечения равно объединению дополнений:
    A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B}
    Для любого семейства подмножеств: ⋃iAi‾=⋂iAi‾\overline{\bigcup_i A_i} = \bigcap_i \overline{A_i} и ⋂iAi‾=⋃iAi‾\overline{\bigcap_i A_i} = \bigcup_i \overline{A_i}.
Примеры, свойства и пояснения:

Отрицание фразы «Иван сдал матанализ и программирование» означает: «Иван не сдал матанализ ИЛИ не сдал программирование».

Коллоквиум 1 · Вопрос № 22

Бинарное отношение на множествах

Бинарным отношением между множеством AA и множеством BB называется любое подмножество RR их декартова произведения:

R⊆A×BR \subseteq A \times B
Если (a,b)∈R(a, b) \in R, то говорят, что элемент aa находится в отношении RR с элементом bb, и пишут aRba R b. Если A=BA = B, то R⊆A×AR \subseteq A \times A называется бинарным отношением на множестве AA.

Примеры, свойства и пояснения:

На множестве R\mathbb{R}: отношение x<yx < y; на множестве Z\mathbb{Z}: отношение делимости a∣ba \mid b.

Коллоквиум 1 · Вопрос № 23

Способы задания бинарных отношений

Бинарное отношение R⊆A×BR \subseteq A \times B задается следующими эквивалентными способами:

  1. Списком пар (перечислением): R={(a1,b1),(a2,b2),… }R = \{(a_1, b_1), (a_2, b_2), \dots\};
  2. Характеристическим предикатом (формулой): (a,b)∈R  ⟺  P(a,b)(a, b) \in R \iff P(a, b) (например, a<ba < b);
  3. Матрицей отношения MR=(mij)M_R = (m_{ij}): mij=1m_{ij} = 1, если (ai,bj)∈R(a_i, b_j) \in R, и 00 иначе;
  4. Графом отношения: ориентированным графом на AA (где дуга a→ba \to b означает (a,b)∈R(a, b) \in R) или двудольным графом между AA и BB;
  5. Сечениями отношения: набором верхних R(a)={b∣(a,b)∈R}R(a) = \{b \mid (a, b) \in R\} или нижних R−1(b)R^{-1}(b) сечений.
Примеры, свойства и пояснения:

Отношение делимости на {1,2,3}\{1, 2, 3\}: пары {(1,1),(1,2),(1,3),(2,2),(3,3)}\{(1,1),(1,2),(1,3),(2,2),(3,3)\}.

Коллоквиум 1 · Вопрос № 24

Область определения отношения и область значений отношения

Для отношения R⊆A×BR \subseteq A \times B:

  • Областью определения (Domain) называется множество всех первых координат пар, входящих в RR:
    Dom(R)={a∈A∣∃b∈B:(a,b)∈R}\mathrm{Dom}(R) = \{ a \in A \mid \exists b \in B : (a, b) \in R \}
  • Областью значений (Range / Image) называется множество всех вторых координат пар, входящих в RR:
    Ran(R)={b∈B∣∃a∈A:(a,b)∈R}\mathrm{Ran}(R) = \{ b \in B \mid \exists a \in A : (a, b) \in R \}
Примеры, свойства и пояснения:

Для R={(1,x),(2,x)}R = \{(1, x), (2, x)\}: Dom(R)={1,2}\mathrm{Dom}(R) = \{1, 2\}, Ran(R)={x}\mathrm{Ran}(R) = \{x\}.

Коллоквиум 1 · Вопрос № 25

Обратное отношение

Обратным отношением к отношению R⊆A×BR \subseteq A \times B называется отношение R−1⊆B×AR^{-1} \subseteq B \times A, состоящее из тех же пар, но с обратным порядком компонент:

R−1={(b,a)∈B×A∣(a,b)∈R}R^{-1} = \{ (b, a) \in B \times A \mid (a, b) \in R \}
Матрица обратного отношения равна транспонированной матрице исходного: MR−1=(MR)TM_{R^{-1}} = (M_R)^T. В графе отношения обращение соответствует смене направления всех стрелок на противоположное.

Примеры, свойства и пояснения:

Для отношения «быть родителем» обратным является отношение «быть ребенком». Для отношения << обратным является >>.

Коллоквиум 1 · Вопрос № 26

Композиция отношений

Композицией (произведением) отношений R⊆A×BR \subseteq A \times B и S⊆B×CS \subseteq B \times C называется отношение R∘S⊆A×CR \circ S \subseteq A \times C (в обозначениях курса сначала применяется RR, затем SS):

R∘S={(a,c)∈A×C∣∃b∈B:((a,b)∈R∧(b,c)∈S)}R \circ S = \{ (a, c) \in A \times C \mid \exists b \in B : ((a, b) \in R \land (b, c) \in S) \}
Матрица композиции вычисляется как булево произведение матриц: MR∘S=MR⊙MSM_{R \circ S} = M_R \odot M_S.

Примеры, свойства и пояснения:

Если RR — «быть отцом», а SS — «быть братом», то R∘SR \circ S — «быть дядей со стороны отца».

Коллоквиум 1 · Вопрос № 27

Степень отношения

Для отношения RR на множестве AA (R⊆A×AR \subseteq A \times A) nn-я степень RnR^n определяется индуктивно через операцию композиции:

  1. R0=IA={(x,x)∣x∈A}R^0 = I_A = \{ (x, x) \mid x \in A \} — тождественное (диагональное) отношение;
  2. R1=RR^1 = R;
  3. Rn+1=Rn∘R=R∘RnR^{n+1} = R^n \circ R = R \circ R^n. Пара (a,b)∈Rn(a, b) \in R^n тогда и только тогда, когда в графе отношения существует маршрут длины nn из вершины aa в вершину bb.
Примеры, свойства и пояснения:

Если RR — «быть родителем», то R2R^2 — «быть дедушкой/бабушкой», R3R^3 — «быть прадедушкой/прабабушкой».

Коллоквиум 1 · Вопрос № 28

Теорема об ассоциативности композиции отношений (формулировка)

Теорема (Ассоциативность композиции отношений): Для любых трех бинарных отношений R⊆A×BR \subseteq A \times B, S⊆B×CS \subseteq B \times C и T⊆C×DT \subseteq C \times D операция композиции ассоциативна:

(R∘S)∘T=R∘(S∘T)(R \circ S) \circ T = R \circ (S \circ T)

Примеры, свойства и пояснения:

Доказывается через ассоциативность конъюнкции и существование промежуточных элементов b∈Bb \in B и c∈Cc \in C.

Коллоквиум 1 · Вопрос № 29

Симметричное отношение

Отношение RR на множестве AA называется симметричным, если для любых элементов выполнение отношения в одну сторону влечет его выполнение в обратную:

∀x,y∈A((x,y)∈R  ⟹  (y,x)∈R)\forall x, y \in A \quad ((x, y) \in R \implies (y, x) \in R)
Критерии: R=R−1R = R^{-1}; матрица симметрична (MR=MRTM_R = M_R^T); в ориентированном графе между любыми вершинами стрелки либо двусторонние, либо отсутствуют.

Примеры, свойства и пояснения:

Отношение равенства (==); отношение дружбы; отношение сравнимости по модулю mm.

Коллоквиум 1 · Вопрос № 30

Асимметричное отношение

Отношение RR на множестве AA называется асимметричным, если одновременное выполнение отношения в обе стороны невозможно ни для каких элементов:

∀x,y∈A((x,y)∈R  ⟹  (y,x)∉R)\forall x, y \in A \quad ((x, y) \in R \implies (y, x) \notin R)
Критерии: R∩R−1=∅R \cap R^{-1} = \varnothing; на главной диагонали матрицы только нули (антирефлексивность обязательна!); в графе нет ни петель, ни встречных дуг.

Примеры, свойства и пояснения:

Строгое неравенство x<yx < y; отношение «быть старше по возрасту».

Коллоквиум 1 · Вопрос № 31

Антисимметричное отношение

Отношение RR на множестве AA называется антисимметричным, если взаимное отношение возможно только для совпадающих элементов:

∀x,y∈A((x,y)∈R∧(y,x)∈R  ⟹  x=y)\forall x, y \in A \quad ((x, y) \in R \land (y, x) \in R \implies x = y)
Критерии: R∩R−1⊆IAR \cap R^{-1} \subseteq I_A; встречные дуги запрещены для различных вершин, но петли разрешены.

Примеры, свойства и пояснения:

Нестрогое неравенство x≤yx \le y; отношение включения подмножеств A⊆BA \subseteq B; отношение делимости a∣ba \mid b на N\mathbb{N}.

Коллоквиум 1 · Вопрос № 32

Несимметричное отношение

Отношение RR называется несимметричным, если оно не является симметричным, то есть найдется хотя бы одна пара элементов, для которой отношение выполняется только в одну сторону:

∃x,y∈A:((x,y)∈R∧(y,x)∉R)\exists x, y \in A : ((x, y) \in R \land (y, x) \notin R)
Несимметричность — это просто отрицание свойства симметричности (не путать с антисимметричностью и асимметричностью!).

Примеры, свойства и пояснения:

Отношение R={(1,2),(2,1),(2,3)}R = \{(1, 2), (2, 1), (2, 3)\} на {1,2,3}\{1, 2, 3\} является несимметричным из-за пары (2,3)(2, 3).

Коллоквиум 1 · Вопрос № 33

Рефлексивность

Отношение RR на множестве AA называется рефлексивным, если каждый элемент множества находится в отношении с самим собой:

∀x∈A((x,x)∈R)\forall x \in A \quad ((x, x) \in R)
Критерии: диагональ содержится в отношении (IA⊆RI_A \subseteq R); на главной диагонали матрицы все единицы; в графе отношения у каждой вершины есть петля.

Примеры, свойства и пояснения:

Отношение равенства x=xx = x; нестрогое неравенство x≤xx \le x; делимость a∣aa \mid a.

Коллоквиум 1 · Вопрос № 34

Антирефлексивность

Отношение RR на множестве AA называется антирефлексивным (иррефлексивным), если ни один элемент множества не находится в отношении с самим собой:

∀x∈A((x,x)∉R)\forall x \in A \quad ((x, x) \notin R)
Критерии: отношение не пересекается с диагональю (R∩IA=∅R \cap I_A = \varnothing); на главной диагонали матрицы все нули; в графе отношения нет ни одной петли.

Примеры, свойства и пояснения:

Строгое неравенство x<xx < x (ложно для всех xx); отношение перпендикулярности прямых.

Коллоквиум 1 · Вопрос № 35

Нерефлексивность

Отношение RR на множестве AA называется нерефлексивным, если оно не является рефлексивным, то есть существует хотя бы один элемент, не связанный отношением с самим собой:

∃x∈A:((x,x)∉R)\exists x \in A : ((x, x) \notin R)
Это логическое отрицание рефлексивности. Нерефлексивное отношение может содержать петли у одних вершин и не иметь у других.

Примеры, свойства и пояснения:

Отношение с матрицей (1000)\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} на {1,2}\{1, 2\} нерефлексивно, но не антирефлексивно.

Коллоквиум 1 · Вопрос № 36

Транзитивное отношение

Отношение RR на множестве AA называется транзитивным, если из связи xx с yy и yy с zz обязательно следует связь xx с zz:

∀x,y,z∈A((x,y)∈R∧(y,z)∈R  ⟹  (x,z)∈R)\forall x, y, z \in A \quad ((x, y) \in R \land (y, z) \in R \implies (x, z) \in R)
Критерии: R2⊆RR^2 \subseteq R; для любого пути длины 2 в графе существует замыкающая прямая дуга.

Примеры, свойства и пояснения:

Отношения <<, ≤\le, ==, ⊆\subseteq, делимость a∣ba \mid b.

Коллоквиум 1 · Вопрос № 37

Антитранзитивное отношение

Отношение RR на множестве AA называется антитранзитивным, если наличие двух звеньев цепочки категорически запрещает замыкающую хорду:

∀x,y,z∈A((x,y)∈R∧(y,z)∈R  ⟹  (x,z)∉R)\forall x, y, z \in A \quad ((x, y) \in R \land (y, z) \in R \implies (x, z) \notin R)
Критерий: R2∩R=∅R^2 \cap R = \varnothing. В графе ни для какого пути длины 2 нет замыкающего ребра.

Примеры, свойства и пояснения:

Отношение «быть отцом»: если xx отец yy, а yy отец zz, то xx не может быть отцом zz (он дедушка).

Коллоквиум 1 · Вопрос № 38

Нетранзитивность

Отношение RR называется нетранзитивным, если оно не является транзитивным, то есть найдется хотя бы одна цепочка из двух пар, для которой замыкающая пара отсутствует в отношении:

∃x,y,z∈A:((x,y)∈R∧(y,z)∈R∧(x,z)∉R)\exists x, y, z \in A : ((x, y) \in R \land (y, z) \in R \land (x, z) \notin R)
Это логическое отрицание транзитивности.

Примеры, свойства и пояснения:

Отношение знакомства людей: если AA знает BB, а BB знает CC, то AA не обязательно знает CC.

Коллоквиум 1 · Вопрос № 39

Замыкание отношения относительно свойства

Замыканием отношения RR относительно заданного свойства PP называется наименьшее (по включению) отношение RP⊇RR_P \supseteq R, обладающее этим свойством. Основные типы замыканий:

  1. Рефлексивное замыкание: r(R)=R∪IAr(R) = R \cup I_A;
  2. Симметричное замыкание: s(R)=R∪R−1s(R) = R \cup R^{-1};
  3. Транзитивное замыкание: t(R)=⋃k=1nRkt(R) = \bigcup_{k=1}^n R^k (вычисляется алгоритмом Уоршелла за O(n3)O(n^3)).
Примеры, свойства и пояснения:

Рефлексивное замыкание строгого порядка << дает нестрогий порядок ≤\le.

Коллоквиум 1 · Вопрос № 40

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

Бинарное отношение ∼\sim на множестве AA называется отношением эквивалентности, если оно одновременно удовлетворяет трем аксиомам:

  1. Рефлексивность: ∀x∈A  (x∼x)\forall x \in A \; (x \sim x);
  2. Симметричность: ∀x,y∈A  (x∼y  ⟹  y∼x)\forall x, y \in A \; (x \sim y \implies y \sim x);
  3. Транзитивность: ∀x,y,z∈A  (x∼y∧y∼z  ⟹  x∼z)\forall x, y, z \in A \; (x \sim y \land y \sim z \implies x \sim z).
Примеры, свойства и пояснения:

Равенство (==); сравнимость по модулю mm: a≡b(modm)a \equiv b \pmod m; отношение параллельности прямых.

Коллоквиум 1 · Вопрос № 41

Класс эквивалентности

Классом эквивалентности элемента a∈Aa \in A по отношению ∼\sim называется множество всех элементов множества AA, находящихся в отношении эквивалентности с элементом aa:

[a]={x∈A∣x∼a}[a] = \{ x \in A \mid x \sim a \}
Свойства:

  1. Непустота: a∈[a]a \in [a];
  2. a∼b  ⟺  [a]=[b]a \sim b \iff [a] = [b];
  3. [a]∩[b]≠∅  ⟺  [a]=[b][a] \cap [b] \ne \varnothing \iff [a] = [b] (классы либо не пересекаются, либо совпадают).
Примеры, свойства и пояснения:

Для вычетов по модулю 3: [1]={…,−5,−2,1,4,7,… }[1] = \{\dots, -5, -2, 1, 4, 7, \dots\}.

Коллоквиум 1 · Вопрос № 42

Порождающий элемент

Порождающим элементом (представителем / representative) класса эквивалентности [a][a] называется любой элемент aa, принадлежащий данному классу. Поскольку x∼y  ⟺  [x]=[y]x \sim y \iff [x] = [y], в качестве порождающего элемента можно выбрать любой элемент этого класса: если b∈[a]b \in [a], то [b]=[a][b] = [a], и bb также является порождающим элементом этого же класса.

Примеры, свойства и пояснения:

В классе четных чисел [0][0] порождающим элементом может служить 0, 2, 4 или любое другое четное число.

Коллоквиум 1 · Вопрос № 43

Разбиение множества

Разбиением множества AA называется семейство непустых попарно непересекающихся подмножеств {Ai}i∈I\{A_i\}_{i \in I} (блоков разбиения), объединение которых дает все множество AA:

  1. ∀i∈I:Ai≠∅\forall i \in I : A_i \ne \varnothing (блоки непусты);
  2. ∀i≠j:Ai∩Aj=∅\forall i \ne j : A_i \cap A_j = \varnothing (блоки попарно не пересекаются);
  3. ⋃i∈IAi=A\bigcup_{i \in I} A_i = A (блоки покрывают AA).
Примеры, свойства и пояснения:

Разбиение Z\mathbb{Z} на четные и нечетные числа: {Zчет,Zнечет}\{\mathbb{Z}_{\text{чет}}, \mathbb{Z}_{\text{нечет}}\}.

Коллоквиум 1 · Вопрос № 44

Теорема про разбиение и классы эквивалентности

Фундаментальная теорема об эквивалентностях и разбиениях: Между множеством всех отношений эквивалентности на множестве AA и множеством всех его разбиений существует взаимно-однозначное соответствие (биекция):

  1. Всякое отношение эквивалентности ∼\sim порождает разбиение A/∼={[a]∣a∈A}A / \sim = \{ [a] \mid a \in A \} (фактор-множество);
  2. Всякое разбиение {Ai}\{A_i\} порождает отношение эквивалентности: a∼b  ⟺  ∃i:(a∈Ai∧b∈Ai)a \sim b \iff \exists i : (a \in A_i \land b \in A_i). Число разбиений nn-элементного множества равно числу Белла BnB_n.
Примеры, свойства и пояснения:

Для множества из 3 элементов число разбиений B3=5B_3 = 5.

Коллоквиум 1 · Вопрос № 45

Отношения строгого и нестрогого частичного порядка

  1. Нестрогий частичный порядок (обозначается ≤\le): отношение, являющееся рефлексивным, антисимметричным и транзитивным.
  2. Строгий частичный порядок (обозначается <<): отношение, являющееся антирефлексивным, асимметричным и транзитивным. Связь между ними: x<y  ⟺  (x≤y∧x≠y)x < y \iff (x \le y \land x \ne y); x≤y  ⟺  (x<y∨x=y)x \le y \iff (x < y \lor x = y).
Примеры, свойства и пояснения:

Нестрогий: ⊆\subseteq на подмножествах; строгий: ⊂\subset (строгое включение).

Коллоквиум 1 · Вопрос № 46

Отношения строгого и нестрогого линейного порядка

Порядок называется линейным (полным), если любые два элемента множества сравнимы между собой:

  1. Нестрогий линейный порядок: нестрогий частичный порядок, удовлетворяющий условию линейности:
    ∀x,y∈A(x≤y∨y≤x)\forall x, y \in A \quad (x \le y \lor y \le x)
  2. Строгий линейный порядок: строгий частичный порядок, удовлетворяющий условию трихотомии:
    ∀x,y∈A(x<y∨x=y∨y<x)\forall x, y \in A \quad (x < y \lor x = y \lor y < x)
Примеры, свойства и пояснения:

Стандартное отношение ≤\le на R\mathbb{R} — линейный порядок; отношение делимости a∣ba \mid b — частичный, но не линейный (2 и 3 несравнимы).

Коллоквиум 1 · Вопрос № 47

Отношение соответствия

Соответствием между множествами AA и BB называется тройка Γ=(A,B,G)\Gamma = (A, B, G), где AA — область отправления, BB — область прибытия, а G⊆A×BG \subseteq A \times B — график соответствия. Понятие соответствия обобщает бинарное отношение явным указанием несущих множеств AA и BB.

Примеры, свойства и пояснения:

Соответствие между студентами и сданными ими экзаменами.

Коллоквиум 1 · Вопрос № 48

Линейно упорядоченное множество

Линейно упорядоченным множеством (цепью / chain) называется частично упорядоченное множество (P,≤)(P, \le), на котором отношение порядка является линейным, то есть любые два элемента сравнимы (x≤yx \le y или y≤xy \le x). Диаграмма Хассе линейно упорядоченного множества представляет собой вертикальную неветвящуюся цепочку.

Примеры, свойства и пояснения:

(N,≤)(\mathbb{N}, \le), алфавитный порядок слов в словаре.

Коллоквиум 1 · Вопрос № 49

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

Частично упорядоченным множеством (ЧУМ / Poset — Partially Ordered Set) называется пара (P,≤)(P, \le), состоящая из непустого множества PP и заданного на нем отношения нестрогого частичного порядка ≤\le (рефлексивного, антисимметричного и транзитивного).

Примеры, свойства и пояснения:

Булеан P(X)\mathcal{P}(X) с отношением включения ⊆\subseteq; делители числа 12 с отношением делимости.

Коллоквиум 1 · Вопрос № 50

Функциональное отношение

Бинарное отношение f⊆A×Bf \subseteq A \times B называется функциональным отношением (однозначным), если каждому элементу a∈Aa \in A сопоставляется не более одного элемента b∈Bb \in B:

∀a∈A,∀b1,b2∈B((a,b1)∈f∧(a,b2)∈f  ⟹  b1=b2)\forall a \in A, \forall b_1, b_2 \in B \quad ((a, b_1) \in f \land (a, b_2) \in f \implies b_1 = b_2)
Если к тому же область определения совпадает со всем AA (Dom(f)=A\mathrm{Dom}(f) = A), то ff называется всюду определенной функцией (отображением) f:A→Bf: A \to B.

Примеры, свойства и пояснения:

f(x)=x2f(x) = x^2 — функциональное отношение; отношение x2+y2=1x^2 + y^2 = 1 не функционально (одному xx соответствуют два yy).

Коллоквиум 1 · Вопрос № 51

Недопределенная функция

Недоопределенной (частичной) функцией (Partial function) называется функциональное отношение f⊆A×Bf \subseteq A \times B, область определения которого строго меньше AA:

Dom(f)⊊A\mathrm{Dom}(f) \subsetneq A
То есть существуют аргументы a∈Aa \in A, для которых значение функции не определено.

Примеры, свойства и пояснения:

Функция f(x)=1xf(x) = \frac{1}{x} на множестве действительных чисел R\mathbb{R} (не определена в точке x=0x = 0).

Коллоквиум 1 · Вопрос № 52

Какими свойствами обладает отношение, когда нельзя определить свойство симметричности однозначно?

Такая ситуация возникает в двух ключевых случаях:

  1. Пустое отношение R=∅R = \varnothing на непустом множестве AA: условие симметричности выполняется тривиально в силу ложности посылки ((x,y)∈∅  ⟹  …(x, y) \in \varnothing \implies \dots истинно), поэтому пустое отношение формально симметрично, но одновременно оно же является асимметричным и антисимметричным.
  2. Отношение не является ни симметричным, ни асимметричным, ни антисимметричным: в нем присутствуют как пары со встречными стрелками для различных элементов (что нарушает асимметричность и антисимметричность), так и односторонние пары без пары-партнера (что нарушает симметричность). Такое отношение называется несимметричным.
Примеры, свойства и пояснения:

Отношение R={(1,2),(2,1),(2,3)}R = \{(1, 2), (2, 1), (2, 3)\} на {1,2,3}\{1, 2, 3\}.

Коллоквиум 1 · Вопрос № 53

Какими свойствами обладает отношение, когда нельзя определить свойство транзитивности однозначно?

  1. Пустое отношение R=∅R = \varnothing и отношение без путей длины 2: условие транзитивности выполняется тривиально из-за отсутствия пар вида (x,y)∧(y,z)(x, y) \land (y, z), поэтому отношение формально транзитивно, но одновременно и антитранзитивно.
  2. Нетранзитивное отношение, не являющееся антитранзитивным: в отношении присутствуют пути длины 2, замыкаемые прямой хордой (транзитивные тройки), и одновременно присутствуют пути длины 2, для которых замыкающей хорды нет. Такое отношение называется нетранзитивным (оно не является ни транзитивным, ни антитранзитивным в чистом виде).
Примеры, свойства и пояснения:

Отношение R={(1,2),(2,3),(1,3),(2,4),(4,5)}R = \{(1, 2), (2, 3), (1, 3), (2, 4), (4, 5)\}: для цепочки 1→2→31 \to 2 \to 3 хорда (1,3)(1, 3) есть, а для 2→4→52 \to 4 \to 5 хорды (2,5)(2, 5) нет.

Коллоквиум 2 · Вопрос № 1

Определение высказывания

Высказыванием (Proposition) в математической логике называется повествовательное предложение, в отношении которого можно однозначно и объективно утверждать, истинно оно (1\mathbf{1} или True\mathrm{True}) или ложно (0\mathbf{0} или False\mathrm{False}), но не то и другое одновременно (закон исключенного третьего и закон непротиворечия).

Примеры, свойства и пояснения:

«Число 7 — простое» (истинное высказывание); «2+2=52 + 2 = 5» (ложное высказывание). Вопросительные и побудительные фразы («Который час?») высказываниями не являются.

Коллоквиум 2 · Вопрос № 2

Арность операции (функции)

Арностью (местностью) операции или функции называется количество входных аргументов (операндов), которые она принимает на вход:

  • 0-арная (нуллиарная) операция — константа (0,10, 1);
  • 1-арная (унарная) операция — принимает один аргумент (например, отрицание ¬x\neg x);
  • 2-арная (бинарная) операция — принимает два аргумента (x∧yx \land y, x∨yx \lor y, x⊕yx \oplus y);
  • 3-арная (тернарная) операция — функция трех переменных (например, функция большинства Maj(x,y,z)\mathrm{Maj}(x, y, z));
  • nn-арная операция — функция от nn аргументов: f:Bn→Bf: B^n \to B.
Примеры, свойства и пояснения:

Отрицание x‾\overline{x} имеет арность 1; импликация x  ⟹  yx \implies y имеет арность 2.

Коллоквиум 2 · Вопрос № 3

Булева алгебра (определение + аксиомы/законы только перечислить)

Булевой алгеброй называется непустое множество BB с двумя бинарными операциями ∨\lor (дизъюнкция / сложение) и ∧\land (конъюнкция / умножение), одной унарной операцией x‾\overline{x} (дополнение / отрицание) и двумя выделенными константами 00 и 11, удовлетворяющее следующим фундаментальным аксиомам:

  1. Коммутативность: x∨y=y∨xx \lor y = y \lor x и x∧y=y∧xx \land y = y \land x;
  2. Ассоциативность: (x∨y)∨z=x∨(y∨z)(x \lor y) \lor z = x \lor (y \lor z) и (x∧y)∧z=x∧(y∧z)(x \land y) \land z = x \land (y \land z);
  3. Дистрибутивность: x∧(y∨z)=(x∧y)∨(x∧z)x \land (y \lor z) = (x \land y) \lor (x \land z) и x∨(y∧z)=(x∨y)∧(x∨z)x \lor (y \land z) = (x \lor y) \land (x \lor z);
  4. Нейтральные элементы (свойства 0 и 1): x∨0=xx \lor 0 = x и x∧1=xx \land 1 = x;
  5. Законы дополнения: x∨x‾=1x \lor \overline{x} = 1 и x∧x‾=0x \land \overline{x} = 0. Дополнительные законы: идемпотентность (x∨x=xx \lor x = x), поглощение (x∨(x∧y)=xx \lor (x \land y) = x), законы де Моргана.
Примеры, свойства и пояснения:

Двухэлементная булева алгебра ({0,1},∨,∧,¬,0,1)(\{0, 1\}, \lor, \land, \neg, 0, 1); алгебра подмножеств (P(U),∪,∩,A‾,∅,U)(\mathcal{P}(U), \cup, \cap, \overline{\phantom{A}}, \varnothing, U).

Коллоквиум 2 · Вопрос № 4

Булево множество

Булевым множеством (булевым носителем) называется двухэлементное множество истинностных значений: B={0,1}B = \{0, 1\}, где 00 кодирует «Ложь» (False), а 11 — «Истину» (True). Множество Bn={0,1}nB^n = \{0, 1\}^n всех двоичных кортежей длины nn называется nn-мерным булевым кубом или пространством булевых аргументов.

Примеры, свойства и пояснения:

B2={(0,0),(0,1),(1,0),(1,1)}B^2 = \{(0,0), (0,1), (1,0), (1,1)\} — булев квадрат мощности 22=42^2 = 4.

Коллоквиум 2 · Вопрос № 5

Закон единственности дополнения

Теорема о единственности дополнения: В любой булевой алгебре для каждого элемента xx существует ровно один элемент yy, удовлетворяющий аксиомам дополнения: x∨y=1x \lor y = 1 и x∧y=0x \land y = 0. Этот единственный элемент называется дополнением (отрицанием) элемента xx и обозначается x‾\overline{x} или ¬x\neg x.

Примеры, свойства и пояснения:

Если yy и zz удовлетворяют свойствам дополнения для xx, то y=y∧1=y∧(x∨z)=(y∧x)∨(y∧z)=0∨(y∧z)=(x∧z)∨(y∧z)=(x∨y)∧z=1∧z=zy = y \land 1 = y \land (x \lor z) = (y \land x) \lor (y \land z) = 0 \lor (y \land z) = (x \land z) \lor (y \land z) = (x \lor y) \land z = 1 \land z = z.

Коллоквиум 2 · Вопрос № 6

Закон инволюции

Закон инволюции (двойного отрицания): Двукратное применение операции отрицания возвращает исходный элемент:

x‾‾=x\overline{\overline{x}} = x
Операция отрицания является инволютивным автоморфизмом булевой алгебры.

Примеры, свойства и пояснения:

¬(¬1)=¬0=1\neg(\neg 1) = \neg 0 = 1.

Коллоквиум 2 · Вопрос № 7

Теорема склеивания

Теорема (закон) склеивания: Для любой элементарной конъюнкции AA и переменной xx справедливы тождества:

  1. ДНФ-форма:
    A⋅x∨A⋅x‾=AA \cdot x \lor A \cdot \overline{x} = A
  2. КНФ-форма:
    (A∨x)∧(A∨x‾)=A(A \lor x) \land (A \lor \overline{x}) = A
    Доказательство: Ax∨Ax‾=A(x∨x‾)=A⋅1=AA x \lor A \overline{x} = A (x \lor \overline{x}) = A \cdot 1 = A. Теорема позволяет устранить переменную xx, входящую в два слагаемых в прямой и инверсной форме.
Примеры, свойства и пояснения:

xyz∨xy‾z=xz(y∨y‾)=xzx y z \lor x \overline{y} z = x z (y \lor \overline{y}) = x z.

Коллоквиум 2 · Вопрос № 8

В чем отличие функции и формулы?

  • Булева функция — это абстрактное математическое отображение f:{0,1}n→{0,1}f: \{0, 1\}^n \to \{0, 1\}, задающее закон соответствия между входными двоичными наборами и выходным битом. Функция однозначно фиксируется своей таблицей истинности (вектором значений).
  • Булева формула — это синтаксическая символьная запись (слово в формальном алфавите из переменных, связок и скобок), представляющая и реализующая некоторую функцию.
  • Различие: одна и та же функция может быть задана бесконечным множеством различных формул (например, формулы x∨yx \lor y, x‾∧y‾‾\overline{\overline{x} \land \overline{y}} и x⊕y⊕xyx \oplus y \oplus xy синтаксически различны, но задают одну и ту же функцию дизъюнкции).
Примеры, свойства и пояснения:

Функция тождественного нуля может быть записана формулами 00, x∧x‾x \land \overline{x}, x⊕xx \oplus x.

Коллоквиум 2 · Вопрос № 9

Число булевых функций $n$ аргументов

Число всевозможных различных булевых функций от nn переменных равно:

N(n)=22nN(n) = 2^{2^n}
Обоснование: nn двоичных переменных образуют 2n2^n различных наборов (длина таблицы истинности). На каждом из 2n2^n наборов функция может независимо принимать значение 0 или 1, что дает 22n2^{2^n} комбинаций.

Примеры, свойства и пояснения:

Для n=0n=0: 220=21=22^{2^0} = 2^1 = 2 (константы 0 и 1); для n=1n=1: 221=42^{2^1} = 4; для n=2n=2: 222=162^{2^2} = 16; для n=3n=3: 28=2562^8 = 256.

Коллоквиум 2 · Вопрос № 10

ДНФ

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция (логическое ИЛИ) одной или нескольких элементарных конъюнкций:

K1∨K2∨⋯∨KmK_1 \lor K_2 \lor \dots \lor K_m
где каждая элементарная конъюнкция Kj=x~j1∧⋯∧x~jrK_j = \tilde{x}_{j_1} \land \dots \land \tilde{x}_{j_r} — это произведение переменных, взятых с отрицанием или без него, причем в пределах одной конъюнкции ни одна переменная не повторяется.

Примеры, свойства и пояснения:

xy∨x‾z∨yz‾x y \lor \overline{x} z \lor y \overline{z} — корректная ДНФ.

Коллоквиум 2 · Вопрос № 11

КНФ

Конъюнктивной нормальной формой (КНФ) называется конъюнкция (логическое И) одной или нескольких элементарных дизъюнкций:

D1∧D2∧⋯∧DmD_1 \land D_2 \land \dots \land D_m
где каждая элементарная дизъюнкция Dj=x~j1∨⋯∨x~jrD_j = \tilde{x}_{j_1} \lor \dots \lor \tilde{x}_{j_r} — это сумма переменных с отрицанием или без него, без повторения одной и той же переменной.

Примеры, свойства и пояснения:

(x∨y‾)∧(x‾∨z)∧(y∨z‾)(x \lor \overline{y}) \land (\overline{x} \lor z) \land (y \lor \overline{z}) — корректная КНФ.

Коллоквиум 2 · Вопрос № 12

Минтерм

Минтермом (конституентой единицы) от nn переменных называется элементарная конъюнкция всех nn переменных, взятых с отрицанием или без него:

mα~(x1,…,xn)=x1α1∧x2α2∧⋯∧xnαnm_{\tilde{\alpha}}(x_1, \dots, x_n) = x_1^{\alpha_1} \land x_2^{\alpha_2} \land \dots \land x_n^{\alpha_n}
где x1=xx^1 = x, x0=x‾x^0 = \overline{x}. Ключевое свойство: минтерм обращается в 11 ровно на одном наборе аргументов α~=(α1,…,αn)\tilde{\alpha} = (\alpha_1, \dots, \alpha_n) и равен 00 на всех остальных 2n−12^n - 1 наборах.

Примеры, свойства и пояснения:

Для набора (1,0,1)(1, 0, 1) минтерм равен xy‾zx \overline{y} z.

Коллоквиум 2 · Вопрос № 13

СДНФ

Совершенной дизъюнктивной нормальной формой (СДНФ) функции ff называется ДНФ, удовлетворяющая требованиям:

  1. Каждое слагаемое является минтермом от всех nn переменных функции;
  2. Все минтермы попарно различны;
  3. Формула представляет собой дизъюнкцию минтермов, соответствующих всем тем наборам, на которых функция принимает значение 1:
    f(x1,…,xn)=⋁α~:f(α~)=1mα~(x1,…,xn)f(x_1, \dots, x_n) = \bigvee_{\tilde{\alpha}: f(\tilde{\alpha}) = 1} m_{\tilde{\alpha}}(x_1, \dots, x_n)
    СДНФ существует и единственна для любой булевой функции, не равной тождественному 0.
Примеры, свойства и пояснения:

Для x⊕yx \oplus y: наборы (0,1)(0, 1) и (1,0)(1, 0) дают СДНФ x‾y∨xy‾\overline{x} y \lor x \overline{y}.

Коллоквиум 2 · Вопрос № 14

Импликанта

Элементарная конъюнкция KK называется импликантой булевой функции ff (K≤fK \le f или K  ⟹  fK \implies f), если на любом двоичном наборе, на котором K=1K = 1, значение функции ff также обязательно равно 11. Иными словами, множество единиц конъюнкции является подмножеством единиц функции: NK⊆NfN_K \subseteq N_f.

Примеры, свойства и пояснения:

Минтерм xyx y является импликантой функции дизъюнкции x∨yx \lor y, так как xy  ⟹  (x∨y)x y \implies (x \lor y).

Коллоквиум 2 · Вопрос № 15

Простая импликанта

Простой импликантой (Prime Implicant) функции ff называется такая её импликанта PP, никакая собственная часть которой уже не является импликантой функции ff. Иными словами, удаление хотя бы одной переменной из конъюнкции PP превращает её в конъюнкцию, принимающую 1 на некотором нулевом наборе функции ff. Геометрически простая импликанта соответствует максимальному по размеру подкубу единиц функции.

Примеры, свойства и пояснения:

Для f=xy∨xy‾f = x y \lor x \overline{y}: конъюнкция xyx y — импликанта, но не простая, так как xx тоже импликанта. Конъюнкция xx — простая импликанта.

Коллоквиум 2 · Вопрос № 16

Число импликант функции

Общее число всех возможных импликант функции ff равно числу всех элементарных конъюнкций (включая конъюнкции разного ранга от 1 до nn), покрывающих только единичные наборы функции. Оно не превосходит общего числа всех конъюнкций 3n−13^n - 1 и зависит от геометрии единичных наборов функции.

Примеры, свойства и пояснения:

Для тождественной единицы f≡1f \equiv 1 любая конъюнкция является импликантой (всего 3n3^n импликант); для тождественного нуля импликант нет.

Коллоквиум 2 · Вопрос № 17

Минимизация булевой формулы. Методы минимизации

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

  1. Графический метод карт Карно (до 5–6 переменных);
  2. Аналитический метод склеивания и поглощения Куайна;
  3. Алгоритмический табличный метод Куайна–Мак-Класки (для ЭВМ);
  4. Метод Петрика (нахождение всех минимальных покрытий через КНФ).
Примеры, свойства и пояснения:

СДНФ xyz∨xyz‾x y z \lor x y \overline{z} минимизируется в xyx y.

Коллоквиум 2 · Вопрос № 18

Сокращенная ДНФ

Сокращенной ДНФ называется дизъюнкция всех простых импликант булевой функции ff:

Dсокр=⋁P∈PI(f)PD_{\text{сокр}} = \bigvee_{P \in \mathrm{PI}(f)} P
Получается из СДНФ последовательным применением всех возможных операций склеивания Ax∨Ax‾=AAx \lor A\overline{x} = A и законов поглощения A∨AB=AA \lor AB = A. Сокращенная ДНФ единственна для каждой функции.

Примеры, свойства и пояснения:

Для f=xy∨xy‾∨x‾yf = x y \lor x \overline{y} \lor \overline{x} y простые импликанты xx и yy, сокращенная ДНФ равна x∨yx \lor y.

Коллоквиум 2 · Вопрос № 19

Тупиковая ДНФ

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

Примеры, свойства и пояснения:

У функции может существовать несколько различных тупиковых ДНФ.

Коллоквиум 2 · Вопрос № 20

Минимальная ДНФ

Минимальной ДНФ (МДНФ) называется тупиковая ДНФ, содержащая наименьшее возможное суммарное число вхождений переменных (букв). Если несколько тупиковых ДНФ имеют одинаковое наименьшее число букв, все они считаются минимальными. Все ядровые простые импликанты обязаны входить в любую МДНФ.

Примеры, свойства и пояснения:

МДНФ функции дизъюнкции: x∨yx \lor y (2 буквы против 6 букв в СДНФ x‾y∨xy‾∨xy\overline{x}y \lor x\overline{y} \lor xy).

Коллоквиум 2 · Вопрос № 21

Макстерм

Макстермом (конституентой нуля) от nn переменных называется элементарная дизъюнкция всех nn переменных, взятых с отрицанием или без него:

Mα~(x1,…,xn)=x1α‾1∨x2α‾2∨⋯∨xnα‾nM_{\tilde{\alpha}}(x_1, \dots, x_n) = x_1^{\overline{\alpha}_1} \lor x_2^{\overline{\alpha}_2} \lor \dots \lor x_n^{\overline{\alpha}_n}
где переменная берется с отрицанием, если в наборе стоит 1, и без отрицания, если стоит 0. Ключевое свойство: макстерм обращается в 00 ровно на одном наборе α~\tilde{\alpha} и равен 11 на всех остальных наборах.

Примеры, свойства и пояснения:

Для нулевого набора (0,1,0)(0, 1, 0) макстерм равен x∨y‾∨zx \lor \overline{y} \lor z.

Коллоквиум 2 · Вопрос № 22

СКНФ

Совершенной конъюнктивной нормальной формой (СКНФ) функции ff называется КНФ, представляющая собой конъюнкцию макстермов по всем нулевым наборам функции:

f(x1,…,xn)=⋀α~:f(α~)=0Mα~(x1,…,xn)f(x_1, \dots, x_n) = \bigwedge_{\tilde{\alpha}: f(\tilde{\alpha}) = 0} M_{\tilde{\alpha}}(x_1, \dots, x_n)
СКНФ существует и единственна для любой булевой функции, не равной тождественной единице.

Примеры, свойства и пояснения:

Для функции импликации x  ⟹  yx \implies y (нуль на наборе (1,0)(1, 0)): СКНФ состоит из единственного макстерма x‾∨y\overline{x} \lor y.

Коллоквиум 2 · Вопрос № 23

Теорема разложения для ДНФ/КНФ

Теорема Шеннона о разложении: Любая булева функция f(x1,…,xn)f(x_1, \dots, x_n) по любой переменной xix_i представима в виде:

  1. ДНФ-разложение:
    f(x1,…,xn)=(xi‾∧f(x1,…,0,…,xn))∨(xi∧f(x1,…,1,…,xn))f(x_1, \dots, x_n) = (\overline{x_i} \land f(x_1, \dots, 0, \dots, x_n)) \lor (x_i \land f(x_1, \dots, 1, \dots, x_n))
  2. КНФ-разложение (двойственное):
    f(x1,…,xn)=(xi∨f(x1,…,0,…,xn))∧(xi‾∨f(x1,…,1,…,xn))f(x_1, \dots, x_n) = (x_i \lor f(x_1, \dots, 0, \dots, x_n)) \land (\overline{x_i} \lor f(x_1, \dots, 1, \dots, x_n))
    При последовательном разложении по всем nn переменным ДНФ-разложение дает СДНФ, а КНФ-разложение дает СКНФ.
Примеры, свойства и пояснения:

Для f(x,y)f(x, y): f(x,y)=x‾f(0,y)∨xf(1,y)f(x, y) = \overline{x} f(0, y) \lor x f(1, y).

Коллоквиум 2 · Вопрос № 24

Полином Жегалкина. Методы построения

Полиномом Жегалкина называется представление булевой функции в виде суммы по модулю 2 (⊕\oplus) элементарных конъюнкций неповторяющихся переменных над полем F2\mathbb{F}_2:

P(x1,…,xn)=⨁(α1,…,αn)cα1…αnx1α1…xnαn,cα~∈{0,1}P(x_1, \dots, x_n) = \bigoplus_{(\alpha_1, \dots, \alpha_n)} c_{\alpha_1 \dots \alpha_n} x_1^{\alpha_1} \dots x_n^{\alpha_n}, \quad c_{\tilde{\alpha}} \in \{0, 1\}
По теореме Жегалкина такое представление существует и единственно. Методы построения:

  1. Метод эквивалентных преобразований (замена x‾=x⊕1\overline{x} = x \oplus 1, x∨y=x⊕y⊕xyx \lor y = x \oplus y \oplus xy);
  2. Метод треугольника Паскаля (быстрое преобразование Мёбиуса за O(n2n)O(n 2^n));
  3. Метод неопределенных коэффициентов (решение системы линейных уравнений над F2\mathbb{F}_2).
Примеры, свойства и пояснения:

x  ⟹  y=xy⊕x⊕1x \implies y = x y \oplus x \oplus 1.

Коллоквиум 2 · Вопрос № 25

Суперпозиция функций

Суперпозицией функций из множества FF называется функция, полученная с помощью конечного числа операций:

  1. Подстановки одной функции из FF вместо аргумента другой функции из FF;
  2. Отождествления (склеивания) переменных;
  3. Переименования аргументов. Суперпозиция моделирует соединение логических вентилей в комбинационную схему без обратных связей.
Примеры, свойства и пояснения:

Если f(x,y)=x∨yf(x, y) = x \lor y и g(x)=¬xg(x) = \neg x, то f(g(x),y)=¬x∨yf(g(x), y) = \neg x \lor y — суперпозиция.

Коллоквиум 2 · Вопрос № 26

Подстановка функции $g$ в функцию $f$

Операция подстановки функции g(y1,…,ym)g(y_1, \dots, y_m) на место ii-й переменной функции f(x1,…,xn)f(x_1, \dots, x_n) порождает новую функцию от n+m−1n + m - 1 переменных:

h(x1,…,xi−1,y1,…,ym,xi+1,…,xn)=f(x1,…,g(y1,…,ym),…,xn)h(x_1, \dots, x_{i-1}, y_1, \dots, y_m, x_{i+1}, \dots, x_n) = f(x_1, \dots, g(y_1, \dots, y_m), \dots, x_n)
Значение hh вычисляется вычислением результата gg и передачей его на вход ff.

Примеры, свойства и пояснения:

Подстановка g(x,y)=x∧yg(x, y) = x \land y в f(z)=z‾f(z) = \overline{z} дает h(x,y)=x∧y‾h(x, y) = \overline{x \land y} (штрих Шеффера).

Коллоквиум 2 · Вопрос № 27

Отождествление переменных в функции $f$

Операция отождествления переменных заключается в подаче одной и той же переменной на два или более различных входа функции f(x1,…,xn)f(x_1, \dots, x_n), например замена переменной xjx_j на xix_i (j≠ij \ne i):

h(x1,…,xj−1,xj+1,…,xn)=f(x1,…,xi,…,xi,…,xn)h(x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n) = f(x_1, \dots, x_i, \dots, x_i, \dots, x_n)
Число существенных аргументов функции при этом уменьшается.

Примеры, свойства и пояснения:

Отождествление переменных в штрихе Шеффера f(x,x)=x∧x‾=x‾f(x, x) = \overline{x \land x} = \overline{x} дает инвертор (НЕ).

Коллоквиум 2 · Вопрос № 28

Замкнутое множество функций

Множество булевых функций F⊆P2F \subseteq P_2 называется замкнутым классом, если оно совпадает со своим замыканием относительно операции суперпозиции:

[F]=F[F] = F
То есть любая суперпозиция функций из FF снова принадлежит множеству FF.

Примеры, свойства и пояснения:

Класс всех линейных функций LL; класс монотонных функций MM.

Коллоквиум 2 · Вопрос № 29

Замыкание множества функций

Замыканием множества функций FF (обозначается [F][F]) называется множество всех возможных булевых функций, которые могут быть получены из функций множества FF с помощью конечного числа суперпозиций. Свойства замыкания:

  1. Экстенсивность: F⊆[F]F \subseteq [F];
  2. Идемпотентность: [[F]]=[F][[F]] = [F];
  3. Монотонность: F1⊆F2  ⟹  [F1]⊆[F2]F_1 \subseteq F_2 \implies [F_1] \subseteq [F_2].
Примеры, свойства и пояснения:

[{∧,¬}]=P2[\{\land, \neg\}] = P_2 (замыкание совпадает со всеми булевыми функциями).

Коллоквиум 2 · Вопрос № 30

Полная система функций

Система булевых функций F⊆P2F \subseteq P_2 называется функционально полной, если её замыкание совпадает со множеством всех булевых функций:

[F]=P2[F] = P_2
Это означает, что абсолютно любая булева функция может быть представлена формулой через функции системы FF.

Примеры, свойства и пояснения:

{∧,∨,¬}\{\land, \lor, \neg\}, {∧,¬}\{\land, \neg\}, {∨,¬}\{\lor, \neg\}, {⊕,∧,1}\{\oplus, \land, 1\}, {∣}\{\mid\}.

Коллоквиум 2 · Вопрос № 31

Безызбыточная полная система функций / Избыточная полная система функций

  • Безызбыточной полной системой функций (базисом) называется функционально полная система функций FF, удаление любой функции из которой делает оставшуюся систему неполной: ∀f∈F  ⟹  [F∖{f}]≠P2\forall f \in F \implies [F \setminus \{f\}] \ne P_2.
  • Избыточной полной системой называется полная система, содержащая хотя бы одну «лишнюю» функцию, удаление которой сохраняет функциональную полноту.
Примеры, свойства и пояснения:

Базисы: {∧,¬}\{\land, \neg\}, {∣}\{\mid\}; избыточная система: {∧,∨,¬}\{\land, \lor, \neg\} (дизъюнкция выражается через ∧\land и ¬\neg по де Моргану).

Коллоквиум 2 · Вопрос № 32

Самодвойственная функция. Число самодвойственных функций $n$ аргументов

Самодвойственной функцией (f∈Sf \in S) называется функция, совпадающая со своей двойственной функцией: f=f∗=f(x‾1,…,x‾n)‾f = f^* = \overline{f(\overline{x}_1, \dots, \overline{x}_n)}. На противоположных наборах аргументов самодвойственная функция принимает противоположные значения:

f(α~‾)=f(α~)‾f(\overline{\tilde{\alpha}}) = \overline{f(\tilde{\alpha})}
Число самодвойственных функций от nn аргументов равно:
∣S(n)∣=22n−1|S(n)| = 2^{2^{n-1}}
(Значения функции на первой половине куба определяют вторую половину однозначно).

Примеры, свойства и пояснения:

Функция x‾\overline{x}; функция большинства Maj(x,y,z)=xy∨yz∨xz\mathrm{Maj}(x, y, z) = xy \lor yz \lor xz. Для n=2n=2: 221=42^{2^1} = 4 функции.

Коллоквиум 2 · Вопрос № 33

Линейная функция. Число линейных функций $n$ аргументов

Линейной функцией (f∈Lf \in L) называется булева функция, полином Жегалкина которой имеет степень не выше 1 (не содержит произведений переменных):

f(x1,…,xn)=c0⊕c1x1⊕c2x2⊕⋯⊕cnxn,ci∈{0,1}f(x_1, \dots, x_n) = c_0 \oplus c_1 x_1 \oplus c_2 x_2 \oplus \dots \oplus c_n x_n, \quad c_i \in \{0, 1\}
Число линейных функций от nn аргументов равно:
∣L(n)∣=2n+1|L(n)| = 2^{n+1}
(Каждый из n+1n+1 коэффициентов c0,…,cnc_0, \dots, c_n выбирается независимо).

Примеры, свойства и пояснения:

x⊕yx \oplus y, x⊕y⊕1x \oplus y \oplus 1. Для n=3n=3: 23+1=162^{3+1} = 16 линейных функций.

Коллоквиум 2 · Вопрос № 34

Монотонная функция

Функция ff называется монотонной (f∈Mf \in M), если на любых двух сравнимых наборах значение функции не убывает:

α~≤β~  ⟹  f(α~)≤f(β~)\tilde{\alpha} \le \tilde{\beta} \implies f(\tilde{\alpha}) \le f(\tilde{\beta})
где (α1,…,αn)≤(β1,…,βn)  ⟺  ∀i  (αi≤βi)(\alpha_1, \dots, \alpha_n) \le (\beta_1, \dots, \beta_n) \iff \forall i \; (\alpha_i \le \beta_i). Критерий: В сокращенной ДНФ монотонной функции нет ни одного знака отрицания.

Примеры, свойства и пояснения:

Константы 0,10, 1; селекторы xix_i; x∧yx \land y; x∨yx \lor y. Отрицание x‾∉M\overline{x} \notin M.

Коллоквиум 2 · Вопрос № 35

Сравнимые наборы

Два двоичных набора α~=(α1,…,αn)\tilde{\alpha} = (\alpha_1, \dots, \alpha_n) и β~=(β1,…,βn)\tilde{\beta} = (\beta_1, \dots, \beta_n) называются сравнимыми (в естественном частичном порядке булева куба), если либо α~≤β~\tilde{\alpha} \le \tilde{\beta}, либо β~≤α~\tilde{\beta} \le \tilde{\alpha}. Условие α~≤β~\tilde{\alpha} \le \tilde{\beta} означает, что для всех разрядов αi≤βi\alpha_i \le \beta_i (i=1,…,ni = 1, \dots, n). Если в одном разряде αi<βi\alpha_i < \beta_i, а в другом αj>βj\alpha_j > \beta_j, наборы называются несравнимыми.

Примеры, свойства и пояснения:

(0,0,1)≤(0,1,1)(0, 0, 1) \le (0, 1, 1) — сравнимы; (0,1)(0, 1) и (1,0)(1, 0) — несравнимы.

Коллоквиум 2 · Вопрос № 36

Функции, сохраняющая константу. Число таких функций $n$ аргументов

  1. Класс T0T_0 (сохраняющие 0): f(0,0,…,0)=0f(0, 0, \dots, 0) = 0. Число таких функций: ∣T0(n)∣=22n−1|T_0(n)| = 2^{2^n - 1};
  2. Класс T1T_1 (сохраняющие 1): f(1,1,…,1)=1f(1, 1, \dots, 1) = 1. Число таких функций: ∣T1(n)∣=22n−1|T_1(n)| = 2^{2^n - 1}. Значение на одном наборе строго зафиксировано, на остальных 2n−12^n - 1 наборах значение функции произвольно.
Примеры, свойства и пояснения:

x∧y∈T0∩T1x \land y \in T_0 \cap T_1; x‾∉T0\overline{x} \notin T_0, x‾∉T1\overline{x} \notin T_1.

Коллоквиум 2 · Вопрос № 37

Формулировка критерия Поста

Теорема Эмиля Поста о функциональной полноте (1941 г.): Система булевых функций F⊆P2F \subseteq P_2 является функционально полной тогда и только тогда, когда она не содержится целиком ни в одном из 5 предполных классов Поста:

[F]=P2  ⟺  {F⊈T0F⊈T1F⊈SF⊈MF⊈L[F] = P_2 \iff \begin{cases} F \not\subseteq T_0 \\ F \not\subseteq T_1 \\ F \not\subseteq S \\ F \not\subseteq M \\ F \not\subseteq L \end{cases}
В таблице Поста для системы FF в каждом из пяти столбцов должен быть хотя бы один знак «−-».

Примеры, свойства и пояснения:

Для проверки полноты строится таблица 5 столбцов (T0,T1,S,M,LT_0, T_1, S, M, L) и проверяется наличие минуса в каждом столбце.

Коллоквиум 2 · Вопрос № 38

Перечислить полные системы из одной функции

Функция, образующая одноэлементный базис, называется шефферовой. Она обязана не принадлежать ни одному из пяти классов Поста (f∉T0,T1,S,M,Lf \notin T_0, T_1, S, M, L). Среди бинарных функций (n=2n = 2) существует ровно две шефферовых функции:

  1. Штрих Шеффера (И-НЕ, NAND): x∣y=x∧y‾x \mid y = \overline{x \land y};
  2. Стрелка Пирса (ИЛИ-НЕ, NOR): x↓y=x∨y‾x \downarrow y = \overline{x \lor y}.
Примеры, свойства и пояснения:

Через штрих Шеффера: x‾=x∣x\overline{x} = x \mid x; x∧y=(x∣y)∣(x∣y)x \land y = (x \mid y) \mid (x \mid y).

Коллоквиум 2 · Вопрос № 39

Частично определенная (недоопределенная) функция

Частично определенной (недоопределенной) булевой функцией называется логическая функция, значения которой заданы не на всех 2n2^n наборах аргументов, а лишь на некотором подмножестве D⊂{0,1}nD \subset \{0, 1\}^n. На остальных наборах функция принимает неопределенное значение (обозначаемое ×\times, dd или «don't care»). При аппаратном синтезе такие состояния доопределяют нулями или единицами так, чтобы получить максимальные группы склеивания на карте Карно.

Примеры, свойства и пояснения:

Функция дешифратора десятичных цифр 8421 BCD (комбинации 1010–1111 являются неопределенными).

Коллоквиум 2 · Вопрос № 40

Кодирование

Кодированием называется процесс однозначного сопоставления каждому символу исходного первичного алфавита A={a1,…,an}A = \{a_1, \dots, a_n\} некоторого слова (кодового слова) c(ai)c(a_i) в кодирующем алфавите B={b1,…,bd}B = \{b_1, \dots, b_d\} (чаще всего в двоичном алфавите B={0,1}B = \{0, 1\}):

c:A→B+c: A \to B^+

Примеры, свойства и пояснения:

Кодирование символов таблицы ASCII 8-битными двоичными числами.

Коллоквиум 2 · Вопрос № 41

Однозначно декодируемый код

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

∀S1,S2∈A∗(S1≠S2  ⟹  c(S1)≠c(S2))\forall S_1, S_2 \in A^* \quad (S_1 \ne S_2 \implies c(S_1) \ne c(S_2))
Это гарантирует возможность безошибочного восстановления исходного сообщения без разделителей.

Примеры, свойства и пояснения:

Код {a→0,b→10}\{a \to 0, b \to 10\} однозначно декодируем; код {a→0,b→00}\{a \to 0, b \to 00\} неоднозначен (цепочка 00 декодируется как aaaa или bb).

Коллоквиум 2 · Вопрос № 42

Равномерный код

Код называется равномерным (кодом фиксированной длины), если все кодовые слова имеют одинаковую длину: ℓ1=ℓ2=⋯=ℓn=ℓ\ell_1 = \ell_2 = \dots = \ell_n = \ell. Минимальная длина равномерного кода для алфавита из nn символов при основании кодирования dd равна ℓ=⌈log⁡dn⌉\ell = \lceil \log_d n \rceil. Любой равномерный код со всеми различными словами однозначно декодируем.

Примеры, свойства и пояснения:

5-битный телеграфный код Бодо; 8-битный код байта; 16-битный код UTF-16.

Коллоквиум 2 · Вопрос № 43

Энтропия сообщения

Энтропией Шеннона дискретного источника информации с распределением вероятностей символов P=(p1,…,pn)P = (p_1, \dots, p_n) называется математическое ожидание собственной информации на один передаваемый символ:

H(X)=−∑i=1npilog⁡2piH(X) = -\sum_{i=1}^n p_i \log_2 p_i
Она измеряет среднюю степень неопределенности источника и задает фундаментальный предел минимальной средней длины кода без потерь (первая теорема Шеннона).

Примеры, свойства и пояснения:

Для равновероятных исходов монеты: H(X)=−(0.5log⁡20.5+0.5log⁡20.5)=1H(X) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 бит.

Коллоквиум 2 · Вопрос № 44

Неравенство Крафта-Макмиллана

Теорема Крафта–Макмиллана: Для существования однозначно декодируемого (и префиксного) кода с длинами кодовых слов ℓ1,ℓ2,…,ℓn\ell_1, \ell_2, \dots, \ell_n в dd-ичном алфавите необходимо и достаточно, чтобы выполнялось неравенство:

∑i=1nd−ℓi≤1\sum_{i=1}^n d^{-\ell_i} \le 1
Для двоичного алфавита (d=2d = 2): ∑i=1n2−ℓi≤1\sum_{i=1}^n 2^{-\ell_i} \le 1.

Примеры, свойства и пояснения:

Длины {1,2,3,3}\{1, 2, 3, 3\}: 2−1+2−2+2−3+2−3=1/2+1/4+1/8+1/8=1≤12^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 1/2 + 1/4 + 1/8 + 1/8 = 1 \le 1 (код существует).

Коллоквиум 2 · Вопрос № 45

Префиксная / суффиксная схема

  • Префиксная схема (условие Фано): никакое кодовое слово не является началом (префиксом) другого кодового слова: ∀i≠j\forall i \ne j c(ai)c(a_i) не префикс c(aj)c(a_j). Префиксный код декодируется мгновенно слева направо без задержки.
  • Суффиксная схема: никакое кодовое слово не является концом (суффиксом) другого кодового слова. Суффиксный код декодируется мгновенно справа налево (с конца строки).
Примеры, свойства и пояснения:

{0,10,110,111}\{0, 10, 110, 111\} — префиксная схема.

Коллоквиум 2 · Вопрос № 46

Избыточность схемы алфавитного кодирования

Избыточностью схемы кодирования называется разность между средней длиной кодового слова LL и теоретическим энтропийным пределом источника H(X)H(X):

R=L−H(X)log⁡2dR = L - \frac{H(X)}{\log_2 d}
Она показывает, сколько «лишних» битов в среднем тратится на передачу одного символа сверх абсолютного информационного минимума.

Примеры, свойства и пояснения:

Если L=1.6L = 1.6 бита, а H(X)=1.4H(X) = 1.4 бита, то избыточность R=0.2R = 0.2 бита/символ.

Коллоквиум 2 · Вопрос № 47

Формула подсчета избыточности схемы

Формула абсолютной избыточности двоичного кода:

R=∑i=1npiℓi−(−∑i=1npilog⁡2pi)=∑i=1npi(ℓi+log⁡2pi)R = \sum_{i=1}^n p_i \ell_i - \left( -\sum_{i=1}^n p_i \log_2 p_i \right) = \sum_{i=1}^n p_i \left( \ell_i + \log_2 p_i \right)
Относительная избыточность: r=RL=1−H(X)Lr = \frac{R}{L} = 1 - \frac{H(X)}{L}. Избыточность обращается в 00 тогда и только тогда, когда все длины идеальны: ℓi=−log⁡2pi\ell_i = -\log_2 p_i.

Примеры, свойства и пояснения:

Для диадических вероятностей {1/2,1/4,1/4}\{1/2, 1/4, 1/4\} с длинами {1,2,2}\{1, 2, 2\} избыточность R=1.5−1.5=0R = 1.5 - 1.5 = 0.

Коллоквиум 2 · Вопрос № 48

Код Хаффмана

Код Хаффмана (1952 г.) — оптимальный префиксный код переменной длины с минимальной средней длиной кодового слова LL. Алгоритм построения (снизу вверх):

  1. Создается список узлов для каждого символа с весом, равным его вероятности;
  2. На каждом шаге выбираются два узла с наименьшими весами и объединяются в новый родительский узел с суммарным весом;
  3. Процесс повторяется, пока не останется один корневой узел;
  4. Ветвям дерева приписываются символы 0 и 1, кодовое слово читается от корня к листу.
Примеры, свойства и пояснения:

Широко применяется в форматах сжатия JPEG, MP3, GZIP, DEFLATE.

Коллоквиум 2 · Вопрос № 49

Код Шеннона - Фано

Код Шеннона–Фано (1949 г.) — эвристический префиксный код переменной длины. Алгоритм построения (сверху вниз):

  1. Символы упорядочиваются по невозрастанию вероятностей: p1≥p2≥⋯≥pnp_1 \ge p_2 \ge \dots \ge p_n;
  2. Массив делится на две непрерывные части так, чтобы сумма вероятностей в них была максимально близкой;
  3. Первой группе приписывается бит 0, второй — бит 1;
  4. Процедура рекурсивно повторяется для каждой группы, пока группа не сократится до 1 символа. Отличие: код Шеннона–Фано субоптимален и может уступать коду Хаффмана.
Примеры, свойства и пояснения:

Для вероятностей {0.4,0.3,0.2,0.1}\{0.4, 0.3, 0.2, 0.1\} деление на {0.4}\{0.4\} и {0.3,0.2,0.1}\{0.3, 0.2, 0.1\}.

Коллоквиум 2 · Вопрос № 50

Арифметическое кодирование

Арифметическое кодирование — метод энтропийного сжатия, кодирующий всю строку сообщения целиком в виде одного вещественного числа (подынтервала) из отрезка [0,1)[0, 1). Каждому символу соответствует пропорциональное сужение текущего подотрезка в соответствии с его вероятностью. Финальный подотрезок записывается минимальным двоичным числом. Преимущество: преодолевает барьер в 1 бит/символ кода Хаффмана, позволяя выделять дробное число бит на символ.

Примеры, свойства и пояснения:

Используется в видеокодеках H.264/AVC (CABAC), JPEG 2000.

Коллоквиум 2 · Вопрос № 51

Расстояние Хэмминга

Расстоянием Хэмминга d(x,y)d(x, y) между двумя двоичными векторами x,y∈{0,1}nx, y \in \{0, 1\}^n одинаковой длины называется количество разрядов (позиций), в которых эти векторы отличаются друг от друга:

d(x,y)=w(x⊕y)=∣{i∣xi≠yi}∣d(x, y) = w(x \oplus y) = |\{ i \mid x_i \ne y_i \}|
где w(v)w(v) — вес Хэмминга (число единиц). Является метрикой (удовлетворяет аксиомам неотрицательности, симметрии и неравенству треугольника).

Примеры, свойства и пояснения:

d((1,0,1,1),(1,1,1,0))=2d((1, 0, 1, 1), (1, 1, 1, 0)) = 2.

Коллоквиум 2 · Вопрос № 52

Код Хэмминга

Код Хэмминга — семейство линейных блоковых кодов с минимальным кодовым расстоянием dmin⁡=3d_{\min} = 3, исправляющих любую одиночную ошибку (t=1t = 1). Длина блока n=2r−1n = 2^r - 1, число проверочных бит rr, число информационных бит k=2r−1−rk = 2^r - 1 - r. Классический код Хэмминга (7,4)(7, 4) (r=3r = 3):

  • Информационные биты размещаются на позициях 3, 5, 6, 7;
  • Проверочные биты размещаются на степенях двойки: 1, 2, 4.
Примеры, свойства и пояснения:

Код Хэмминга (7,4)(7, 4), (15,11)(15, 11), (31,26)(31, 26).

Коллоквиум 2 · Вопрос № 53

Принцип поиска и исправление ошибок в коде Хэмминга

Исправление ошибок основано на синдромном декодировании:

  1. На приемной стороне по проверочной матрице HH вычисляется вектор синдрома S=y⋅HT=(sr…s2s1)2S = y \cdot H^T = (s_r \dots s_2 s_1)_2;
  2. Если S=0002S = 000_2, принятое слово корректно (ошибок нет);
  3. Если S≠0S \ne 0, двоичное число SS в точности равно номеру ошибочного бита в кодовом слове;
  4. Для исправления ошибки найденный бит просто инвертируется: yS←yS⊕1y_S \leftarrow y_S \oplus 1. Добавление общего бита четности формирует расширенный код SECDED (8,4)(8, 4) с dmin⁡=4d_{\min}=4, способный исправлять 1 ошибку и обнаруживать 2 ошибки.
Примеры, свойства и пояснения:

Если синдром равен (1,0,1)2=5(1, 0, 1)_2 = 5, произошла инверсия 5-го бита; инвертируем его и восстанавливаем данные.

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.