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