Логика из выключателей

Глава 28 закончилась вопросом: как кусок кремния складывает два бита? Случаев всего четыре: $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$ и $1 + 1 = 10_2$, то есть два в двоичной записи. Чтобы ответ всегда занимал два разряда, допишем ведущий ноль.

Разберите ответ по разрядам. Младший равен единице, когда единица ровно в одном из слагаемых. Старший — когда единицы в обоих. Старший — это «и» из главы 3, «и то, и другое»; младший — «одно из двух, но не оба», исключающее «или». В Python для битов их пишут как a & b и a ^ b, и ячейка выше это подтверждает: сложить два бита — значит вычислить две логические функции.

Выходит, машине, которая складывает, нужна вещь, вычисляющая логику электричеством. Её мы и построим: сначала из реле, которые щёлкают, потом из транзисторов, которые молчат. Затем в мастерской вы получите коробку деталей одного-единственного вида и соберёте из них всё остальное: «не», «и», «или», «исключающее или», сумматор. Каждый пройденный уровень кладёт новую деталь в коробку и заодно в «Искру-8» — учебный компьютер, который мы соберём в главах 29–31 и запустим в главе 32.

Выключатель, который нажимает ток

В главе 3 условие уже превращалось в схему: and ставил выключатели друг за другом, or — рядом, и лампа горела, когда выражение истинно. Но там выключатели нажимал человек. Чтобы схема считала сама, нужен выключатель, которым управляет другой ток.

Такой выключатель придумали ещё для телеграфа, он называется реле. В нём есть катушка с железным сердечником, подвижный железный якорь на пружине и пара контактов. Пустите ток через катушку — сердечник станет магнитом, притянет якорь, и тот щёлкнет контактами. Выключите ток — пружина вернёт якорь назад. Контакты бывают двух видов: нормально разомкнутые замыкаются, когда на катушке ток, а нормально замкнутые, наоборот, размыкаются.

В виджете четыре схемы, не считая цепочки. Два нормально разомкнутых контакта подряд — это «и»: лампа горит, только когда притянуты оба якоря. Два рядом — «или». Нормально замкнутый контакт — «не»: лампа горит, пока на катушке нет тока. А два нормально замкнутых контакта рядом дают «не (A и B)»: лампа гаснет, только когда нажаты обе кнопки. Запомните последнюю схему, она станет героиней главы.

«И» и «или» умели и выключатели из главы 3. У реле есть свойство поважнее: его выход можно подать на катушку другого реле. Выключатель под пальцем человека в такую цепочку не встанет. Контакты реле сами включают ток, который нажимает следующий выключатель. Включите режим «цепочка» и послушайте: щелчки бегут от реле к реле, как эстафетная палочка. Из такой эстафеты складывается логика любой глубины: ответ одного условия становится входом следующего. Слышна и цена: каждое звено щёлкает чуть позже предыдущего. В главе 30 эта задержка станет главной заботой конструктора сумматоров.

Кембридж, 1937. Магистерская работа

В ноябре того же 1937 года, независимо от Шеннона, исследователь Bell Labs Джордж Стибиц собрал на кухонном столе одноразрядный двоичный сумматор: старые реле, две лампочки от фонарика и полоски жести вместо переключателей. Машину потом прозвали «Модель K» — от английского kitchen, «кухня». Двое в один год пришли к одной мысли: реле, которые соединяют телефонные линии, умеют и считать.

Шеннону мы обязаны языком, на котором говорит эта глава. Схему можно записать формулой, формулу нарисовать схемой, а формулы преобразовывать по правилам алгебры. К самой алгебре мы вернёмся после мастерской, а сначала заменим щёлкающее реле на деталь, из которой сделан ваш компьютер.

Транзистор: реле без движущихся частей

