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