Экзамен

Булевы функции

1. Булевы функции: определение. Количество булевых функций от n переменных. Способы задания булевых функций.

Определение: Булевой функцией (или функцией алгебры логики) от $n$ переменных называется функция $f(x_1,x_2,\dots ,x_n)$, где аргументы $x_i$ и само значение функции принимают значения из множества $\{0,1\}$. Отображение $f:\{0,1{\}}^n\to \{0,1\}$.

Количество булевых функций: Количество различных булевых функций от $n$ переменных равно $2^{2^n}$.

• Для $n=1$: $2^{2^1}=4$ функции.
• Для $n=2$: $2^{2^2}=16$ функций.

Способы задания:

1. Таблица истинности: Перечисление всех $2^n$ наборов значений аргументов и соответствующих им значений функции.
2. Аналитический (формульный): Задание функции с помощью формулы, использующей логические операции (например, $f=x\wedge (y\vee \bar{z})$).
3. Векторный: Задание функции вектором значений (последний столбец таблицы истинности), при фиксированном порядке наборов.
4. Графический: Использование карт Карно, диаграмм Эйлера-Венна или булева куба.
5. Числовой: Задание номеров наборов (в десятичной системе), на которых функция принимает значение 1 (или 0).

2. Таблица истинности (ТИ) булевой функции.

Таблица истинности — это табличное представление булевой функции, в котором для каждого из $2^n$ возможных наборов значений переменных указано соответствующее значение функции.

Структура:

• Входные столбцы ($x_1,\dots ,x_n$): Содержат все возможные комбинации 0 и 1. Обычно наборы упорядочиваются лексикографически (как двоичные числа от 0 до $2^n-1$).
• Выходной столбец ($f$): Содержит значения функции на этих наборах.

Пример (для функции $f=x\wedge y$):

| x | y | f(x,y) | | --- | --- | ------ | | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

3. Основные функции: дизъюнкция, конъюнкция, импликация, эквивалентность, сложение по модулю два, стрелка Пирса, штрих Шеффера.

1. Конъюнкция (Логическое И, AND, $x\wedge y$, $x\cdot y$): Равна 1 тогда и только тогда, когда оба аргумента равны 1.

2. Дизъюнкция (Логическое ИЛИ, OR, $x\vee y$): Равна 0 тогда и только тогда, когда оба аргумента равны 0.

3. Импликация (Следование, $x\to y$): Равна 0 тогда и только тогда, когда $x=1$ (посылка истинна), а $y=0$ (следствие ложно).

4. Эквивалентность (Равносильность, $x\leftrightarrow y$, $x\sim y$): Равна 1, если значения аргументов совпадают ($00$ или $11$).

5. Сложение по модулю 2 (Исключающее ИЛИ, XOR, $x\oplus y$): Равна 1, если значения аргументов различны ($01$ или $10$).

6. Штрих Шеффера (И-НЕ, NAND, $x|y$): Отрицание конъюнкции: $x|y=\overline{x\wedge y}$. Равна 0 только при $11$.

7. Стрелка Пирса (ИЛИ-НЕ, NOR, $x\downarrow y$): Отрицание дизъюнкции: $x\downarrow y=\overline{x\vee y}$. Равна 1 только при $00$.

4. Булев куб. Развертка булева куба. Поиск функции по развертке.

Булев куб ($B^n$): Геометрическая модель множества всех наборов значений $n$ переменных. Вершины куба соответствуют наборам из 0 и 1. Две вершины соединены ребром, если соответствующие наборы отличаются значением ровно одной координаты (расстояние Хэмминга = 1).

• $n=1$: Отрезок (вершины 0 и 1).
• $n=2$: Квадрат (вершины 00, 01, 10, 11).
• $n=3$: Трехмерный куб.

Развертка булева куба: Представление $n$-мерного куба на плоскости в виде графа или специальной диаграммы, сохраняющей отношение соседства вершин. Для $n=3$ и $n=4$ часто используется диаграмма, аналогичная карте Карно, где соседние клетки соответствуют соседним вершинам куба.

