Выражение суммы по модулю два для n переменных

v_87

кто помнит выражение суммы по модулю два для n переменных через дизъюнкцию, конъюнкцию, отрицание

PETERPETER

для двух переменных:
(x1&!x2)|(!x1&x2)
теперь, если нужно добавить ещё одну переменную, что это выражение принимается за y1 и y2 и подставляется в аналогичное выражение (от y1 и y2). В итоге получится, что в итоговом выражении - 2^n переменных, что, конечно, выглядит страшно, но принципиально его улучшить нельзя, если я не торможу... Можно переписать в другом виде, раскрыв скобки и приведя с какой-либо из НФ - только здесь тоже та же сложность...

На память да и сейчас мне кажется (из ряда соображений что принципиально сократить здесь невозможно (можно в log(n) раз сократить хотя я могу ошибаться и ещё подумаю. Если тебя слущает, что запись такая громоздкая - то это вполне нормальное явление для дискры

v_87

так я делала, слишком громоздко

PETERPETER

Я то вот из каких соображений это говорю (о том, что врят ли возможно лучше):
Можно построить схему из функциональных элементов (тех же трёх которая будет выполнять такое сложение - эта схема будет иметь сложность O(n). Далее можно по этим схемам строить выражения - и вот эти выражения получаются такими громоздкими. Проблема в том, что выражение всегда зависит от всех переменных - то есть вычислив выражения от (n-1) переменных никогда нельзя сказать, чему оно равно от n переменных, из-за этого высота схемы из ФЭ не может быть меньше n, и из-за этого запись такая здоровая.

PETERPETER

Нет, можно проще - это я торможу, традиционно...
И схему можно более низкую построить, и запись - проще
сложность - что-то в районе O(n^2)
=========================================
Короче, пусть у нас n переменных, причём n=2^N
Для построения выражения от 2 переменных x1,x2 требуется выражение из 4 переменных, аналогично для двух переменных x3,x4. Обозначим за y1 = (x1&!x2)|(!x1&x2 y2 = (x3&!x4)|(!x3&x4). Тогда выражение, считающее для 4 переменных, будет z = (y1&!y2)|(!y1&y2) - и будет состоять из 4*4=16 элементов (пока не так интересно). Уменя вычислять выражения для 4 элементов с помощью 16 вхождений переменных, можно построить (аналогично) вычисление выражения для 8 элементов с помощью 16*4=64 вхождений переменных. Итого, если нужно вычислить выражение для n = 2^N переменных, то получится выражение, состоящее из 4^N вхождений, то есть зависимость - квадратичная, и для таких n можно построить выражение из n^2 вхождений переменных.

v_87

мне не нужна сложность, просто сама формула в общем виде, а я ее не могу записать исходя из формулы для двух

PETERPETER

Хорошо, как выглядит формула для n=2^N понятно? Тогда дополняем остальные нехватающие переменные нулями и записываем формулу для 2^N...

v_87

с переобозначением переменных,естественно, все понятно, только мне вот терм нужно записать, так что этот способ не катит я пыталась через днф, тоже что-то плохо выходит

PETERPETER

Я тоже не представляю, как корректно и красиво через ДНФ записать... Но вообще откуда задача такая пошла, что нужна именно аккуратная запись ответа? Дело в том, что рекурентные формулы вообще сложно записать нормально (в виде терма, скажем). Вообще, для статьи/книжки было бы самое правильное написать примерно так:

y_i = x_i, если i <=n
y_i = 0, если n < i <=2^N, где N - наименьшее целое >= log_2 (N)
T(y1,y2) = (y1&!y2)|(!y1&y2)
T(y1yk) = (T(y1y_{k/2}) & !T(y_{k/2+1}yk | (!T(y1y_{k/2}) & T(y_{k/2+1}yk (где k - степень двойки)

Это всё в виде системы... Вполне корректная и понятная запись... И в отличии он ДНФ здесь кодируется короткая форма выражения (O(n^2 а не O(2^n.

v_87

кодить как раз не нужно, просто нужно записать формулу языка второго порядка, через индивидные переменные, функциональные константы и с помощью кванторов

Sanych

$V_{i_1,i_2...i_{n-1}\in \{0,1\}} \left(x_1^{i_1} \& x_2^{i_2} \& ...
\& x_{n-1}^{i_{n-1}}\&
x_n^{1+i_1+...+i_{n-1}}\right)$
или в виде картинки

Длинно, стандартно, но вдруг пригодится.
x^a -- это x при a равном 0 (четном) и !x при a нечетном.

PETERPETER

я уже начинаю немного отъезжать от обсуждения...
Мне всё же непонятно
Во-первых, зачем здесь нужны кванторы?
Во-вторых, исходно говорилось, что нужен терм, а языки, всё же, оперируют с функциями (можно ввести функцию and(x1,x2) вместо x1&x2, у и аналогично not(x1) и т.п.). В принципе, можно с помощью рекурсивных функций это корректно записать, только не уверен, что смогу сделать это действительно корректно для конкретного способа...
В-третьих, subj тогда должен быть "матлогика", а не "дискра"

v_87

черт, матлогика у нас будет только в следующем семестре, а курсач мне сейчас надо делать ибо научник каждую неделю требует отчета о проделанной работе

PETERPETER

честно говоря, я просто не представляю, что за требования такие "у вас"
тогда, неверное, это примерно то, что я в виде системы с рекуррентными термами написал, или, быть может, что предложил (я правда такие формулы не перевариваю). Потому как языки, всё же, для другого предназначены...
Сформулируй получше, что именно нужно - тогда совместными усилиями что-нибудь да придумаем

v_87

с Вовой мы уже все обсудили, что-то не получили нужного результата

v_87

"f (n) (x1,...,xn) = x1 + ... + xn" (сумма по модулю два) нужно записать на языке
язык:
индивидные переменные
функциональные переменные
функциональные константы -, &, дизъюнкция
знак равенства
логические связки -, &, дизъюнкция
кванторы
скобки, запятые
Оставить комментарий
Имя или ник:
Комментарий: