Как определить линейная булева функция или нет
Я не пойму, что такое α1, α2, как ее находить?
Как определить периодична ли функция или нет?
Например функция y=\frac
Определить, является ли булева функция шефферовой
вводится булева функция (например f(y,x,z)=10001001), определить,является ли она шефферовой. То.
Класс функция(линейная или квадратичная)
Описать класс Математическая функция.Функция может быть линейной y=ax+b или квадратичной.
Как выяснить линейна ли булева функция?
Всем привет, помогите пожалуйста с этим сложным заданием, очень прошу помочь. Вот условие.
Чтобы найти эти коэффициенты, нужно подставить в полином Жегалкина (написанный выше) значения функции на различных наборах переменных и решить систему уравнений. Далее, подставив найденные коэффициенты в полином, убеждаемся в его линейности.
построить функцию y=kx+b (линейная функция) с помощью Vcart или canvas (form.canvas)
Надо построить функцию y=kx+b (линейная функция) с помощью Vcart или canvas (form.canvas)
Как определить объект Nothing или нет
Собственно сабж. Хотелост бы иметь функцию типа IsNull, но для объектов.
Булева функция
Примеры в тесте 1)Булева функция 0 → x тождественно равна функции 2)Булева функция 0 | x.
ЛИНЕЙНЫЕ БУЛЕВЫ ФУНКЦИИ 1. Полиномы Жегалкина. 2. Класс
ЛИНЕЙНЫЕ БУЛЕВЫ ФУНКЦИИ 1. Полиномы Жегалкина. 2. Класс линейных функций.
Вопрос 1. Полиномы Жегалкина Рассмотрим кольцевую сумму (операцию сложения по модулю 2 или сумму Жегалкина), которая обозначается х у и задается таблицей истинности:
О. 1. 1. Полиномом (многочленом) Жегалкина называется многочлен, являющийся суммой константы (0 или 1) и различных одночленов, в которых все переменные входят не выше, чем в первой степени: (1) причем на каждом наборе (i 1, i 2, …, ik) все ij (j = 1, 2, …, k) различны, а
Пример 1. 1. Полином Жегалкина константы равен самой этой константе. 2. Полином Жегалкина булевой функции одной переменной f(х) имеет вид f(х) = а 0 а 1 х. 3. Полином Жегалкина булевой функции двух переменных f(х1, х2) имеет вид f(х1, х2) = а 0 а 1 х1 а 2 х2 а 12 х1 х2. 4. Полином Жегалкина булевой функции трех переменных f(х1, х2, х3) имеет вид f(х1, х2, х3) = а 0 а 1 х1 а 2 х2 а 3 х3 а 12 х1 х2 а 13 х1 х3 а 23 х2 х3 а 123 х1 х2 х3.
Во всех приведенных формулах коэффициенты и свободный член а 0 принимают значения 0 или 1; число слагаемых в формуле равно 2 n (где n – число переменных). Можно показать, что число полиномов Жегалкина от n переменных х1, х2, …, хn, т. е. число выражений вида (1), равно Так как число булевых функций от n переменных так же равно то каждая булева функция может быть представлена полиномом Жегалкина.
T. 1. 1. (теорема Жегалкина) Каждая булева функция f(х1, х2, …, хn) может быть представлена в виде полинома Жегалкина и притом единственным образом (с точностью до порядка слагаемых). Пример 2. С помощью таблицы истинности найдем полином Жегалкина для функции х. х = х 1.
Алгоритмы построения полинома Жегалкина Известно, что любую булеву функцию, отличную от константы 0, можно представить в виде СДНФ. Сравним таблицы истинности дизъюнкции и кольцевой суммы:
Мы видим, что они отличаются только последней строкой, т. е. на наборе (11). Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю 2. Кроме того, х = х 1. На этом основан следующий алгоритм построения полинома Жегалкина.
Первый алгоритм построения полинома Жегалкина (на основе СДНФ) 1. Находим множество тех двоичных наборов, на которых функция принимает значение 1. 2. Составляем СДНФ. 3. В СДНФ каждый знак дизъюнкции заменяем знаком суммы Жегалкина. 4. Упрощаем, если можно, полученное выражение, используя тождество
5. В полученной формуле каждое отрицание заменяем на хi 1. 6. Раскрываем скобки в полученной формуле, содержащей только функции , и константу 1. 7. Приводим подобные члены, используя тождество хi = 0.
Пример 3. На основе СДНФ построить полином Жегалкина для функции Решение Данная функция представлена в форме СДНФ. Таким образом, имеет место представление
Второй алгоритм построения полинома Жегалкина (с помощью метода неопределенных коэффициентов) 1. Запишем предполагаемый результат в виде выражения общего вида с неопределенными коэффициентами. 2. Составляем систему линейных уравнений относительно 2 n неизвестных коэффициентов, содержащую 2 n уравнений, решением которой являются коэффициенты полинома Жегалкина.
Пример 4. С помощью метода неопределенных коэффициентов построить полином Жегалкина для функции Решение Запишем предполагаемый результат в виде выражения общего вида с неопределёнными коэффициентами:
Для определения значений коэффициентов вычислим левую и правую части для четырех возможных наборов значений входных переменных:
f(0, 0) = 1 = a 0 0 0 = a a = 1. f(0, 1) = 0 = 1 0 c 0 1 c = 0 c = 1. f(1, 0) = 0 = 1 b 0 0 1 b = 0 b = 1. f(1, 1) = 1 1 1 d = 1 d = 0. Таким образом, имеет место представление f(x 1, x 2) = 1 x 2.
Вопрос 2. Класс линейных функций О. 2. 1. Полином Жегалкина называется линейным (нелинейным), если он не содержит (содержит) конъюнкции переменных. О. 2. 2. Булева функция f(х1, х2, …, хn) называется линейной (нелинейной), если ее полином Жегалкина является линейным (нелинейным).
Полином Жегалкина линейной функции f(х1, х2, …, хn) имеет вид a 0 a 1 x 1 a 2 x 2 …. anxn. Из определения полинома Жегалкина следует, что для любой булевой функции коэффициенты при переменных х1, х2, …, хn и свободный член выражаются по формулам: а 0 = f(0, 0, …, 0), а 1 = а 0 f(1, 0, …, 0), а 2 = а 0 f(0, 1, …, 0), …, аn = а 0 f(0, 0, …, 1).
Алгоритм определения линейности (нелинейности) булевой функции 1. По таблице истинности указанной функции f(х1, х2, …, хn) и выше указанным формулам находим коэффициенты a 0, a 1, …, an. 2. Выписываем полином Ф(х1, х2, …, хn) = a 0 a 1 x 1 a 2 x 2 …. anxn и проверяем, задает ли он эту функцию. Для этого строим таблицу истинности полинома Ф(х1, х2, …, хn) и сравниваем ее с таблицей истинности функции f(х1, х2, …, хn).
3. Если результирующие столбцы таблиц истинности совпадают, то функция f(х1, х2, …, хn) линейная и Ф(х1, х2, …, хn) – ее полином Жегалкина. , т. е. f(х1, х2, …, хn) = Ф(х1, х2, …, хn). В противном случае функция f(х1, х2, …, хn) нелинейная.
Пример 5. Докажите, что булева функция f(х1, х2, х3), заданная таблицей истинности, линейна:
Решение 1. Вычислим коэффициенты а 0, а 1, а 2, а 3 полинома Жегалкина функции f(х1, х2, х3): а 0 = f(0, 0, 0) = 1, а 1 = а 0 f(1, 0, 0) = 1 1 = 0, а 2 = а 0 f(0, 1, 0) = 1 0 = 1, а 3 = а 0 f(0, 0, 1) = 1 0 = 1. 2. Запишем многочлен Ф(х1, х2, х3) = a 0 a 1 x 1 a 2 x 2 a 3 x 3 = =1 0 x 1 1 x 2 1 x 3. Таким образом, Ф(х1, х2, х3) = 1 x 2 х3.
Достроим в таблице истинности заданной функции последний столбец для Ф(х1, х2, х3):
3. Из расширенной таблицы истинности видно, что столбцы для Ф(х1, х2, х3) и f(х1, х2, х3) совпадают. Следовательно, данная функция f(х1, х2, х3) линейна и представима в виде линейного полинома Жегалкина: f(х1, х2, х3) = 1 x 2 х3. Класс линейных булевых функций обозначается L. Пример 6. 1. К классу линейных булевых функций относятся константы 0 и 1, тождественная функция х, функции х и х1 х2. 2. Функции х1 х2 не принадлежат классу L.
Научный форум dxdy
Последний раз редактировалось ariel777 05.07.2019, 08:13, всего редактировалось 3 раз(а).
Не могу осилить условие линейности булевой функции. Теорию на вики https://clck.ru/GvU9Q прочитал. Но не понял практическое применение, так как нигде не могу найти примеры применения этой теории.
Вот, допустим, задание:
Необходимо проверить, является ли функция линейной. Какие шаги я должен сделать при проверке и с чего начать?
Насколько я понимаю, конкретно эта функция уже представлена в виде многочлена Жегалкина. По определению функция является линейной если:
«. ее полином Жегалкина содержит только первые степени слагаемых.» вот этот момент про степень я недопонял. О какой степени речь? И пример какой-нибудь, пожалуйста.
Последний раз редактировалось Connector 05.07.2019, 12:00, всего редактировалось 5 раз(а).
Кстати, если в разложении возникает конструкция вида 
, то от неё всегда легко избавиться, заменив на 
.
Последний раз редактировалось ariel777 05.07.2019, 13:03, всего редактировалось 1 раз.
Обычные многочлены понимаете? Что многочлен
линейный, а
нет?
Как определить линейная булева функция или нет
Такое решение:
Если выполняется условие:
f2 = АЛЬФА0 + АЛЬФА1*x1+АЛЬФА2*x2+.АЛЬФАn*xn
то функция линейная
В моем случае
АЛЬФА0 = 1
АЛЬФА1 = 1
АЛЬФА2 = 1
АЛЬФА3 = 0
f2 = 1+x1+x2(выполняется, значит линейная)
Я не пойму, что такое АЛЬФА1,АЛЬФА2, как ее находить?
Чтобы найти эти коэффициенты, нужно подставить в полином Жегалкина (написанный выше) значения функции на различных наборах переменных и решить систему уравнений. Далее, подставив найденные коэффициенты в полином, убеждаемся в его линейности.
За вас это решать никто не будет. Если при разложении в полином Жигалкина функция не будет содержать конъюнкций нескольких переменных, то функция линейная. Для примера:
1) ПЖ линейной ф-ции: A0+A1x+A2y+A3z+A4j+A5k
2) ПЖ нелинейной ф-ции: A0+A1x+A2y+A3z+A4xy+A5yz+A6xz