Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство
Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но засчитываться не будут.
Пусть всего у нас n=2m+1 участников(входов). Сделаем "И" для всех наборов из m+1 участника (т.е. попарное "И" пока не останется один выход)(пример для 5 приведен(для первых 3 участников)). Потом сделаем "ИЛИ" для всех получившихся наборов из "И"(из m+1 участника). Данная конструкция будет возвращать 1 если хотя бы один из наборов из m+1 участника возвращает 1, т.е. хотя-бы один из наборов из m+1 участника состоит только из 1, т.е больше половины голосов 1. Предложенная конструкция решает задачу для любого нечетного кол-ва участников.