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