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