Поиск функции по развертке: Значения функции (0 или 1) приписываются соответствующим вершинам куба. Это позволяет визуализировать структуру функции, находить интервалы (склейки) и минимизировать функцию геометрическим методом.

5. Сравнимые и несравнимые наборы. Доминирующий набор.

Сравнимые наборы: Наборы $\alpha =({\alpha }_1,\dots ,{\alpha }_n)$ и $\beta =({\beta }_1,\dots ,{\beta }_n)$ называются сравнимыми, если для всех $i$ выполняется ${\alpha }_i\le {\beta }_i$ (обозначается $\alpha \le \beta$) или для всех $i$ выполняется ${\beta }_i\le {\alpha }_i$ ($\beta \le \alpha$).

• Пример: $(0,1,0)\le (1,1,0)$.

Несравнимые наборы: Наборы, для которых не выполняется ни одно из условий сравнения.

• Пример: $(0,1)$ и $(1,0)$.

Доминирующий набор: В контексте пары $(\alpha ,\beta )$, если $\alpha \le \beta$ и $\alpha \ne \beta$, то набор $\beta$ доминирует над $\alpha$ (или $\alpha$ предшествует $\beta$).

6. Существенные и фиктивные переменные: определение и способы нахождения.

Фиктивная переменная: Переменная $x_i$ называется фиктивной для функции $f$, если значение функции не зависит от изменения этой переменной при любых значениях остальных переменных. Формально: $f(x_1,\dots ,0,\dots ,x_n)=f(x_1,\dots ,1,\dots ,x_n)$ для всех наборов остальных аргументов.

Существенная переменная: Переменная, которая не является фиктивной. То есть существует хотя бы один набор значений остальных переменных, при котором изменение $x_i$ меняет значение функции.

Способы нахождения:

1. По таблице истинности: Сравнивать пары строк, где меняется только исследуемая переменная. Если значения функции в таких парах всегда совпадают — переменная фиктивная. Если есть хоть одно различие — существенная.
2. Аналитический: Привести формулу к СДНФ или полиному Жегалкина. Если переменная входит в минимальную форму или полином — она существенная (с оговорками для некоторых форм, но для полинома Жегалкина это критерий).
3. Метод остаточных функций: Разложить функцию по переменной: $f={\bar{x}}_{i}f(x_i=0)\vee x_{i}f(x_i=1)$. Если $f(x_i=0)\equiv f(x_i=1)$, то $x_i$ фиктивна.

7. Основные равносильности: коммутативность, ассоциативность, дистрибутивность, законы де Моргана, формулы с константами.

1. Коммутативность: $x\wedge y=y\wedge x$ $x\vee y=y\vee x$

2. Ассоциативность: $x\wedge (y\wedge z)=(x\wedge y)\wedge z$ $x\vee (y\vee z)=(x\vee y)\vee z$

3. Дистрибутивность: $x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$ $x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$ (специфично для булевой алгебры)

4. Законы де Моргана (правила отрицания): $\overline{x\wedge y}=\bar{x}\vee \bar{y}$ $\overline{x\vee y}=\bar{x}\wedge \bar{y}$

5. Действия с константами и идемпотентность: $x\vee 0=x$; $x\vee 1=1$; $x\vee x=x$; $x\vee \bar{x}=1$ $x\wedge 1=x$; $x\wedge 0=0$; $x\wedge x=x$; $x\wedge \bar{x}=0$ $\overline{\bar{x}}=x$ (двойное отрицание)

8. ДНФ, КНФ, СДНФ, СКНФ. Способы приведения функции к СДНФ, СКНФ.

ДНФ (Дизъюнктивная нормальная форма): Дизъюнкция элементарных конъюнкций (произведений). Пример: $xy\vee \bar{z}$. КНФ (Конъюнктивная нормальная форма): Конъюнкция элементарных дизъюнкций (сумм). Пример: $(x\vee y)(\bar{z}\vee x)$.

СДНФ (Совершенная ДНФ): ДНФ, в которой каждая конъюнкция содержит все $n$ переменных (в прямом или инверсном виде), и все слагаемые различны. СКНФ (Совершенная КНФ): КНФ, в которой каждая дизъюнкция содержит все $n$ переменных, и все множители различны.

