Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство
Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но засчитываться не будут.
Пусть а[i] - значение на i-м входе. Автомат для голосования для n входов, значении Истина на входе показывает, что нашлось хотя бы одно сочетание входов со значением Истина, содержащее в себе более (n-1)/2 элементов, т.е. из всех сочетаний С из n по ((n-1)/2+1) существует хотя бы одно,на каждом входе элемента которого стоит значение Истина. Переведем это в вид формулы: a[1]^a[2]^a[3]...a[((n-1)/2)+1] + a[2]^a[3]^a[4]^...a[((n-1)/2)+2] + ..... и т.д. В этом выражении используются только элементы И и ИЛИ, т.е при любом нечетном n можно построить автомат для голосования только с помощью элементов И и ИЛИ.