По заданной монотонной самодвойственной функции найти ее представление с использованием медианы

Булевы функции – один из центральных объектов изучения дискретной математики. Множество S булевых функций называют полным, если любая булева функция может быть представлена в виде композиции функций из множества S.

К классическим полным системам функций относят, например, {∨, ∧, ¬} для дизъюнктивной или конъюнктивной нормальной формы, или {⊕, ∧, 1} для полиномов Жегалкина, а также существуют полные системы, состоящие из одной функции стрелка Пирса ↓ (not or), и штрих Шеффера ' (not and).

Большинство полных систем, которые обычно рассматриваются, содержат унарные и бинарные функции. Но есть несколько тернарных операций, которые также представляют особый интерес. Одна из них – медиана: < xyz >, равная 0, если хотя бы два ее аргумента равны 0, и 1 если хотя бы два ее аргумента равны 1. Медиану легко выразить через конъюнкцию и дизъюнкцию:

< xyz > = (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x) = (x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x).

Функция f(x1, x2, ... , xn) называется самодвойственной, если для любого набора переменных выполнено следующее свойство: f(x1, x2, ... , xn) = f(x1, x2, ..., xn), где x означает not x. Пример самодвойственной функции: f(x, y, z) = x ⊕ y ⊕ z.

Функция f(x1, x2, . . . , xn) называется монотонной, если для любых двух наборов переменных x1, x2, ..., xn и y1, y2, ..., yn, таких что xi ≤ yi для всех i, выполнено следующее свойство: f(x1, x2, ..., xn) ≤ f(y1, y2, ..., yn). Пример монотонной функции: f(x, y, z) = x ∧ y ∧ z.

Легко проверить, что медиана является одновременно самодвойственной и монотонной. Более того, медиана оказывается полной для класса самодвойственных монотонных функция. Это означает, что любая самодвойственная монотонная функция может быть представлена в виде композиции медиан. Например, функция f (u, v, x, y, z) = ((u∨v∨x∨y)∧z)∨(u∧v∧x∧y) может быть представлена в виде f (u, v, x, y, z) = < uz < vz < xzy > > >.

По заданной монотонной самодвойственной функции найдите ее представление с использованием медианы.

Входные данные
Входной файл INPUT.TXT содержит формулу самодвойственной монотонной булевой функции. В формуле используются маленькие буквы английского алфавита в качестве переменных, а также следующие операции (в порядке приоритета при вычислении): «!» для not, «&» для and, «|» для or. Скобки как обычно используются для изменения приоритета операций. В формуле используется не более 5 переменных. Длина формулы не превышает 250 символов.

Выходные данные
В выходной файл OUTPUT.TXT выведите представление функции из входного файла с использованием медианы. Не выводите пробелов. Ваша формула должна содержать не более 50 000 символов.

0