У реле три беды. Якорю нужно несколько миллисекунд, чтобы долететь до контакта. Само реле размером с напёрсток, а то и больше. И оно изнашивается: контакты обгорают, пружины устают. Компьютер из реле возможен, такие строили в 1940-х, но он занимает комнату и складывает числа в лучшем случае несколько раз в секунду.

В декабре 1947 года в той же Bell Labs Джон Бардин и Уолтер Браттейн показали первый работающий транзистор, а их руководитель Уильям Шокли вскоре придумал его улучшенный вариант. Транзистор в современном процессоре устроен иначе, чем тот первый, но идея та же, что у реле: управляющий вывод — затвор — открывает или закрывает путь току. Только ничто не движется: путь открывается внутри кристалла, когда напряжение на затворе меняет свойства кремния под ним. Такой выключатель переключается за доли наносекунды, и на одном кристалле их помещаются десятки миллиардов.

Транзисторы бывают двух видов. Транзистор n-типа проводит ток, когда на затворе единица (высокое напряжение), а p-типа — когда ноль. Почти все цифровые схемы сегодня строят парами из обоих видов, это называется КМОП (CMOS). Вот как в КМОП устроен вентиль, который мы видели последним в виджете с реле, — «не (A и B)».

Нижняя цепочка соединяет выход с землёй, только когда открыты оба n-транзистора, то есть когда $A = 1$ и $B = 1$. В остальных случаях хотя бы один p-транзистор сверху открыт и подтягивает выход к питанию. Получается «не (A и B)», и на него уходят четыре транзистора. А «A и B» без отрицания так не построить: КМОП-схема с одним слоем транзисторов всегда переворачивает сигнал. Чтобы получить «и», к четырём транзисторам приходится добавить ещё два — инвертор. Поэтому в мире КМОП «не-и» — деталь простая и дешёвая, а «и» — составная.

Вентили

Схема, которая получает несколько битов и выдаёт один бит по фиксированному правилу, называется логическим вентилем. Правило вентиля — его таблица истинности, та же, что в главе 3, только вместо True и False теперь 1 и 0. На схемах вентили рисуют условными значками. Единого начертания нет: в виджете — значки американского стандарта, привычные по англоязычным книгам, а по стандарту МЭК и российскому ГОСТ 2.743 те же вентили рисуют прямоугольниками со знаком внутри: «&» для «и», «1» или «≥1» для «или».

Сколько вообще бывает вентилей с двумя входами? У таблицы четыре строки, в каждой выход — 0 или 1, значит, разных таблиц $2^4 = 16$. Переберём их все.

Шестнадцать, и у всех есть имена, хотя полезны далеко не все: «всегда 0» и «просто a» вентилем назвать трудно. Для трёх входов строк уже восемь, а таблиц $2^8 = 256$; для $n$ входов — $2^{2^n}$. Уже при пяти входах это больше четырёх миллиардов. Держать на складе по детали на каждую функцию невозможно, нужен маленький набор, из которого собирается любая. В мастерской этот набор сократится до одной детали.

Мастерская: всё из NAND

В коробке мастерской детали одного вида — NAND, по-русски «и-не»: он выдаёт 0, только когда на обоих входах единицы, и 1 во всех остальных случаях. Это схема из четырёх транзисторов, которую вы только что включали. На каждом уровне нужно собрать новую деталь: слева — входы, справа — выходы, посередине — ваша схема. Пройденный уровень кладёт собранную деталь в коробку, и на следующих уровнях ею можно пользоваться как готовой.

Как работать с верстаком. Кнопка «+ NAND» ставит новый вентиль, его можно перетаскивать. Чтобы провести провод, нажмите на выход (кружок справа от детали или от входа на левом краю), а потом на вход другой детали; можно и тянуть пальцем от одного к другому. Нажатие на занятый вход снимает провод, а лишнюю деталь убирает кнопка «удалить деталь», если сначала нажать на саму деталь. Тумблеры слева переключают входы, и по проводам с единицей бежит свет. Под верстаком — таблица истинности: в каждой строке видно, что нужно и что выдаёт ваша схема, ошибки подсвечены красным. Нажатие на строку выставляет её входы. Когда сойдутся все строки, уровень засчитан.

