Cайты для работы и коммуникаций
Лучше один раз увидеть, чем 100 раз услышать!
Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.
Критерий полноты { формулировка } . Лемма о немонотонной функции
Формулировка. Система булевых функций $F$ является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов $~S,M,L,T_0,T_1$.
- монотонные функции { функция монотонно не убывает по каждому из своих аргументов } ;
- функции, сохраняющие нуль { функция от нуля даёт ноль } ;
- функции, сохраняющие единицу { функция от единицы даёт единицу } ;
- линейные функции { функция представима многочленом, в котором каждый член состоит из одной переменной } ;
- самодвойственные функции { функция двойственна сама себе } .
Лемма: { о немонотонной функции } : Суперпозицией констант 0 и 1 и немонотонной функции можно получить отрицание.
Доказательство: Пусть $f(x_1, x_2 , ..., x_n)$ немонотонная функция. Тогда $\exists$ набор $(a_1, a_2, ...,a_n), b = (b_1, b_2, ...,b_n)$ для которых $a \leq b$, но $f(a) > f(b)$. Пусть $i_1, i_2, ...,i_k$ есть все те номера аргументов, для которых $a_ { ip } < b_ { ip } , p=1,2, ...,k$. На остальных аргументных местах $j$ имеем $a_j = b_j$. В выражении $f(a_1, a_2, ...,a_n)$ заменим нули на местах $i_1, i_2, ...,i_k$ на $x$. В результате получим функцию $g(x)$, для которой $g(0) = f(a) = 1$ и $g(1) = f(b) =0$, то есть для $g(x)$ является отрицанием.
Лемма: функция монотонна $\Longleftrightarrow$ ее сокращенная ДНФ не содержит отрицания.
Следствие: Функция $f$ монотонна $\Longleftrightarrow$ минимальная ДНФ не содержит отрицаний переменных.
Далее:
Функции k-значной логики. Элементарные функции. Лемма об аналоге правила де Моргана
Теорема об алгоритме распознавания полноты
Класс $T_0$. Теорема о замкнутости класса $T_0$
Функции 2-значной логики. Лемма о числе функций. Элементарные функции 1-ой и 2-х переменных
Критерий полноты {формулировка}. Лемма о несамодвойственной функции
Криволинейный интеграл первого рода
Нахождение потенциала
Критерий полноты {формулировка}. Лемма о немонотонной функции
Класс $L$. Теорема о замкнyтости класса $L$
Вычисление криволинейного интеграла первого рода. Примеры
Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
Полином Жегалкина. Пример.
Теорема о предполных классах
Поток векторного поля через поверхность
Дифференциальные характеристики векторного поля
Огравление $\Rightarrow $
Комментарии ()