Gate — соберите схему под таблицу истинности
Три входа, три пустых слота, одна таблица истинности. Подберите элементы, которые её дают. Шесть задач, бесплатно.
Шесть задач. Подберите три элемента, чтобы схема совпала с таблицей.
Как играть
- Совместите целевой столбец. Нажимайте на слот, чтобы перебирать пять элементов.
- Разводка: g1 берёт A и B, g2 берёт выход g1 и C, g3 берёт A и выход g2.
- Элемента НЕ нет — подайте провод на оба входа И-НЕ или ИЛИ-НЕ, чтобы его инвертировать. Именно это делает их универсальными.
- Четыре проверки на задачу. Каждая сообщает только совпавшие строки, так что рассуждайте, а не перебирайте.
Как это работает
Каждая задача даёт таблицу истинности и схему, где разводка уже сделана, а элементов нет. Вы выбираете один из пяти двухвходовых элементов для каждого из трёх слотов так, чтобы схема давала целевой выход на всех восьми комбинациях входов. Элемента НЕ нет, и это урок, а не упущение: чтобы инвертировать провод, подайте его на оба входа И-НЕ или ИЛИ-НЕ — именно это и делает эти два элемента универсальными. Каждая задача доказуемо решаема: набор получен перебором всех 125 расстановок, а сложность — это измеренное число решений, от четырёх способов до ровно одного. На задачу даётся четыре проверки, и каждая сообщает лишь то, какие строки уже совпали, так что перебор безнадёжен, а рассуждение — нет. Всё работает на вашем устройстве, никуда ничего не отправляется, регистрироваться негде.
Головоломка про булеву логику, а не симулятор схем. У настоящего железа есть задержки распространения, ограничения по нагрузке и элемент НЕ.
Частые вопросы
Почему нет элемента НЕ?
Потому что его можно построить. Подайте один и тот же провод на оба входа И-НЕ — и получите инверсию: NAND(x, x) = NOT x. Тот же приём работает с ИЛИ-НЕ. Именно это имеют в виду, называя эти элементы универсальными: из них строится любой другой. Отсутствие НЕ в палитре как раз и заставляет это открыть.
Все ли задачи действительно решаемы?
Да, доказуемо. Пять элементов в трёх слотах — это 125 возможных схем, и игра перебирает их все до старта. Таблица истинности предлагается как задача, только если её даёт хотя бы одна расстановка, а сколько расстановок её дают — это и есть градация сложности: у некоторых целей четыре решения, у тридцати трёх — ровно одно.
Нельзя ли просто перебрать всё?
Не за четыре проверки. Расстановок 125, верных из них максимум четыре, так что угадывание даёт около 20 очков из 600 возможных — измерено, а не предположено. Перебор одного слота с проверкой на каждом шаге чуть хуже. Обратная связь после проверки нарочно скупая: какие строки совпали, и ничего о том, какой элемент неверен.
Как подступаться к задаче?
Прочитайте целевой столбец рядом со входами и сначала назовите функцию: это «A и что-то», это исключающее ИЛИ, выход почти всегда истинен? Затем идите по схеме назад: последний элемент видит A и один провод, значит настоящая задача — чем должен быть этот провод, и она меньше.