Способы приведения к СДНФ/СКНФ:

1. По таблице истинности:
   • СДНФ: Выбираем наборы, где $f=1$. Для каждого набора записываем конъюнкцию (если $x_i=1$, пишем $x_i$, если $0$, пишем ${\bar{x}}_i$). Все конъюнкции соединяем $\vee$.
   • СКНФ: Выбираем наборы, где $f=0$. Для каждого набора записываем дизъюнкцию (если $x_i=0$, пишем $x_i$, если $1$, пишем ${\bar{x}}_i$). Все дизъюнкции соединяем $\wedge$.
2. Равносильные преобразования:
   • Привести к ДНФ/КНФ.
   • Дополнить недостающие переменные, используя законы: $A=A\wedge (x\vee \bar{x})$ для СДНФ и $A=A\vee (x\wedge \bar{x})$ для СКНФ.
   • Раскрыть скобки и удалить повторы.

9. Карты Карно. Склейка на карте Карно.

Карта Карно — графический способ представления булевой функции в виде таблицы, где ячейки расположены так, что соседние (по стороне) ячейки соответствуют наборам, различающимся только в одном разряде (код Грея).

• Левый и правый края, а также верхний и нижний считаются соседними (тор).

Склейка: Процесс объединения соседних ячеек с единицами (для ДНФ) в прямоугольные блоки размером $2^k$ (1, 2, 4, 8, 16 клеток).

• Каждый блок соответствует элементарной конъюнкции (импликанте), из которой исключаются переменные, меняющие свое значение внутри блока.
• Цель: покрыть все единицы минимальным количеством максимально больших блоков.

10. Ранг конъюнкции. Длина ДНФ.

Ранг элементарной конъюнкции: Количество литералов (переменных или их отрицаний), входящих в эту конъюнкцию.

• Пример: ранг $x_1{\bar{x}}_2{x}_3$ равен 3.

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

• Иногда под сложностью ДНФ понимают суммарное количество литералов во всех конъюнкциях.

11. Минимальные, кратчайшие, сокращенные и тупиковые ДНФ.

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

12. Ядро булевой функции.

Ядро — это совокупность тех простых импликант, которые обязательно должны входить в любую тупиковую (и, следовательно, минимальную) ДНФ функции.

• Импликанта входит в ядро, если она покрывает хотя бы одну единицу функции, которую не покрывает ни одна другая простая импликанта.

13. Что такое функция Патрика.

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

• После раскрытия скобок и упрощения, кратчайший терм в ДНФ функции Патрика укажет на набор импликант для минимального покрытия.

14. Алгоритм нахождения МДНФ и КрДНФ.

1. Получение сокращенной ДНФ: Найти все простые импликанты функции (методом склеивания/Блейка/карт Карно).
2. Построение импликантной матрицы: Строки — простые импликанты, столбцы — конституенты единицы (наборы, где $f=1$).
3. Выделение ядра: Найти столбцы с единственной меткой. Соответствующие импликанты образуют ядро и обязательно включаются в МДНФ.
4. Покрытие оставшихся единиц: Для единиц, не покрытых ядром, выбрать минимальный набор оставшихся импликант, обеспечивающий покрытие (можно использовать метод Петрика или перебор).
5. Выбор лучшего варианта: Из полученных тупиковых форм выбрать ту, что имеет минимальную сложность (для МДНФ) или длину (для КрДНФ).

15. Импликантная матрица. Порядок построения импликантной матрицы.

Импликантная матрица (таблица покрытий): Таблица, используемая для выбора минимального покрытия. Порядок построения:

1. Столбцы матрицы помечаются всеми конституентами единицы (наборами из СДНФ) данной функции.
2. Строки матрицы помечаются всеми простыми импликантами (из сокращенной ДНФ).
3. В ячейке $(i,j)$ ставится метка (крестик/единица), если $i$-я импликанта покрывает $j$-ю конституенту (то есть конституента является частью интервала импликанты).

