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


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

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

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

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

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

Ре­ше­ние.

Один из воз­мож­ных при­ме­ров ре­ше­ния изоб­ра­жен на схеме ниже:

Также на схеме видно, как ра­бо­та­ет этот эле­мент на кон­крет­ном на­бо­ре зна­че­ний (ИС­ТИ­НА, ЛОЖЬ, ИС­ТИ­НА).

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

Более эко­ном­ный, с точки зре­ния ко­ли­че­ства ис­поль­зу­е­мых сим­во­лов, при­мер при­ведён далее:

Дан­ная схема по­стро­е­на из сле­ду­ю­щих со­об­ра­же­ний: если пер­вый вход при­ни­ма­ет ис­тин­ное зна­че­ние, нам до­ста­точ­но ис­тин­но­сти лю­бо­го из двух остав­ших­ся; в про­тив­ном слу­чае тре­бу­ет­ся ис­тин­ность обоих остав­ших­ся.

 

Ответ: см. рис.

1

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