Реферат Курсовая Конспект
Линейные функции - раздел Образование, Понятие равносильности формул Определение. Функция Называ...
|
Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций. Общий вид линейной функции
f = C0 ÅC1×x1Å C2×x2 Å… ÅCn×xn.
Число различных линейных функций от не более чем n переменных определяется формулой N = 2n+1.
Суперпозиция линейных функций есть функция линейная, следовательно, множество линейных функций образуют класс линейных функций, обозначаемый как L. Базисом класса L служит множество {xÅy, 1}
23.Замкнутые системы
Замкнутый класс в алгебре логики - такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: .
Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
Свойства замыкания Править
1. Любое множество является подмножеством своего замыкания: .
2. Замыкание подмножества является подмножеством замыкания: .
Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: .
3. Многократное применение операции замыкания эквивалентно однократному: .
Примеры замкнутых классов Править
§ Множество функций, принимающих только одно значение (констант), замкнуто. Если в качестве агрументов функции не рассматривать фиктивных переменных, суперпозиция в классе констант вообще окажется невозможной.
§ Множество унарных функций замкнуто.
§ Множество всех возможных булевых функций замкнуто.
Особо важны для теории булевых функций следующие замкнутые классы, выделенные Эмилем Постом:
§ Класс функций, сохраняющих константу 0:
.
§ Класс функций, сохраняющих константу 1:
.
§ Класс самодвойственных функций:
.
§ Класс монотонных функций:
.
§ Класс линейных функций:
.
Ни один из классов Поста не содержится целиком в объединении четырёх остальных; любой замкнутый класс булевых функций, отличный от , целиком содержится хотя бы в одном из пяти классов Поста.
Некоторые свойства замкнутых классов
§ Непустое пересечение замкнутых классов снова является замкнутым классом.
§ Объединение замкнутых классов может замкнутым классом не являться.
§ Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит тождественную функцию.
§ Дополнение замкнутого класса булевых функций до множества всех булевых функций замкнутым классом не является
– Конец работы –
Эта тема принадлежит разделу:
Если функция f задана формулой построенной с помощью amp и переменных то по теореме о суперпозиции двойственных функций и ввиду того... Дизъюнктивная нормальная форма и совершенная дизъюнктивная...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Линейные функции
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов