сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Назовём ав­то­ма­том для го­ло­со­ва­ния нечётного числа n че­ло­век ло­ги­че­скую схему с n вхо­да­ми, при­ни­ма­ю­щую ис­тин­ное зна­че­ние, когда боль­ше по­ло­ви­ны вхо­дов при­ни­ма­ют ис­тин­ные зна­че­ния, и лож­ное зна­че­ние в про­тив­ном слу­чае.

Это очень есте­ствен­ное опре­де­ле­ние: если n вхо­дов пред­став­ля­ют n че­ло­век, каж­дый из ко­то­рых го­ло­су­ет либо «за» (ис­тин­ное зна­че­ние), либо «про­тив» (лож­ное), на вы­хо­де мы по­лу­ча­ем ва­ри­ант, за ко­то­рый про­го­ло­со­ва­ло боль­шин­ство.

Име­ет­ся ло­ги­че­ский эле­мент с тремя вхо­да­ми, ко­то­рый даёт на вы­хо­де 1, если число еди­ниц на входе боль­ше числа нулей (ре­а­ли­зу­ет функ­цию го­ло­со­ва­ния для трёх че­ло­век).

До­ка­жи­те, что можно по­стро­ить ав­то­мат для го­ло­со­ва­ния лю­бо­го нечётного числа че­ло­век, ис­поль­зуя толь­ко эле­мен­ты го­ло­со­ва­ния для трёх че­ло­век.

Спрятать решение

Ре­ше­ние.

До­ка­жем это по ин­дук­ции. База n=3 со­дер­жит­ся в усло­вии.

Для пе­ре­хо­да от 2 n минус 1 к 2 n плюс 1 вос­поль­зу­ем­ся ин­дук­ци­он­ным пред­по­ло­же­ни­ем. Рас­смот­рим сле­ду­ю­щие эле­мен­ты для го­ло­со­ва­ния 2 n минус 1 че­ло­ве­ка: все, кроме пер­во­го и вто­ро­го; все, кроме вто­ро­го и тре­тье­го и все, кроме пер­во­го и тре­тье­го че­ло­ве­ка.. Вы­хо­ды каж­до­го из этих эле­мен­тов отож­де­ствим с вхо­да­ми четвёртого эле­мен­та для го­ло­со­ва­ния трёх че­ло­век. По­лу­чен­ная схема почти все­гда будет да­вать ре­зуль­тат, сов­па­да­ю­щий с го­ло­со­ва­ни­ем боль­шин­ства. Един­ствен­ное ис­клю­че­ние  — си­ту­а­ция, в ко­то­рой боль­шин­ство со­сто­ит ровно из n плюс 1 че­ло­ве­ка и в это боль­шин­ство вхо­дят од­но­вре­мен­но люди с но­ме­ра­ми 1, 2 и 3. Со­зда­дим ещё две ана­ло­гич­ных схемы, ко­то­рые «оши­ба­ют­ся» в дру­гих си­ту­а­ци­ях. Тогда, если мы замкнём их вы­хо­ды на вход ещё од­но­го эле­мен­та для го­ло­со­ва­ния трёх че­ло­век, по­лу­чен­ный ре­зуль­тат все­гда будет верен.

1

По­строй­те ав­то­мат для го­ло­со­ва­ния трёх че­ло­век, ис­поль­зуя ло­ги­че­ские эле­мен­ты И и ИЛИ.


2

До­ка­жи­те, что из эле­мен­тов И и ИЛИ можно по­стро­ить ав­то­мат для го­ло­со­ва­ния лю­бо­го нечётного числа че­ло­век.