0
голосов
0
ответов
71 показ

Для вычисления $$MAJ_n$$Эта функция принимает значение 1, если во входных данных 1 больше чем 0 и 0 в противном случае.Как я умею строить схему для та ...
0
голосов
0
ответов
135 показов

Рассматриваем схемы в стандартном базисе. Пусть схемная сложность функции f не больше A,а схемная сложность функции g не больше B. Докажите, что схемн ...
1
голос
1
ответ
136 показов

Найдите полином Жегалкина для функции $$MAJ_4(x, y, z, t)$$
0
голосов
0
ответов
276 показов

Доказать, что существуют булевы функции от n переменных схемной сложности больше (c * 2^n)/n.
0
голосов
0
ответов
187 показов

Доказать, что всякую функцию f: {0,1}^n → {0,1} можно вычислить схемой размера не больше O(n * 2^n).
-2
голосов
0
ответов
853 показа
-1
голосов
0
ответов
938 показов

Сколько ненулевых коэффициентов в многочлене Жегалкина, который равен x1 ∨ x2 ∨ · · · ∨ xn ?
-1
голосов
0
ответов
648 показов

Функция f вычисляется в базисе {¬MAJ(x1, x2, x3), MAJ(x1, x2, x3)} схемойx1, x2, x3, s1 := MAJ(x1, x2, x3); s2 := ¬MAJ(x1, x2, x3); s3 := ¬MAJ(s1, s2, ...
0
голосов
1
ответ
924 показа

Является ли полным базис {∨; →} из дизъюнкции и импликации?
-1
голосов
0
ответов
841 показ
-1
голосов
0
ответов
816 показов

Булева функция f : {0, 1}^n → {0, 1} называется монотонной, если для всяких x, y ∈ {0, 1}^n верно x <= y ⇒ f(x) <= f(y), где векторы x и y сравн ...
-2
голосов
0
ответов
762 показа

Докажите, что всякую монотонную булеву функцию можно вычислить монотонной схемой
-1
голосов
0
ответов
681 показ

Булева функция f : {0, 1}^n → {0, 1} называется линейной, если она представляется в виде f(x_1, ... , x_n) = a_0 ⊕ (a_1 ∧ x_1) ⊕ · · · ⊕ (a_n ∧ x_n) д ...
1
голос
1
ответ
304 показа

Сконструировать пример схемы в базисе дизъюнкции, конъюнкции и отрицания, реализующей функцию $%f(x_1, ..., x_n, y_1, ..., y_n)$%, которая принимает з ...
0
голосов
0
ответов
253 показа

Булева функция U2(x1, . . . , xn) равна 1 тогда и только тогда, когда среди значений x1,...,xn есть ровно 2 единицы. Постройте схему размера O(n), выч ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru