Медиана

Булевы функции – один из центральных объектов изучения дискретной математики. Множество 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(x₁, x₂, ... , x_n) называется самодвойственной, если для любого набора переменных выполнено следующее свойство: f(x1, x2, ... , xn) = f(x1, x2, ..., xn), где x означает not x. Пример самодвойственной функции: f(x, y, z) = x ⊕ y ⊕ z.

Функция f(x₁, x₂, . . . , x_n) называется монотонной, если для любых двух наборов переменных x₁, x₂, ..., x_n и y₁, y₂, ..., y_n, таких что x_i ≤ y_i для всех i, выполнено следующее свойство: f(x₁, x₂, ..., x_n) ≤ f(y₁, y₂, ..., y_n). Пример монотонной функции: 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 символов.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]