Уровень 1. Перевернуть сигнал

Первая деталь — «не»: на входе A, на выходе $\overline{A}$. У NAND два входа, а у нас один сигнал. Что будет, если подать его на оба?

Если на обоих входах одно и то же, из таблицы NAND остаются две строки: 0 и 0 дают 1, а 1 и 1 дают 0. Получилось «не». Хватило одного вентиля, меньше не бывает.

Уровень 2. И

Теперь в коробке есть «не». NAND — это «и», после которого всё перевернули. Как отменить переворот?

Два переворота подряд ничего не меняют, поэтому «и» — это NAND, за которым стоит «не». Внутри два вентиля NAND.

Уровень 3. ИЛИ

Здесь придётся подумать. «A или B» ложно в одном-единственном случае: когда ложны оба. То есть «A или B» означает «неверно, что и A ложно, и B ложно». Переведите эту фразу на язык деталей слово за словом.

«A ложно» — это $\overline{A}$, «и… неверно» — это NAND. Значит, $A + B = \mathrm{NAND}(\overline{A}, \overline{B})$: два «не» перед входами одного NAND, итого три вентиля. Мы только что воспользовались законом де Моргана из главы 3, и скоро он получит доказательство.

Уровень 4. Одно из двух

Последняя деталь первого яруса — исключающее или, XOR: единица, когда входы различны. Это младший разряд суммы из начала главы. Собрать его из готовых «и», «или», «не» нетрудно, например как «(A или B) и не (A и B)». Посчитайте, сколько NAND окажется внутри, а потом попробуйте уложиться в четыре.

Как уложиться в четыре NAND

Пусть $n = \mathrm{NAND}(A, B)$. Он равен нулю только при $A = B = 1$. Теперь посмотрим на $\mathrm{NAND}(A, n)$. Если $A = 0$, он равен 1. Если $A = 1$, то $n = \overline{B}$, и $\mathrm{NAND}(1, \overline{B}) = B$. Ноль получается только при $A = 1$, $B = 0$, поэтому $\mathrm{NAND}(A, n) = \overline{A \cdot \overline{B}}$. Симметрично $\mathrm{NAND}(B, n) = \overline{\overline{A} \cdot B}$. Последний NAND от этих двух по закону де Моргана даёт $A\overline{B} + \overline{A}B$, то есть «одно из двух». Хитрость в том, что вентиль $n$ используется дважды: один выход может питать сколько угодно входов.

Всё, что вы собрали, можно проверить кодом. Ниже — те же четыре детали на Python: функции, которые знают только nand, и счётчик, сколько раз его вызвали на одно вычисление.

Столбцы совпадают с таблицами из ячейки про шестнадцать вентилей, а счётчики — с рекордами мастерской: 2, 3 и 4. Компьютерный перебор подтверждает, что меньше нельзя ни для одного из них.

Алгебра, которую можно проверить перебором

Шеннон записывал схемы формулами, и мы будем делать так же. Договоримся об обозначениях: «и» пишется как умножение, $ab$ или $a \cdot b$; «или» — как сложение, $a + b$; «не» — чертой сверху, $\overline{a}$. Переменные принимают только значения 0 и 1, и $1 + 1$ здесь равно 1: «истина или истина» — истина. Такая система называется булевой алгеброй, в честь Джорджа Буля, который в 1854 году записал логику уравнениями.

Законы булевой алгебры похожи на школьные, но не все. У каждого закона два варианта: для «и» и для «или».

Странно выглядит второй распределительный закон: «или» раскрывается через «и», как будто $2 + 3 \cdot 4$ равнялось бы $(2 + 3)(2 + 4)$. С числами так нельзя, а с битами можно. Последняя строка — законы де Моргана, названные по имени лондонского математика Огастеса де Моргана, который переписывался с Булем. Отрицание проходит внутрь скобки и по дороге меняет «и» на «или», а «или» на «и».

