Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
За круглым столом сидит n>2 человек. Каждый из них либо рыцарь, либо лжец. Рыцари всегда говорят только правду, а лжецы всегда лгут. Опишите способ построения логической схемы c n входами, которая принимает значение истина тогда и только тогда, когда каждый из сидящих за столом может произнести фразу «Оба моих соседа лжецы».
На логической схеме входы соответствуют людям: нули обозначают лжецов, а единицы рыцарей. Разрешается использовать логические элементы AND (и), OR (или), NOT (не) и XOR (исключающее или). Соседние входы соответствуют соседним людям, кроме того, поскольку стол круглый, самый верхний вход будем считать соседним с самым нижним.
Для иллюстрации Вашего решения Вы можете использовать манипулятор с тремя входами. Однако, оцениваться будет в первую очередь текст решения, автоматической проверки не производится.
Пусть k это номер произвольного входа, а правила применённые к этому входу нужно будет применить ко всем остальным. 1 шаг. Для входа k свяжем командой XOR этот вход и вход выше этого (если k самый верхний, то свяжем его с самым нижним). 2 шаг. Для входа k свяжем командой XOR этот вход и вход ниже этого (если k самый нижний, то свяжем его с самым верхним). 3 шаг. Связываем выходы команд XOR с помощью команды OR. 4 шаг. Накладываем отрицание на вход k и связываем его и выход из команды OR командой AND. 5 шаг Для входа k свяжем командой XOR этот вход и вход выше этого (если k самый верхний, то свяжем его с самым нижним). 6 шаг. Для входа k свяжем командой XOR этот вход и вход ниже этого (если k самый нижний, то свяжем его с самым верхним). 7 шаг. Связываем выходы команд XOR с помощью команды AND. 8 шаг. Связываем выход команды AND (из шага 7) и входа k с помощью команды AND. 9 шаг. Связываем команды AND (8 шаг) и AND (4 шаг) командой OR 10 шаг. Соединяем выход команды OR и вход вывода.