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

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

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

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

Функция 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
голосов
0
ответов
458 показов

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

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

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

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

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

Булева функция U2(x1, . . . , xn) равна 1 тогда и только тогда, когда среди значений x1,...,xn есть ровно 2 единицы. Постройте схему размера O(n), выч ...
0
голосов
0
ответов
428 показов

Докажите полноту базиса, состоящего из одной функции x | y, которая по определению равна ¬(x∧y)(штрих Шеффера, она же NAND).
0
голосов
0
ответов
243 показа

Схемная сложность функции f не больше чем А, а схемная сложность функции g не больше B. Верно ли, что схемная сложность f XOR g не более чем A + B + 5 ...
0
голосов
0
ответов
198 показов

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