Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство.
Докажите, что 2n элементов И и ИЛИ достаточно, чтобы построить автомат для голосования n человек (n – нечётное).
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но отдельно засчитываться не будут.
Из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа(n) человек. Для этого нужно поделить число человек(n) на два (с округлением в большую сторону к примеру 5/2=3) и взять получившееся значение за число N, после чего при помощи элемента И связать каждые N элементов. Так как число N больше половины, если хоть одна связь И окажется истинной, на выходе мы должны получить истинное значение=> нам нужно связать все получившиеся И элементами ИЛИ и направить получившееся значение на выход.=>Для связи N человек нам понадобится N/2 (с округлением в большую сторону) элементов И, обозначим это число как k.Кол во нужных связей И для n человек определяется по формуле F(N)=N+F(N-1)+2*(F(N-1)+F(N-2)+...+F(1)) где F(1)=1(значит для семи человек, когда N=4,F(4)=4+3+2+1+2*(3+2+1+2+1+1)=30)=> необходимое число элементов И=F(N)*k(с округлением в большую сторону), т.к нам нужно применить ИЛИ ко всем связям И их нужно столько же сколько и связей(F(N)=N+F(N-1)+2*(F(N-1)+F(N-2)+...+F(1))=> число элементов И и ИЛИ, чтобы построить автомат для голосования n человек (n – нечётное) нужно F(N)*k+F(N), а F(N)*k+F(N) всегда меньше 2^n