34. Logic Gates
The workshop was quiet, as it always was. Set apart from lecture halls and corridors alike, it knew nothing of student arguments or the rhythm of presses. Only the slow tick of cooling metal and the faint smell of oil marked the passing of time.
Liina stood near the workbench, hands folded, watching Mihkel re-cover the Logic Mill with its familiar canvas. She had seen it now. Once—and that was enough.
„You always show me what it does,“ she said at last, „but never how it decides.“
Mihkel paused. He had rehearsed many explanations in his head—about safety, about danger, about the weight of secrets—but none of them fit the question.
„Because it doesn’t decide the way people do,“ he said. „It does not weigh, or doubt, or hesitate.“
He hesitated himself, then drew a small piece of chalk from his pocket and marked two symbols on the workbench:
1 and 0
„Everything begins here,“ he said. „Yes and no. Presence and absence. The Mill knows nothing else.“
Liina leaned closer. „And from only that… you get all this?“
Mihkel nodded. „By rules of combination.“
He uncovered a corner of the Logic Mill, revealing a lattice of small levers and stops. Each was simple. Almost disappointingly so.
„When two truths meet,“ he continued, „they must obey a gate.“
He sketched quickly:
(1 & 1) → 1
(1 & 0) → 0
„This one only allows agreement,“ he said. „Both must stand, or neither passes.“
Liina considered it. „Like a promise,“ she said. „It holds only if both keep it.“
Mihkel smiled despite himself.
He drew another.
(1 ! 1) → 0
(1 ! 0) → 1
„And this one forbids sameness,“ he added. „Only difference survives.“
Liina straightened. „That one is cruel,“ she said quietly.
Mihkel did not disagree.
„The Mill knows no kindness,“ he said. „Only consistency.“
He prepared a short tape and fed it into the machine, enclosing the symbols within careful parentheses, like thoughts nested inside other thoughts.
The Logic Mill stirred. Not with urgency, but with certainty. Each gate collapsed its judgment into a single mark, passing the remainder onward.
Liina watched without speaking.
„So this is how it thinks,“ she said at last. „By refusing to think at all.“
Mihkel covered the Mill again. „Exactly.“
For the first time, explaining the machine left him more uneasy than hiding it.
On the input tape you’ll get an expression with different logic gates and boolean values (0 and 1).
Your task is to evaluate the expression and output the result (0 or 1).
The following logic gates are used:
- AND (
&) — outputs 1 if both inputs are 1, otherwise outputs 0 - OR (
|) — outputs 1 if at least one input is 1, otherwise outputs 0 - NOR (
^) — inverse of OR - XOR (
!) — outputs 1 if exactly one input is 1, otherwise outputs 0
An expression is always surrounded by parentheses. Expressions can be nested and will use parentheses to indicate the order of operations. An expression always has a single logic gate connecting two sub-expressions or values.
For example, the expression ((1&0)|(0!1)) should be evaluated as follows:
- Evaluate the left sub-expression (AND gate):
(1&0)→0 - Evaluate the right sub-expression (XOR gate):
(0!1)→1 - Combine the results with the OR gate:
(0|1)→1
More examples:
(1&0)→0((0|1)!1)→0(1!(1!1))→1