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