Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство
Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но засчитываться не будут.
Для каждого нечетного числа n четко определено минимальное число людей, которые должны точно проголосовать "за" для того, чтобы значение функции стало истинным. Это необходимое условие. Соответственно, можно перебрать все варианты групп людей из этого количества человек, которые все будут соединены элементами "и", а между собой группы будут соединены элементами "или". Соответственно, если нашлась хоть одна минимальная необходимая группа проголосовавших "за", то функция примет истинное значение. Если такой группы людей не найдется, то ложное.