В школьной алгебре тождество доказывают выкладками: подставить все числа невозможно. Здесь значений всего два, и тождество от трёх переменных достаточно проверить на восьми наборах. Такой перебор — полноценное доказательство, и провести его можно поручить компьютеру.

Последняя строка — частая ошибка: отрицание внесли в скобку, а «и» на «или» поменять забыли. Перебор сразу находит контрпример.

Законы в обычном коде

Булева алгебра пригодится не только конструктору процессоров. Условие if not (age < 18 or not has_ticket): читается с трудом: «если неверно, что младше восемнадцати или без билета». По закону де Моргана отрицание уходит внутрь, «или» становится «и», двойное «не» исчезает: if age >= 18 and has_ticket:. Смысл тот же, а прочесть можно с первого раза. Ещё пример: if is_admin or (is_admin and is_owner): по закону поглощения сокращается до if is_admin:.

Какое условие равносильно not (x > 0 and y > 0)?

x <= 0 or y <= 0 x <= 0 and y <= 0 x < 0 or y < 0

По де Моргану «не (A и B)» = «не A или не B», а «не (x > 0)» = «x <= 0». Обе ловушки в программах встречаются постоянно: забыть поменять «и» на «или» и забыть про равенство на границе.

Почему одного NAND хватает на всё

Мастерская обещала, что из NAND собирается что угодно. Четыре уровня — ещё не доказательство: может быть, есть функция, которая из NAND не складывается никак. Докажем, что такой нет.

Формула из шага 1 — сумма произведений, по одному на каждую единицу таблицы, — называется дизъюнктивной нормальной формой. Из доказательства следует сильная вещь: любая схема без памяти — сумматор, блок сравнения, дешифратор команд процессора — в принципе собирается из одной детали. До памяти мы дойдём в главе 31, и она тоже окажется сделанной из NAND.

А из одних «и» и «или», без «не», можно собрать что угодно?

Да, если взять их побольше Нет, кое-что не получится

Нет. Подайте на все входы такой схемы нули. Вентиль «и» или «или», у которого на входах нули, выдаёт ноль, поэтому нули дойдут до самого выхода. А «не» обязано ответить на ноль единицей. Схемы из «и» и «или» называют монотонными: включение входа может зажечь их выход, но не погасить. NAND отличается тем, что внутри у него уже есть переворот.

Доказательство даёт и рецепт: по таблице истинности сразу строится схема. Виджет ниже проделывает это для любой функции от двух, трёх или четырёх входов. Можно щёлкать по клеткам столбца выходов, а можно вписать выражение на Python.

Карта Карно: упрощаем на глаз

Формула из доказательства верна, но расточительна. Возьмём функцию большинства от трёх входов: она равна 1, когда единиц хотя бы две. В её таблице четыре строки с единицей — 011, 101, 110 и 111, — значит, по рецепту выйдет четыре произведения по три множителя:

$$\mathrm{maj}(a, b, c) = \overline{a}bc + a\overline{b}c + ab\overline{c} + abc.$$

Первое и последнее слагаемые различаются только множителем $a$. По распределительному закону $\overline{a}bc + abc = (\overline{a} + a)bc = bc$. Переменная, которая встречается в паре и с чертой, и без, выпадает. Слагаемое $abc$ годится в пару и второму, и третьему: по закону повторения его можно написать трижды. Получаем

$$\mathrm{maj}(a, b, c) = bc + ac + ab$$

— три произведения по два множителя вместо четырёх по три. Вопрос в том, как быстро находить такие пары. В 1953 году инженер Bell Labs Морис Карно предложил рисовать таблицу истинности не столбцом, а прямоугольником, развивая похожую диаграмму Эдварда Вейча 1952 года. Строки и столбцы карты Карно подписаны не по порядку 00, 01, 10, 11, а так: 00, 01, 11, 10. При таком порядке любые две соседние клетки различаются только одним входом, а соседями считаются и клетки на противоположных краях, будто карта свёрнута в трубку.

