Вам дана булева функция от трех переменных, заданная своей таблицей истинности. Требуется построить минимальное по длине выражение, равное этой функции. Выражение может содержать:
- Операцию И ('&', ASCII код 38)
- Операцию ИЛИ ('|', ASCII код 124)
- Операцию НЕ ('!', ASCII код 33)
- Переменные x, y и z (ASCII коды 120-122)
- Круглые скобки ('(', ASCII код 40, и ')', ASCII код 41)
Если выражений несколько, требуется найти лексикографически минимальное.
Операции имеют стандартный приоритет: самый большой приоритет у НЕ, затем идет И, а самый маленький приоритет у ИЛИ. Формально, выражение должно удовлетворять следующей грамматике:
E ::= E '|' T | T
T ::= T '&' F | F
F ::= '!' F | '(' E ')' | 'x' | 'y' | 'z'
Выходные данные
Выведите n строк, в i-й должно содержаться выражение минимальной длины, равное i-й функции. Если выражений минимальной длины несколько, нужно вывести лексикографически минимальное. Выражения должны удовлетворять грамматике из условия и не должны содержать пробельных символов.
Примечание
Таблица истинности для второй функции:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
00110011
00000111
11110000
00011111
|
y
(y|z)&x
!x
x|y&z
|