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


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

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

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

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

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

Ре­ше­ние.

Пусть ко­ли­че­ство че­ло­век равно 2 m минус 1, где m на­ту­раль­ное число. Проще всего по­стро­ить такую схему из тех же со­об­ра­же­ний, из ко­то­рых был по­стро­ен при­мер №1 в преды­ду­щей за­да­че: пе­ре­берём все воз­мож­ные на­бо­ры по m вхо­дов, объ­еди­нив каж­дый из на­бо­ров при по­мо­щи эле­мен­тов И. Затем со­еди­ним по­лу­чен­ные части схемы при по­мо­щи эле­мен­тов ИЛИ.

1

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


2

До­ка­жи­те, что 2n эле­мен­тов И и ИЛИ до­ста­точ­но, чтобы по­стро­ить ав­то­мат для го­ло­со­ва­ния n че­ло­век (n  — нечётное).