Изменения
Нет описания правки
= Дискретная математика, 1 семестр =
Задания, помеченные 🤔 - задания повышенной сложности. Задания, помеченные 😱 - задания очень высокой сложности. ✋ помечены задания, где мы передаем привет курсу "Алгоритмы и структуры данных".
# Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
# Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
# Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
# 🤔 🤔✋ Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
# 🤔 В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
# СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
# Выразите в явном виде "и", "или" и "не" через стрелку Пирса
# Выразите в явном виде "и", "или" и "не" через штрих Шеффера
# Приведите пример непороговой функции
# Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
# ✋ Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
# ✋ КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
