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