Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.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 комбинаций, затем выходы этих маленьких схем только через элементы ИЛИ подключают на общий выход.