Дальше работает глаз. Две соседние единицы склеиваются в произведение, где пропал один вход; четыре единицы прямоугольником — где пропали два. Нужно накрыть все единицы как можно меньшим числом как можно больших прямоугольников из 1, 2, 4 или 8 клеток; каждый прямоугольник даёт одно слагаемое. Выберите в виджете выше пример «большинство»: его единицы накрываются тремя группами по две клетки. Потом выберите «чётность». Единицы стоят в шахматном порядке, ни одна пара не склеивается, и упростить нечего. Для двухъярусной схемы чётность — самая неудобная функция, а понадобится она сразу же: младший разряд суммы трёх битов и есть чётность. Поэтому в сумматоре её считают цепочкой XOR.

Карта Карно удобна до четырёх-пяти входов, а в процессоре функций от десятков входов тысячи. Их упрощают программы синтеза схем, которые делают то же самое — ищут, что можно склеить, — только без карты и в огромных масштабах. Задача найти самую короткую формулу в общем случае трудна, и программы довольствуются хорошей, но не обязательно лучшей. Что значит «трудна» в точном смысле, мы узнаем в главе 57.

Сумматор

Вернёмся к сложению двух битов, с которого начиналась глава. Теперь его можно собрать: младший разряд — XOR, старший — «и». Такая деталь называется полусумматором.

Уровень 5. Полусумматор

Полусумматор делает только половину работы: при сложении столбиком в каждом разряде, кроме самого младшего, складываются три бита — два из чисел и перенос, пришедший справа. Сложим 6 и 7, то есть $0110_2 + 0111_2$:

Получилось $1101_2 = 13$. В разряде 1 сложились 1 и 1, вышел 0 и перенос; в разряде 2 — 1, 1 и перенос, вышло 1 и снова перенос. Деталь, которая складывает три бита и выдаёт сумму и перенос, называется полным сумматором. Её бит суммы — чётность трёх входов, $a \oplus b \oplus c$ (значком $\oplus$ пишут XOR), а перенос — функция большинства из раздела о картах Карно: перенос возникает, когда единиц хотя бы две. Собрать её проще всего из двух полусумматоров: первый складывает $a$ и $b$, второй прибавляет к их сумме входящий перенос, а переносы обоих объединяет «или». Оба переноса сразу случиться не могут — подумайте, почему.

Уровень 6. Полный сумматор

Проверим ту же сборку кодом. Утверждение в ячейке проверяет то, ради чего сумматор и строят: перенос весит два, сумма — один, и вместе они дают $a + b + c$.

Уровень 7. Стрелочник

Последняя деталь не складывает, а выбирает. Мультиплексор получает два сигнала A и B и управляющий бит S. При $S = 0$ на выход идёт A, при $S = 1$ — B. Это условный оператор, сделанный из проводов: a if s == 0 else b без всякого if. В формулах $y = \overline{s}a + sb$: из двух слагаемых открыто всегда одно, и оно пропускает свой вход.

Стрелочник понадобится в обеих следующих главах. В главе 30 восьмибитные мультиплексоры будут выбирать, какой результат — сложения, вычитания или «и» — отправить в регистр «Искры-8». В главе 31 схема того же рода по восьмибитному адресу выберет одну ячейку памяти из 256.

Теперь в коробке лежат «не», «и», «или», XOR, полусумматор, полный сумматор и мультиплексор, и внутри каждой детали — одни NAND. Это первые детали «Искры-8». Её процессор будет складывать восьмибитные числа, а у нас пока сумматор на один разряд с переносом.

Задачи

Четыре задачи на Python, где биты — целые 0 и 1. В каждой есть ограничение «чем можно пользоваться»: проверка читает ваш код и не пропустит запрещённого. Программа должна остаться схемой, только записанной на Python.

