Класс l
L – класс ленейных ф-ций.
Ф-ция f(x1,…xn) наз. линейной, если ее представление в виде полинома Жегалкина имеет вид:
f(x1,…xn)=a0a1x1a2x2…anxn.
Слогаемые aixi наз. линейными, а все остальные – нелинейными.
линейные: 0, 1, x, x=x1, .
нелинейные: &, , , , .
Каждая линейная ф-ция однозначно определяется своими коэфициэнтами, поэтому |L|=2n+1.
т.к. суперпозиция линейных ф-ций – линейная ф-ция, то класс линейных ф-ций замкнут: |L|=L.
Лема о нелинейных ф-циях: Если ф-ция нелинейна, то из нее путем подстановки вместо переменных, констант, тождественной ф-ции и отрицания самой ф-ции можно получить коньюнкцию.
Док-во: Пусть fL. Тогда в ее представлении в виде полинома Жегалкина имеется наименьшее слагаемое. Будем предполагать, что в это слогаемое входят переменные x1 и x2. Тогда (3, 4,…,n):
f(x1, x2, 3, 4,…,n)=x1x2x1x2.
(в противном случае, переменные x1, x2 были бы фиктивными).
(x1, x2)= x1x2x1x2.
По ф-ции построем ф-цию S:
S(x1, x2)=(x1, x2).
Можно показать, что S(x1, x2)=x1&x2.
| T0 | T1 | S | M | L |
1 | - | + | + | + | + |
x | + | + | + | + | + |
x | - | - | - | - | + |
Из таблицы видно, что основные замкнутые классы попарно не совпадают.
-
Содержание
- Множества. Основные понятия.
- Операции над множествами и их свойства.
- Декартово произведение. Разбиение множеств.
- Алгебра множеств
- Отношение. Бинарное отношение
- Алгебра бинарных отношений
- Отображение. Виды отображений
- Отношение порядка. Изоморфизм упорядоченных множеств.
- Алгебраические системы. Изоморфизм алгебраических систем.
- Функции алгебры логики.
- Формулы. Реализация функций формулами.
- Эквивалентность формул. Свойства элементарных булевых функций.
- Двойственные функции. Принцип двойственности
- Разложение булевых функций по переменным. Сднф.
- Полнота и замкнутость.
- Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
- Классы т0, т1.
- Класс s.
- Класс м.
- Класс l
- Теорема о функциональной полноте. Проверка системы функций на полноту.
- Задача минимизации булевых функций.
- Задача минимизации булевых функций в геометрической постановке.
- Сокращенные днф.
- Тупиковые днф и решение задачи минимизации.
- Графы. Основные понятия.
- Орграфы. Основные понятия.
- Маршруты. Цепи. Циклы. Связность.
- Операции над графами