Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Докажите, что можно построить автомат для голосования любого нечётного числа человек, используя только элементы голосования для трёх человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Разобьем все входы на тройки и объединим эти тройки элементов АВТ3. Затем полученные выходы также разобьем на тройки и объединим этим тройки элементами АВТ3. Повторяем до тех пор, пока не получим один выход. Если какие-то элементы не вошли в тройки, то их подключить на следующем шагу. Доказательство аналогично доказательству задачи 2, т.к. элемент АВТ3 работает как элемент И для своих входов, т.е. если x,y,z -- логические входы, то: x И y = АВТ3(x,y,z) x И z = АВТ3(x,y,z) y И z = АВТ3(x,y,z) Кроме того, (x И y) ИЛИ z = АВТ3(x,y,z) (x И z) ИЛИ y = АВТ3(x,y,z) (y И z) ИЛИ x = АВТ3(x,y,z) то есть указанная схема эквивалента схеме только из элементов И и ИЛИ, а возможность построения такой схемы доказана в №2.