В коробке по-прежнему только nand. Напишите nor(a, b) («или-не»: 1, только когда оба входа 0), xnor(a, b) (равенство: 1, когда входы одинаковы) и implies(a, b) («если a, то b»: 0 только при $a = 1$, $b = 0$). Внутри функций — только вызовы nand и ваших собственных функций: никаких операторов, if и сравнений. И есть бюджет: на одно вычисление nor может вызвать nand не больше четырёх раз, xnor — пяти, implies — двух.

Заведите помощников из мастерской: not_(a) — один NAND, or_(a, b) — три. Тогда «или-не» — это «не» от «или»: как раз четыре.

Равенство — это перевёрнутый XOR. XOR из четырёх NAND разобран под уровнем 4 мастерской; плюс одно «не» — пять.

«Если a, то b» ложно в единственной строке: $a = 1$, $b = 0$. NAND тоже ложен в единственной строке — когда оба его входа равны 1. Что подать на его входы, чтобы это была строка $a = 1$, $b = 0$?

Импликация — NAND, у которого перевёрнут второй вход: он даёт 0 только при $a = 1$ и $\overline{b} = 1$. Компьютерный перебор всех схем показывает, что бюджеты в условии — точные минимумы: «или-не» не собрать меньше чем из четырёх NAND, равенство — меньше чем из пяти. Зато из NOR «или-не» получается одним вентилем, и наоборот, NAND из NOR стоит четыре: два универсальных вентиля зеркальны.

Напишите full_adder(a, b, c), который возвращает пару (s, carry) — сумму и перенос, так что $a + b + c = 2 \cdot carry + s$. А потом зеркальную деталь для вычитания столбиком: full_subtractor(a, b, borrow) возвращает (d, borrow_out) — разность и заём из старшего разряда, так что $a - b - borrow = d - 2 \cdot borrow\_out$. Например, $0 - 1 - 0$: занимаем двойку у соседа, $2 - 1 = 1$, значит, full_subtractor(0, 1, 0) равно (1, 1). Пользоваться можно только битовыми операциями &, |, ^: без +, -, сравнений и if.

Сумматор есть в тексте главы. Для вычитателя выпишите таблицу на восемь строк: для каждой тройки посчитайте $a - b - borrow$ и подберите d и borrow_out. Например, $0 - 1 - 1 = -2 = 0 - 2 \cdot 1$.

Столбец d совпадёт со столбцом суммы у сумматора. Столбец заёма впишите в виджет «функция → таблица → схема»: карта Карно найдёт три группы по две клетки.

Заём возникает, когда «вычитаемых» единиц ($b$ и $borrow$) больше, чем есть у $a$. Сравните с переносом сумматора (это функция большинства): что изменится, если перевернуть $a$? «Не» для бита без минуса — это a ^ 1.

Разность устроена так же, как сумма, — это чётность трёх битов. А заём — большинство из $\overline{a}$, $b$ и $borrow$: та же функция, что перенос, только с перевёрнутым $a$. Выходит, вычитатель — сумматор с одним «не». А в главе 30 выяснится, что отдельный вычитатель процессору вообще не нужен: благодаря дополнительному коду вычитает тот же сумматор.

Напишите mux(s, a, b): при $s = 0$ она возвращает a, при $s = 1$ — b. Без if, сравнений, арифметики, индексов и and/or/not — только &, |, ^, ~ и сдвиги. Подвох в том, что a и b — не обязательно биты: стрелочник в процессоре переключает сразу восемь проводов, поэтому mux должна работать и для байтов от 0 до 255 (а s — всегда 0 или 1). Затем соберите mux4(s1, s0, a, b, c, d): адрес $s_1 s_0$ = 00, 01, 10, 11 выбирает a, b, c или d. Внутри mux4 — только три вызова mux.

