Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо «за» (истинное значение), либо «против» (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Постройте автомат для голосования пяти человек, используя только элементы голосования для трёх человек.
Пронумеруем голосующих числами от 1 до 5. Возьмём элементы для голосования трёх человек с номерами 1, 2 и 3; 1, 2 и 4; 1, 2 и 5. Выходы каждого из этих элементов отождествим с входами четвёртого элемента для голосования трёх человек. Заметим, что полученная схема выдаёт верный результат для голосования пяти человек для всех ситуаций, кроме двух: когда люди с
Создадим ещё две аналогичных схемы: схему, которая «ошибается» только при распределении голосующих 2 и 3 против 1, 4
где m натуральное число. Проще всего построить такую схему из тех же соображений, из которых был построен пример №1 в предыдущей задаче: переберём все возможные наборы по m входов, объединив каждый из наборов при помощи элементов И. Затем соединим полученные части схемы при помощи элементов ИЛИ.