Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо «за» (истинное значение), либо «против» (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Постройте автомат для голосования трёх человек, используя логические элементы И и ИЛИ.
Один из возможных примеров решения изображен на схеме ниже:
Также на схеме видно, как работает этот элемент на конкретном наборе значений (ИСТИНА, ЛОЖЬ, ИСТИНА).
Мы перебираем все возможные пары входов и, если хотя бы на одном из них принимается истинное значение, логическая схема выдаёт истинный результат.
Более экономный, с точки зрения количества используемых символов, пример приведён далее:
Данная схема построена из следующих соображений: если первый вход принимает истинное значение, нам достаточно истинности любого из двух оставшихся; в противном случае требуется истинность обоих оставшихся.
Ответ: см. рис.
где m натуральное число. Проще всего построить такую схему из тех же соображений, из которых был построен пример №1 в предыдущей задаче: переберём все возможные наборы по m входов, объединив каждый из наборов при помощи элементов И. Затем соединим полученные части схемы при помощи элементов ИЛИ.