СВ в 18:09, 24 октября 2026

2026-10-24T18:09:02Z

← Предыдущая		Версия 18:09, 24 октября 2026
Строка 138:		Строка 138:
	В таком случае будем писать $f=g$.		В таком случае будем писать $f=g$.
	}}		}}

			Конспект: [[Дискретная математика]]

СВ: Новая страница: «Математическая логика окончательно оформилась как самостоятельная математическая дис...»

2026-10-24T18:08:39Z

Новая страница: «Математическая логика окончательно оформилась как самостоятельная математическая дис...»

Новая страница

Математическая логика окончательно оформилась как самостоятельная математическая дисциплина
к 30-м годам XX века. Основная причина ее появления {{---}} математические парадоксы, например [[Парадокс Рассела|парадокс Рассела]].

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

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

Возникла идея исследовать язык логики и математики, подойти к доказательству на основе понятий аксиом и правил вывода.

Будем рассматривать булевы функции (функции алгебры логики) {{---}} функции, аргументы и значения которых лежат в множестве {"истина" , "ложь"}.
"Истину" и "ложь" будем обозначать соответственно 1 и 0.
Таким образом, булева функция $f$ от $n$ аргументов есть
$f : \underbrace{E_2 \times E_2 \times ... \times E_2 }_{n} \rightarrow E_2 .$
Аргументы этих функций будем называть логическими переменными и обозначать буквами $x$, $y$ и $z$, возможно, с индексами.
Множество всех булевых функций (функций алгебры логики) будем обозначать $P_2$.

{{Пример
|content=Табличное задание функции $f$:

<math>
\begin{array}{rrr|c}
x & y & z & f(x,y,z)\\
\hline
2^3 \left\{
\begin{array}{r}
0\\
0\\
0\\
0\\
1\\
1\\
1\\
1\\
\end{array}
\right.
&
\begin{array}{r}
0\\
0\\
1\\
1\\
0\\
0\\
1\\
1\\
\end{array}
&
\begin{array}{r}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1\\
\end{array}
&
\begin{array}{r}
1\\
0\\
1\\
0\\
0\\
1\\
0\\
1\\
\end{array}
\end{array}
</math>

Всего существует $2^3$ различных наборов значений трех переменных.
Если их нумеровать от $0$ до $2^3-1$, то набор с номером $i$ оказывается
представлением числа $i$ в двоичной системе счисления.
Всего различных функций от 3-х аргументов {{---}} $2^{2^3}$
В общем случае число строк в таблице для функции от $n$ аргументов равно $2^n$.
Число различных булевых функций от $n$ аргументов {{---}} $2^{2^n}$.
}}
{{Пример
|content=Рассмотрим, как зависит функция $f$ из предыдущего примера от переменной $y$.
Пусть <math>\gamma'=(\alpha_1, 0, \alpha_3)</math> и <math>\gamma''=(\alpha_1, 1, \alpha_3)</math> {{---}} два набора с произвольными значениями $\alpha_1$ и $\alpha_3$.
Тогда по таблице выше можно убедиться, что <math>f(\gamma')=f(\gamma'')</math>:
$f(0, 0, 0)=f(0, 1, 0)$, $f(0, 0, 1) = f(0, 1, 1)$ и так далее.
В таком случае, можно сказать, что функция $f$ не зависит существенно от переменной $y$,
или, что $y$ {{---}} несущественная переменная функции $f$.
}}
{{Замечание
|content=Среди $2^{2^n}$ различных функций от $n$ переменных далеко не все зависят от аргументов существенно. В это число войдут и все функции от $n-1$, $n-2$, и т. д. аргументов.
}}
{{Определение
|definition=
Будем говорить, что функция $f(x_1, x_2, ..., x_n)$ не зависит существенно от $x_n$
($x_n$ {{---}} фиктивная (несущественная) переменная функции $f(x_1, x_2, ..., x_n)$),
если для любых значений $\alpha_1, \alpha_2, ..., \alpha_{n-1}\in E_2 $
выполняется равенство $f(\alpha_1, \alpha_2, ..., \alpha_{n-1}, 0)=f(\alpha_1, \alpha_2, ..., \alpha_{n-1}, 1)$.

Переменные функции $f$, которые не являются фиктивными, называют существенными переменными
и говорят, что функция $f$ существенно от них зависит.
}}

[[Файл:p33-01-fictitious-variable-pairs.svg|frame|none|900px|alt=Таблица f(x, y, z) из восьми строк, сгруппированных парами: в паре различается только y, значения f совпадают; после удаления y остаётся таблица f′(x, z)|Рис. 1. В каждой паре строк совпадают <math>x</math> и <math>z</math>, различается только <math>y</math>, а значения <math>f</math> одинаковы. После удаления столбца <math>y</math> остаётся таблица <math>f'(x,z)</math>: поэтому <math>f(\alpha_1,0,\alpha_3)=f(\alpha_1,1,\alpha_3)</math>.]]

{{Пример
|content=Продолжим предыдущий пример.
Удалим из таблицы для функции $f$ по одной из каждой пары строк,
соответствующих разным значениям переменной $y$ при одинаковых $x$ и $z$,
а также удалим столбец со значениями переменной $y$.
Получим таблицу для новой функции $f'(x,z)$:

<math>
\begin{array}{cc|c}
x & z & f'\\
\hline
0 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 0\\
1 & 1 & 1\\
\end{array}
</math>

Функции $f$ и $f'$ по определению различны: у них разная область определения.
С другой стороны, если учитывать только существенные переменные, эти две функции
полностью совпадают. В дальнейшем будем считать такие функции равными.
}}
{{Определение
|definition=
Будем говорить, что две функции $f(x_1, x_2, ..., x_k)$ и $g(x_1, x_2, ..., x_l)$ равны,
если после удаления всех несущественных переменных получаются функции с одинаковыми таблицами.
В таком случае будем писать $f=g$.
}}

Булевы функции - История изменений

СВ в 18:09, 24 октября 2026

СВ: Новая страница: «Математическая логика окончательно оформилась как самостоятельная математическая дис...»