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