Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство
Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но засчитываться не будут.
Для решения такой задачи для n человек нам нужно знать, какое число участников является большинством. Большинством будут считаться все числа от (n+1)/2 до n. Строим таблицу истинности. Далее нам нужно описать с помощью конъюнкции каждый вариант входного набора и связать все варианты дизъюнкцией, но для такого решения не имеет смысла описывать варианты набора входных данных, где значений "Истина" больше, чем (n+1)/2, так как такие варианты будут включать в себя те варианты с количеством значений "Истина" (n+1)/2 Например для n=3 и входов с названиями a, b, c это будет - bc+ac+ab