16. Нахождение ядра булевой функции с помощью импликантной матрицы.

1. В построенной импликантной матрице ищем столбцы, в которых стоит ровно одна метка.
2. Импликанты, соответствующие строкам, где находятся эти единственные метки, являются ядровыми.
3. Они “спасают” соответствующие конституенты, которые больше никем не покрываются.

17. Полиномиальная нормальная форма (ПНФ) и СПНФ. Положительно поляризованный и отрицательно поляризованный полином.

ПНФ: Представление функции в виде суммы по модулю 2 конъюнкций переменных. (Аналог ДНФ, но с $\oplus$ вместо $\vee$ и без отрицаний над всем выражением). Полином Жегалкина — это ПНФ, где переменные входят без отрицаний.

Поляризованный полином: Обобщение, где каждая переменная $x_i$ входит либо только как $x_i$ (положительная поляризация), либо только как ${\bar{x}}_i$ (отрицательная поляризация) во всем полиноме.

• СПНФ (Совершенная ПНФ): Обычно синоним полинома Жегалкина (канонический полином), который существует и единственен для любой функции.

18. Полином Жегалкина. Способы построения полинома Жегалкина.

Полином Жегалкина: Сумма по модулю 2 элементарных конъюнкций над множеством переменных $\{x_1,\dots ,x_n\}$ без инверсий. $f=a_0\oplus a_1{x}_1\oplus \cdots \oplus a_{12}{x}_1{x}_2\oplus \dots$

Способы построения:

1. Метод неопределенных коэффициентов: Записать общий вид полинома, подставить наборы значений переменных и решить систему линейных уравнений над полем GF(2).
2. Преобразование ДНФ: Заменить $\vee$ на формулу $A\vee B=A\oplus B\oplus AB$, $\bar{x}=x\oplus 1$, раскрыть скобки и привести подобные ($x\oplus x=0$). Если ДНФ состоит из непересекающихся слагаемых (ОДНФ), то $\vee$ просто заменяется на $\oplus$.
3. Метод треугольника (Паскаля): По вектору значений функции строится треугольник сумм по модулю 2. Левая боковая грань треугольника дает коэффициенты полинома.

19. Свойства булевых функций (Классы Поста). Полное множество булевых функций. Критерий Поста.

Классы Поста (Замкнутые классы):

1. $T_0$ — функции, сохраняющие 0 ($f(0,\dots ,0)=0$).
2. $T_1$ — функции, сохраняющие 1 ($f(1,\dots ,1)=1$).
3. $S$ — самодвойственные функции ($f({\bar{x}}_1,\dots ,{\bar{x}}_n)=\overline{f(x_1,\dots ,x_n)}$).
4. $M$ — монотонные функции (если $\alpha \le \beta$, то $f(\alpha )\le f(\beta )$).
5. $L$ — линейные функции (представимы полиномом Жегалкина 1-й степени: $a_0\oplus a_1{x}_1\oplus \dots$).

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

Критерий Поста: Система булевых функций полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти предполных классов ($T_0,T_1,S,M,L$). То есть в системе должна быть:

• хотя бы одна функция не из $T_0$,
• хотя бы одна не из $T_1$,
• одна не из $S$,
• одна не из $M$,
• одна не из $L$.

Теория графов

1. Шесть способов представления графа. Дать определения всем используемым понятиям и привести примеры.

1. Графический: Изображение вершин точками, ребер линиями.
2. Множественный: Пара множеств $G=(V,E)$, где $V$ — вершины, $E$ — список пар вершин (ребер).
3. Матрица смежности: Квадратная матрица $n\times n$, где $a_{ij}=1$, если есть ребро $(i,j)$, иначе 0.
4. Матрица инцидентности: Матрица $n\times m$ (вершины $\times$ ребра). Для неориентированного графа: 1, если вершина инцидентна ребру. Для орграфа: 1 (начало), -1 (конец).
5. Списки смежности: Для каждой вершины указывается список соседних вершин.
6. Списки ребер: Просто список пар вершин, образующих ребра.

2. Связные и несвязные графы. Компоненты связности и бикомпоненты. Понятие слабой связности. Алгоритм поиска.

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

