== Математическая логика ==

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

([2], стр. 24) Рассмотрим совокупность элементов $ A, B, C, \dots $ и три операции, определенные для элементов этой системы.

Операция дополнения, которая каждому элементу $ A $ ставит в соответствие элемент $ A' $, называемый дополнением элемента $ A $.

Операция объединения, ставящая в соответствие каждой паре элементов $ A $ и $ B $ элемент $ A \cup B $, называемый объединением или суммой элементов $ A $ и $ B $.

Операция пересечения, ставящая в соответствие каждой паре элементов $ A $ и $ B $ элемент $ A \cap B $, называемый пересечением элементов $ A $ и $ B $.

Операции дополнения, объединения и пересечения должны удовлетворять следующим аксиомам:

$ a_1 ) $ $ A'' = A $

$ a_2 ) $ $ A \cup B = B \cup A $

$ a_3 ) $ $ ( A \cup B ) \cup C = A \cup ( B \cup C ) $

$ a_4 ) $ $ A \cap ( B \cup C ) = ( A \cap B ) \cup ( A \cap C ) $

$ a_5 ) $ $ A \cap ( B \cup B' ) = A $

$ a_6 ) $ $ ( A \cup B )' = A' \cap B' $

Система элементов, для которой определены операции дополнения, объединения и пересечения, удовлетворяющие аксиомам $ a_1 - a_6 $, называется по имени Джорджа Буля (1815 - 1864) //булевой алгеброй//.

Аксиома $ a_6 $ обеспечивает выполнение во всякой булевой алгебре закона двойственности.

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

([1], стр. 4) // Булевы функции // или функции алгебры логики -- функции, аргументы и значения которых лежат в множестве {"истина", "ложь"}.

Обозначения: "истина" -- 1, "ложь" -- 0, булева функция $ f $ от $ n $ аргументов -- 
$$ f : \underbrace{ \{0,1\} \times  \{0,1\} \times \dots \times \{0,1\} }_{n} \rightarrow \{0,1\}. $$

Аргументы булевых функций называют логическими переменными. Множество всех булевых функций обозначают $ P_2 $.

Булевы функции можно задавать с помощью таблиц. Число строк в таблице для функции $ n $ аргументов равно $ 2^n $. Число различных булевых функции от $ n $ аргументов равно $ 2^{2^n} $.

Функция $ f(x_1, x_2, \dots, x_n) $ не зависит существенно от $ x_n $, если для любых значений $ \alpha_1, \alpha_2, \dots, \alpha_{n-1} \in \{0,1\} $ выполняется равенство $f(\alpha_1, \alpha_2, \dots, \alpha_{n-1},0)=f(\alpha_1, \alpha_2, \dots, \alpha_{n-1},1) $. В таком случае $ x_n $ -- // фиктивная // или несущественная переменная функции $ f(x_1, x_2, \dots, x_n) $.

Переменные функции $ f $, которые не являются фиктивными, называют // существенными // переменными и говорят, что функция $ f $ существенно от них зависит.
 
Две функции $ f(x_1, x_2, \dots, x_k) $ и $ g(x_1, x_2, \dots, x_\ell) $ равны, если после удаления всех несущественных переменных получаются функции с одинаковыми таблицами. 

Пример.  $ f=g $

$$ \begin{array}{c c c | c}
x & y & z & f(x,y,z) \\ \hline
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\
\end{array} $$

$$ \begin{array}{c c | c}
x & z & g \\ \hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\end{array} $$

Еще форма записи: $f=(1,0,1,0,0,1,0,1) $.