Основные понятия

Элементы теории множеств

Свойства операций

Элементы математической логики

Таблица истинности

Свойства логических операций

Равносильности

Булева алгебра

Нечеткие множества

Теория множеств

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

Основные равносильности

Равносильности при раскрытии логических операций

Алгоритм доказательства равносильности логических формул

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

Применение булевой алгебры в теории множеств

Теоретико-множественные операции

Операции над нечеткими подмножествами

Свойства операций над нечеткими подмножествами

Геометрическая интерпретация нечетких множеств

Элементы нечеткой логики

Свойства операций над нечеткими высказываниями

Мощность множества

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

Формула включений и исключений

Характеристики графа

Пути и циклы в графе

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

A \sub B \Leftrightarrow x \in A \Rightarrow x \in B

x \in A \cap B \Leftrightarrow x \in A \wedge x \in B

x \in A \cup B \Leftrightarrow x \in A \vee x \in B

x \in A \subset A \Leftrightarrow x \in E \wedge x \notin A

X \subset A \setminus B \Leftrightarrow x \in a \wedge x \notin B

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

A \cap B = B \cap A, ~A \cup B = B \cup A

A \cap (B \cap C) = (A \cap B) \cap C, ~A \cup (B \cup C) = (A \cup B) \cup C

A \cap (B \cup C) = (A \cap B) \cup (A \cap C), ~A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

Также существуют более сложные свойства, описывающие взаимодействия с универсальным и пустым множествами.

A \cap A = A, ~A \cup A = A

A \cap E = A, ~A\cup E = E

A \cap \emptyset = \emptyset, ~A \cup \emptyset = A

A \cap \subset A = \emptyset, ~A \cup \subset A = E

Предложение в формальной логике о котором можно сказать истинно оно или ложно называется высказыванием. Если $A \vee B$ — некоторое высказывание, то $\neg A, ~A \cap B, ~A \cup B, A \Rightarrow B, ~A\Leftrightarrow B$ тоже являются высказываниями.

\neg A

$A$	1	0
$\neg A$	0	1

A \wedge B

$A\backslash B$	1	0
1	1	0
0	0	0

A \vee B

$A \backslash B$	1	0
1	1	1
0	1	0

A \Rightarrow B

$A \backslash B$	1	0
1	1	0
0	1	1

A \Leftrightarrow B

$A \backslash B$	1	0
1	1	0
0	0	1

Также существуют свойства для логических операций, которые отражают основные законы булевой алгебры.

A \wedge 1 = A, ~A \vee 1 = 1

A \wedge \neg A = 0, ~A \vee \neg A = 1

\neg (A \wedge B) = \neg A \vee \neg B, ~\neg (A \vee B) = \neg A \cap \neg B

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

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

\neg A \cap B \Rightarrow A \cup \neg B

Формула выполнима при $A=(1, 1, 0); ~B=(1, 0, 0).$

Две формулы называются равносильными если их значения истинности совпадают при любых значениях входящих в них высказываний.

A \equiv B

Существуют важные равносильности, которые позволяют упрощать логические выражения и доказывать эквивалентность формул.

\neg (\neg A) \equiv A

A \wedge A \equiv A, ~A \vee A \equiv A

A \wedge 1 \equiv A, ~A \vee 1 \equiv 1

A \wedge 0 \equiv 0, ~A \vee 0 \equiv A

A \wedge \neg A \equiv 0, ~A \vee \neg A = 1

Для упрощения выражений используются эти три равносильности, с помощью которых можно преобразовать исходное выражение.

A \Leftrightarrow B \equiv (A \Rightarrow B) \cap (B \Rightarrow A)

A \Rightarrow B \equiv \neg A \vee B

\neg(A \vee B) \equiv \neg A \wedge \neg B

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

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

(x \Rightarrow y) \Rightarrow x

Логическая формула принимающая значение ноль при любых значениях входящих в неё элементарных высказываний называется тождественно ложной.

Все входящии в нее элементарные высказывания меняются их отрицаниями.
$A \to \neg A$
Все кванторы меняются на смежные.
$\forall \to \exists, ~\exists \to \forall$
Все «и» меняются на «или» и наоборот.
$\wedge \to \vee, ~\vee \to \wedge$

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

Булевой алгеброй называется не пустое множество, содержащее наименьший элемент 0 и наибольший элемент 1, на котором заданы три операции: $\vee, \wedge, \neg,$ удовлетворяющие всем аксиомам.

Характеристической функцией множества $A$ (функцией принадлежности) можно задать любое подмножество $E.$

\mu_A(x)=\begin{cases} 0; &x \not\in A \newline 1; &x\in A \end{cases}

В операциях с нечёткими множествами основные операции над множествами выражаются через функцию принадлежности. Эти операции позволяют формализовать логические соотношения между нечёткими множествами.

A=B \Leftrightarrow \mu_A = \mu_B

A \subset B \Leftrightarrow \mu_B \geq \mu_A

\subset A \quad \mu_{\subset A} = 1 - \mu_A

A \cap B \quad \mu_{A\cap B} = \mu_A \odot \mu_B

$\odot$	0	1
0	0	0
1	0	1

A \cup B \quad \mu_{A\cup B} = \mu_A \oplus \mu_B

$\oplus$	0	1
0	0	1
1	1	1

Если на множестве $2^E$ задана булева алгебра с операциями $\odot, \oplus, \subset,$ то булеву сумма и произведение можно заменить на операции взятия максимума и минимума.

Нечетким подмножеством $\tilde A$ называется множество всех элементов $E$ снабженных функцией принадлежности $\mu_{\tilde A} (x)$ , которая принимает значения на отрезке [0, 1].

Для нечетких подмножеств также используются операции позволяющие выполнять сравнение, отрицание и другие логические операции.

