Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо «за» (истинное значение), либо «против» (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Докажите, что можно построить автомат для голосования любого нечётного числа человек, используя только элементы голосования для трёх человек.
Докажем это по индукции. База содержится в условии.
Для перехода от к воспользуемся индукционным предположением. Рассмотрим следующие элементы для голосования человека: все, кроме первого и второго; все, кроме второго и третьего и все, кроме первого и третьего человека.. Выходы каждого из этих элементов отождествим с входами четвёртого элемента для голосования трёх человек. Полученная схема почти всегда будет давать результат, совпадающий с голосованием большинства. Единственное исключение — ситуация, в которой большинство состоит ровно из человека и в это большинство входят одновременно люди с