Для орграфов:

• Сильно связный (бикомпонента): Существует путь как $u\to v$, так и $v\to u$ для любых $u,v$.
• Слабо связный: Граф связен, если заменить все дуги на неориентированные ребра.

Алгоритм поиска по матрице достижимости ($T$):

• Бикомпоненты: $S=T\&T^T$. Единицы в строке $i$ матрицы $S$ указывают на вершины, входящие в одну сильную компоненту с $i$.
• Компоненты связности: Используют транзитивное замыкание неориентированного графа или поиск в ширину/глубину.

3. Метод нахождения количества путей в орграфах по матрице смежности. Алгоритм построения матрицы достижимости. Алгоритм Флойда-Уоршелла.

Количество путей: Элемент $(i,j)$ матрицы $B^k$ (матрица смежности в степени $k$) равен количеству путей длины $k$ из вершины $i$ в вершину $j$.

Матрица достижимости ($T$): $T=E\vee B\vee B^2\vee \cdots \vee B^{n-1}$ (булева сумма).

Алгоритм Флойда-Уоршелла: Динамический алгоритм для нахождения кратчайших путей (или просто достижимости) между всеми парами вершин. Пробегает $k$ от 1 до $n$, пытаясь улучшить путь $i\to j$ через промежуточную вершину $k$: $T_{ij}=T_{ij}\vee (T_{ik}\wedge T_{kj})$ (для достижимости).

4. Деревья. Минимальные и максимальные покрывающие деревья. Алгоритмы Краскала и Прима.

Дерево: Связный граф без циклов. (Или связный граф с $n$ вершинами и $n-1$ ребрами). Остовное (покрывающее) дерево: Подграф, содержащий все вершины исходного графа и являющийся деревом. Минимальное остовное дерево (MST): Остов, сумма весов ребер которого минимальна.

Алгоритм Краскала:

1. Сортируем ребра по весу.
2. Берем ребро с мин. весом. Если оно не образует цикл с уже выбранными — добавляем в дерево.
3. Повторяем, пока не наберем $n-1$ ребер.

Алгоритм Прима:

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

5. Эйлеровы пути и циклы. Критерий существования. Алгоритм Флёри. Задача китайского почтальона. Гамильтоновы пути и циклы. Критерии Дирака и Оре.

Эйлеров цикл: Цикл, проходящий по всем ребрам графа ровно по одному разу. Критерий: Граф связен и степени всех вершин четны. Эйлеров путь: Путь, проходящий по всем ребрам. Существует, если граф связен и нечетных вершин 0 или 2.

Алгоритм Флёри: Идем по ребрам, стирая их за собой. Не проходим по реберу-мосту, если есть альтернатива.

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

Гамильтонов цикл: Цикл, проходящий через все вершины ровно один раз. Критерий Дирака (достаточный): $n\ge 3$, степень каждой вершины $\ge n/2$. Критерий Оре (достаточный): Для любых несмежных $u,v$: $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$.

6. Изоморфизм и гомеоморфизм графов. Полные и двудольные графы. Плоские и планарные графы. Формула Эйлера. Критерий Куратовского.

Изоморфизм: Графы $G_1$ и $G_2$ изоморфны, если существует биекция между их вершинами, сохраняющая смежность. (Графы одинаковы с точностью до переименования вершин). Гомеоморфизм: Графы гомеоморфны, если они могут быть получены из одного графа (подразделением ребер) — вставкой вершин степени 2 на ребра.

Полный граф ($K_n$): Каждая пара вершин соединена ребром. Двудольный граф: Вершины разбиты на два множества, ребра идут только между множествами.

Планарный граф: Граф, который можно изобразить на плоскости без пересечения ребер. Плоский граф: Конкретное изображение планарного графа без пересечений.

Формула Эйлера (для связного плоского графа): $V-E+F=2$ (Вершины - Ребра + Грани = 2).

Критерий Куратовского (Понтрягина-Куратовского): Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных $K_5$ (полный на 5) или $K_{3,3}$ (полный двудольный 3 на 3).\