\tilde A = \tilde B \Leftrightarrow \mu_{\tilde A} = \mu_{\tilde B}

\tilde A \subset \tilde B \Leftrightarrow \mu_{\tilde B} \geq \mu_{\tilde A}

\subset \tilde A \quad \mu_{\subset \tilde A} = 1 - \mu_{\tilde A}

А более сложные операции для пересечения, объединения и разности нечётких множеств.

\tilde A \cap \tilde B \quad \mu_{\tilde A \cap \tilde B} = min(\mu_{\tilde A}, \mu_{\tilde B})

\tilde A \cup \tilde B \quad \mu_{\tilde A \cup \tilde B} = max(\mu_{\tilde A}, \mu_{\tilde B})

\mu_{\tilde A \backslash \tilde B} = min(\mu_{\tilde A}, (1 - \mu_{\tilde B}))

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

\tilde A \cap \subset \tilde A \neq \emptyset

\tilde A \cup \subset \tilde A \neq E

Любое высказывание в бинарной логике можно сопроводить функцией истинности $(A, \mu_{\tilde A}).$ В нечеткой логике каждому высказыванию соответствует функция истинности, принимающая значения на отрезке $[0, 1].$

\mu_{\tilde A \wedge \tilde B} = min(\mu_{\tilde A}, \mu_{\tilde B})

\mu_{\tilde A \vee \tilde B} = max(\mu_{\tilde A}, \mu_{\tilde B})

\mu_{\neg \tilde A} = 1 - \mu_{\tilde A}

\tilde A \Rightarrow \tilde B \quad \mu_{\tilde B} > \mu_{\tilde A}

Для нечетких высказываний справедливы все свойства логических операций, которе справедливы для обычных высказываний за исключением двух, которые не выполняются.

\mu_{\tilde A} \wedge \tilde A \neq 0

\mu_{\tilde A} \vee \neg \tilde A \neq 1

Мощностью множества называется «количество» элементов этого множества.

|A|

Неконечное множество называется счетным если его члены можно занумеровать (построить взаимно-однозначное соответствие между элементами множества и множеством натуральных чисел).

Объединение и пересечение счетных множеств является счетным множеством. Подмножество счетных множеств является либо конечным либо счетным.

Мощность множества $\mathbb R$ называется континуум и обозначается $c.$ Не существует множества больше счетного, но меньше континуума.

$A \times B$ — декартово произведение множеств, где $a \in A, ~b \in B.$

A = \{1, 2\}, ~B = \{a, b\}

A \times B = \{1, a\}, \{1, b\}, \{2, a\}, \{2, b\}

B \times A = \{a, 1\}, \{a, 2\}, \{b, 1\}, \{b, 2\}

A \times B \neq B \times A

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

A \times A = A^2

$n$ -я декартова степень множества $A$ определяется для целых неотрицательных $n,$ как $n$ -кратное декартово произведение $A$ на себя.

\underbrace{A \times A \times \ldots \times A}_n

|A| = n, ~|B| = m

|A \cup B| = |A| + |B| - |A \cap B|

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

|A \backslash B| = |A| - |A \cap B|

Дано множество точек $X$ и множество отношений $T$ между этими отношениями, каждая точка $x_i \in X$ имеет отношение с некоторым подмножеством множества $X.$ Каждое отношение назовется ребром.

Графом называется множество точек $X$ с введенной на нем системой отношений $T.$ Обозначается $G(X,~T).$ Точки называются вершинами графа, а отношения называются ребрами и обозначаются $(x_i, ~x_j).$

Вершина $x_1,$ которая не имеет отношений ни с одной другой называется изолированной. Ребро графа, соединяющее вершину с ней самой, называется петлей. Граф у которого некоторые пары вершин соединены более чем одним ребром называются мультиграфом. Два ребра графа называются смежными если они имеют общую вершину, две вершины графа называются смежными если они принадлежат одному ребру. Вершина графа и некоторое ребро называются инцидентными если вершина принадлежит данному ребру.

Любой граф можно зажать при помощи матриц смежности и инцидентности. Пусть граф имеет $n$ вершин и $m$ ребер. Матрица $A_{n\times m}$ каждый элемент которой $a_{i,j}$ равен количеству ребер, соединяющий вершины $x_i, x_j$ называется матрицей смежности графа. Матрица $B_{m\times n}$ каждый элемент которой $b_{i, j}$ называется матрицей инцидентности. Любой граф имеет матрицу инцидентности и по матрицам смежности или инцидентности можно восстановить граф.

Граф называется полным если любые две вершины соединены ровно одним ребром. Если полный граф имеет $n$ вершин, то его количество ребер $m = C_n^2.$ Если задан некоторый граф с $n$ вершинами, то его дополнением называется граф с такими же вершинами и такими ребрами, которых не хватает у графа чтобы он стал полным.

Степенью вершины графа $d_i$ называется количество ребер, выходящих из данной вершины. Вершина называется четной (нечетной) если её степень $d_i$ четная (нечетная). Количество нечетных вершин в любом графе четно. В графе с $n$ вершинами всегда найдется две вершины одинаковой четности. Сумма степеней вершин любого графа равна удвоенному количеству ребер.

\sum\limits_{i=1}^n d_i = 2m

$\neg A \cap B$

$A \cup \neg B$

Путем между вершинами $x_i, x_j$ называется последовательность ребер, начинающихся в $x_i,$ и заканчивавшихся в $x_j,$ состоящих из смежных ребер. Длинной пути называется количество ребер в пути. Путь называется простым если он проходит через каждую вершину только один раз. Путь в графе, у которого начальная и конечная точка совпадает называется циклом. Длинной цикла называются количеством ребер в цикле. Цикл называется простым если он проходит через каждую вершину только один раз.