Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Назовём автоматом для голосования нечётного числа n человек логическую схему с n входами, принимающую истинное значение, когда больше половины входов принимают истинные значения, и ложное значение в противном случае.
Это очень естественное определение: если n входов представляют n человек, каждый из которых голосует либо "за" (истинное значение), либо "против" (ложное), на выходе мы получаем вариант, за который проголосовало большинство
Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
Решение данной задачи должно содержать текст доказательства. Примеры схем могут быть использованы в качестве пояснений, но засчитываться не будут.
Допустим, n=2k+1, k -- натуральное число. Тогда на выходе схемы должна быть 1, если на (k+1) входах имеется единица. Все случаи, когда единица находится более, чем на (k+1) входах, можно не рассматривать, они входят в те, где единица строго на (k+1) входах. Всего возможно С комбинаций, где С -- количество размещений из (2k+1) по (k+1), C=(2k+1)*(2k)*(2k-1)*...*(k+2) Если хотя бы одна такая комбинация входов дает на выходе единицу, то условие выполняется. То есть, все схемы, проверяющие соответствие таких комбинаций условию, можно подключить к выходу цепочкой через элементы ИЛИ. Пусть x(1), x(2), x(3),..,x(2k+1) -- логические входы. Тогда схемы, проверяющие каждую из комбинаций будут иметь вид: x(1) И x(2) И x(3) И ... И x(k) И x(k+1) x(1) И x(2) И x(3) И ... И х(л) И х(к+2) x(1) И x(2) И x(3) И ... И х(л) И х(к+3) и т.д. То есть, сначала задается какой-то набор из k входов и к этому набору добавляют каждый из (k+1) оставшихся входов по одному и цепочкой через элементы И подключают эти входы. Затем набор из k входов изменяют. Каждая такая схема проверяет одну комбинацию. То есть маленькая схема только из логических элементов И проверяет каждую из C комбинаций, затем выходы этих маленьких схем только через элементы ИЛИ подключают на общий выход.