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