Для битов работает формула $y = \overline{s}a + sb$. Проверьте на байте: при $s = 1$ выражение s & b оставляет от b только младший бит. Нужна маска — восемь копий бита s: 0b11111111 при $s = 1$ и ноль при $s = 0$.

Маску можно размножить сдвигами: m = s | (s << 1) — два бита, потом m | (m << 2) — четыре, потом ещё раз. Дальше (a & ~m) | (b & m): где маска — единицы, проходит b, где нули — a.

Для mux4 младший бит адреса выбирает внутри пар (a или b, c или d), а старший — между парами.

В железе маске соответствуют восемь проводов, на которые разведён один управляющий бит: сигнал выбора усиливают и подают сразу на восемь одинаковых стрелочников, по одному на разряд. mux4 — маленькое дерево: два стрелочника на нижнем ярусе, один на верхнем. Для 256 входов понадобится восемь ярусов; так по восьмибитному адресу выбирают ячейку памяти, о которой речь пойдёт в главе 31.

Ответственные узлы — в бортовых компьютерах, на атомных станциях — иногда утраивают: три одинаковых блока считают одно и то же, а схема-голосовалка выдаёт то, что сказали хотя бы двое. Если один блок сломался, двое других его перекричат. Напишите эту голосовалку: majority(a, b, c) возвращает 1, когда единиц среди входов хотя бы две, — только битовыми операциями, без +, сравнений и if. Потом совет из пяти: majority5(a, b, c, d, e) — только вызовами majority. Никаких операторов в ней, но передавать в majority константы 0 и 1 можно.

Для трёх входов формула получена в разделе о картах Карно: $ab + bc + ac$.

Выясните, что делают majority(x, y, 0) и majority(x, y, 1). С этими двумя «деталями» пятёрку можно собрать по рецепту из доказательства универсальности: «или» по всем тройкам из пяти, внутри каждой — «и».

Решение по рецепту длинное. Короче так: сначала проголосуют трое — m = majority(a, b, c). Если $d$ и $e$ не согласны между собой, их голоса гасят друг друга, и решает тройка. Если согласны, им нужен ещё один союзник из тройки: при $d = e = 1$ — хотя бы одна единица среди $a$, $b$, $c$, при $d = e = 0$ — хотя бы один ноль. Это можно записать четырьмя вызовами.

Четыре вызова — меньше нельзя, это проверено перебором всех схем. Почему это работает, видно из разбора случаев, если помнить, что $\mathrm{maj}(1, x, y) = x + y$, а $\mathrm{maj}(0, x, y) = xy$. При $d = e = 1$ выход превращается в $a + b + c$: двум голосам «за» хватает одного из тройки. При $d = e = 0$ — в $abc$: нужны все трое. При $d \ne e$ голоса $d$ и $e$ гасят друг друга, и подстановка показывает, что выход совпадает с $m$ — решением тройки. Самая надёжная проверка та же, что для законов булевой алгебры: перебрать все 32 строки. Функция большинства нам уже встречалась — это перенос полного сумматора: перенос возникает, когда «за» хотя бы два слагаемых из трёх.

Куда дальше

Мастерская закончена: из детали, которая умеет только «не-и», собралось всё остальное, а доказательство обещает, что соберётся и любая другая логика. Самая ценная вещь в коробке — полный сумматор. Он складывает три бита: два разряда и перенос.

Но регистры «Искры-8» восьмибитные. Команда ADD R0, R1 должна складывать числа от 0 до 255, SUB — вычитать, и обе обязаны сообщать, не случился ли перенос и не вышел ли ноль. Вычитателя в коробке нет. А если поставить восемь сумматоров в ряд, перенос побежит от разряда к разряду, как щелчки по цепочке реле. Как с этим справиться, покажет сборочный цех главы 30. Там же отдел контроля качества разберётся, как в 1994 году ошибка в пяти клетках таблицы обошлась Intel в 475 миллионов долларов.