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