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