Функции 2-значной логики. Лемма о числе функций. Элементарные функции 1-ой и 2-х переменных
Пусть $U = { u_1,u_2,..., u_m,... } $ — исходный алфавит переменных (аргументов) и $ E_2 = { 0,1 } $.
Определение. Функция $f(u_ { i_1 } , u_ { i_2 } ,... ,u_ { i_n } )$, где $u_ { i_s } \neq u_ { i_t } $ при $s \neq t$, аргументы и значение которой определены на множестве $E_2$, называется функцией алгебры логики или булевой функцией.
Замечание. Чтобы избежать сложных обозначений для индексов переменных, мы будем употреблять в качестве произвольных символов алфавита $U$ символы $x,y,z,..$, а также эти символы с индексами $x_1, x_2, . . . , y_1,y_2, . . .$
Опишем два способа задания функций алгебры логики.
$\textbf { Таблица. } $ Для задания функции $f (x_1,..., x_n)$ достаточно указать, какое значение функции соответствует каждому из наборов значений аргументов, т.е. выписать таблицу.
$x_1$ | ... | $x_ { n-1 } $ | $x_ { n } $ | $f(x_1, ..., x_ { n-1 } , x_n)$ |
0 | ... | 0 | 0 | $f(0, ..., 0, 0)$ |
0 | ... | 0 | 1 | $f(0, ..., 0, 1)$ |
0 | ... | 1 | 0 | $f(0, ..., 1, 0)$ |
0 | ... | 1 | 0 | $f(0, ..., 1, 1)$ |
... | ... | |||
1 | ... | 1 | 1 | $f(1, ..., 1, 1)$ |
Таблица 1. Таблица функции $f(x_i,...,x_n)$
Обозначим через $P_2$ систему всех функций алгебры логики над алфавитом $U$, содержащую также константы $0$ и $1$.
Лемма 1.1. Число всех функций из $P_2$, зависящих от, переменных $x_i,x_2,...,x_n$, равно $2^ { 2^ { n } } $.
Доказательство. Легко видеть, что $n$ переменных принимают $2^ { n } $ различных значений. Поэтому таблица функции $f (x_i,... ,x_n)$ содержит $2^ { n } $ строк (наборов). Наборы принято располагать в соответствии с естественным порядком следования двоичных записей чисел $0,1,..., 2^ { n } — 1$. Поскольку на каждом наборе функция принимает одно из двух значений { $0$ или $1$ } , то число различных функций равно $2$ в степени "количество наборов", т.е. $2^ { 2^ { n } } $.
Следовательно, уже при сравнительно небольших значениях $n$ перебор функций становится практически невозможным, даже с использованием компьютера.
Рассмотрим примеры функций алгебры логики. Данные функции часто употребляются в математической логике и кибернетике и играют такую же роль, как, например, $x^n$ или $sin x$ в анализе, поэтому их называют элементарными.
$x$ | константа $0$ | константа $1$ | тождественная $x$ | отрицание $\bar { x } $ |
0 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
Таблица 2. Элементарные функции одной переменной.
$x_1$ | $x_2$ | коньюнкция $x_1\wedge x_2$ | дизъюнкция $x_1\vee x_2$ | импликация $x_1\rightarrow x_2$ | сложение по mod2 $x_1\oplus x_2$ | эквиваленция $x_1\equiv x_2$ | штрих шеффера $x_1|x_2$ |
0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
Таблица 3. Элементарные функции двух переменных.
Замечание. Часто вместо $x_1\wedge x_2$ пишут $x_1x_2$. Также заметим, что $x_1\wedge x_2 = min(x_1; x_2) = x_1\cdot x_2$, $x_1\vee x_2 = max(x_1, x_2)$
Равенство функций и эквивалентность формул
Введенное понятие функции не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа аргументов.
Определение. Функция $f(x_1,... ,x_ { i—1 } ,x_i,x_ { i+1 } ,... ,x_n)$ из $P_2$ существенно зависит от переменной $x_i$, если существуют такие значения $( \alpha_1 ,..., \alpha_ { i—1 } , \alpha _ { i+1 } ,..., \alpha _n$ переменных $x_1 ,..., x_ { i—1 } , x_ { i+1 } ,..., x_n$, что
$f( \alpha_1 ,..., \alpha_ { i-1 } ,0, \alpha_ { i+1 } ,..., \alpha_n) = f( \alpha_1 ,..., \alpha_ { i-1 } ,1, \alpha_ { i+1 } ,..., \alpha_n)$.
В этом случае переменная $x_i$ называется существенной. Если $x_i$ не является существенной переменной, то она называется фиктивной.
Пусть для функции $f(x_1 ,..., x_n)$ перемениая $x_i$ является фиктивной. По таблице функции $f(x_1 ,... ,x_n)$ построим новую таблицу, вычеркивая все строки вида $(0,..., а_ { i—1 } ,1, a_ { i+1 } ,..., a_n)$ и вычеркивая столбец переменной $x_i$. Полученная таблица определяет некоторую функцию $g(x_1,..., x_ { i—1 } ,x_ { i+1 } ,..., x_n)$. Будем говорить, что функция $g$ получена из $f$ путем удаления фиктивной переменной $x$, а также, что функция $f$ получается из $g$ путем введения фиктивной переменной $x_i$.
Определение. Функции $f_1$ и $f_2$ называются равными, если функцию $f_2$ можно получить из $f$ путем введения и удаления фиктивных переменных.
Напомним, что каждой формуле над $F$ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.
Далее:
Механические приложения тройного интеграла
Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе
Вычисление поверхностного интеграла второго рода
Вычисление двойного интеграла. Двукратный интеграл
Вычисление криволинейного интеграла второго рода. Примеры.
Несобственные интегралы по неограниченной области
Соленоидальное векторное поле
Дифференциальные характеристики векторного поля
Логические следствия
Вычисление двойного интеграла
Класс $T_1$. Теорема о замкнутости класса $T_1$
Определение криволинейного интеграла второго рода
Вычисление поверхностного интеграла первого рода
Теорема Стокса
Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах
Огравление $\Rightarrow $
Комментарии ()