задачка

если что, спрашиваю не для того, чтобы похалявить а потому что интересно, блин, реально интересно

если что, спрашиваю не для того, чтобы похалявить

будто бы это что-то плохое.

ок, насчёт похалявить. вы хорошо разбираетесь в регулярных выражениях? есть маленький вопросик

Если ты сетуешь что ((AB+CD)'+CD)B + (A+B)' при 1,1,1,1 не работает. Дык ((AB+CD)'+CD)B+(A+B)' == A'+(BCD) (Пруф смотри в вольфраме).

блин, офигенно

есть маленький вопросик

Регулярно выражаюсь. Давай вопросик

Мы такое в универе на втором курсе решали, да.

http://sci.tech-archive.net/Archive/sci.math/2004-06/5730.html страшные вещи пишут

Положим

X = ABC + ABD + ACD + BCD
Y = AB + AC + AD + BC + BD + CD
Z = ABCD + X'(A+B+C+D)

A' = X'Y'Z' + X'Y'(B+C+D) + X'(BC+BD+CD) + Z'BCD

Ключевой момент: выход одного из вентилей «не» должен быть частью входа другого вентиля «не». Иначе не получится, что легко доказать.

страшные вещи пишут

Это не страшные вещи, это просто плохие обозначения плюс несделанные упрощения. Фактически, там дано такое же решение, как и у меня, только для трёх переменных:

X = AB + AC + BC
Y = ABC + X'(A+B+C)

спасибо. а если не секрет, как вы на такое вышли?

Ответ верный, но его можно упростить до

A' = Y'Z' + Y'(B+C+D) + X'(BC+BD+CD) + Z'BCD

Для тех, кто хочет еще что-то проанализировать, запишу X', Y' и Z' в дизъюнктивной форме:

X' = A'B' + A'C' + A'D' + B'C' + B'D' + C'D'
Y' = A'B'C' + A'B'D' + A'C'D' + B'C'D' + A'B'C'D'
Z' = A'BCD + AB'CD + ABC'D + ABCD' + A'B'C'D'

как вы на такое вышли?

Ух. Попробую описать эту внутреннюю кухню, насколько смогу.

Для начала я решил посильнее формализовать задачу. Нам нужно составить, с некоторыми ограничениями, три функции X, Y и Z от логических переменных A, B, C и D, а также функции N, M, K, L уже от семи переменных, так, что

N(A, B, C, D, X'(A, B, C, D), Y'(A, B, C, D), Z'(A, B, C, D)) = A'

Первым моим предположением было, что X, Y и Z получаются при помощи «и» и «или» из A, B, C и D. То есть, в частности, X' не участвует в выражениях для Y и Z и т.п. Тогда три функции X, Y, Z от четырёх переменных будут, в общем-то, аналогичны функциям N, M, K и L от семи переменных: и те и другие получаются из своих аргументов при помощи «и» и «или».

Затем я попробовал заменить условие типа «получается при помощи 'и' и 'или'» на более простое. Очевидным кандидатом было условие МОНОТОННОСТИ: если некая функция получается из своих аргументов только при помощи «и» и «или», то она монотонна, в смысле, что если мы меняем один из аргументов с 0 на 1, то значение функции не может уменьшиться. Я не был уверен, что условие монотонности является также ДОСТАТОЧНЫМ (т.е., что любая монотонная функция может быть получена таким способом), но это казалось разумным предположением.

В этот момент стало очевидным, что нужно использовать упорядоченные множества. В частности, множество Q, состоящее из двух элементов 0 и 1, упорядоченное как «0 < 1».

Итого, мне нужны три монотонных функции от четырёх переменных, и четыре монотонных функции от семи переменных, удовлетворяющие выписанным выше уравнениям.

Далее, я решил, что на первом этапе мне нет нужды явно выписывать эти функции от семи переменных; они наверняка будут сложными. Мне достаточно, если их существование ничему не будет противоречить. Это означает, что не будет такого случая, чтобы нашлись два набора аргументов, один из которых больше другого, а требуемое значение функции, скажем, N на первом оказывается меньше, чем на втором.

Но ведь N = A'! Это значит, что наша «запрещённая» ситуация соответствует следующему: нашлись два набора (A,B,C,D,X',Y',Z'), таких, что первый из них больше другого, и при этом в первом значение A больше, чем во втором. Поскольку эта ситуация запрещена, это означает вот что: если поменять A с нуля на единицу, хотя бы одно из X', Y' и Z' должно УМЕНЬШИТЬСЯ, то есть, поменяться с единицы на ноль. Это значит, что хотя бы одно из X, Y и Z должно увеличиться — поменяться с нуля на единицу.

Получается, что отображение (A, B, C, D) -> (X, Y, Z) окажется не просто монотонным, но СТРОГО монотонным, то есть, если, например, A увеличивается, то тройка (X, Y, Z) не может остаться прежней, но должна увеличиться тоже. Получается строго монотонное отображение из Q^4 в Q^3, чего быть не может по очень простой причине: самая длинная строго возрастающая последовательность в Q^3 имеет 4 элемента, в то время как в Q^4 найдётся строго возрастающая последовательность из пяти элементов.

Отсюда следуют выводы. Вывод первый: моё исходное предположение оказалось неверным; выражение для кого-то из X, Y и Z включает в себя что-то из X', Y' и Z'. Вывод второй — менее формальный: большое значение имеет КОЛИЧЕСТВО тех из A, B, C и D, которые равны 1. Объясню поподробнее: дело в том, что именно эта величина позволяет доказать, что в Q^n нет строго возрастающих последовательностей длины более n+1. В самом деле, если такая последовательность нашлась, то количество компонент её i-го элемента (считая с нуля), равных 1, будет не меньше i, и это легко доказывается по индукции; значит, количество компонент её последнего элемента, равных 1, будет больше n.

Это наводит на мысль, что самое главное — с помощью X, Y и Z определить, СКОЛЬКО из A, B, C и D имеют значение 1. Определить, в некотором смысле, слой, на котором лежит четвёрка (A, B, C, D) — нулевой слой — все они равны нулю, первый слой — среди них ровно одна единица, и т.п.

Самый большой слой — второй: на нём аж шесть элементов (число сочетаний из 4 по 2). Прикидываем: что, если отделить его с помощью X и Y? Например, пусть X = 1 тогда и только тогда, когда среди A, B, C и D будет хотя бы три единицы, а Y = 1 тогда и только тогда, когда среди A, B, C и D хотя бы две единицы. По крайней мере, эти функции вполне себе монотонны. Остаётся отделить нулевой слой от первого, а третий — от четвёртого; у нас остался только Z, но мы можем пользоваться значениями X' и Y'. Впрочем, в этих случаях они совпадают (только на втором слое они будут отличаться), так что достаточно использовать X'. Фактически, остаётся единственный вариант: пусть Z=1, если мы находимся на четвёртом слое, либо если X'=1 и мы находимся не на нулевом слое.

Таким образом, я получил «подозреваемых» в качестве X, Y и Z. Так как они симметричны относительно A, B, C и D, мне достаточно далее придумать только функцию N. Не мудрствуя лукаво, я взял и выписал табличку:

A K X' Y' Z' N=A'
0 0 1  1  1  1
0 1 1  1  0  1
0 2 1  0  0  1
0 3 0  0  1  1
1 0 1  1  0  0
1 1 1  0  0  0
1 2 0  0  1  0
1 3 0  0  0  0

В общем, непохоже, чтобы что-то мешало существованию такой монотонной функции N. Я попытался придумать что-нибудь красивое и короткое, не смог, плюнул, и расписал по пунктам, когда N равно 1: а) Когда X'=Y'=Z'=1 (первая строчка) б) Когда X'=Y'=1 и K>=1 (вторая строчка; условие на K необходимо, чтобы исключить пятую строчку) в) Когда X'=1 и K>=2 (третья строчка; условие на K исключает шестую строчку) г) Когда Z'=1 и K=3 (четвёртая строчка; условие на K исключает седьмую строчку).

Это самое большое «или» я и записал.