Введение в схемы, автоматы и алгоритмы

         

что минимальная схема для сложения


Задача 2.1. Докажите пункт (2) теоремы 2.1.
Задача 2.2. Докажите, что минимальная схема для сложения имеет сложность L(+) = 4.
Задача 2.3. Используя схему SUMn, постройте схему, реализующую операцию вычитания двух n-разрядных двоичных чисел: d =a - b (при условии, что a
b). Оцените сложность полученной схемы.
Задача 2.4. Определите глубину схем S+, Sodd, SUM1 и SUMn.
Задача 2.5. Два игрока независимо выбирают одно из четырех чисел от 0 до 3. Первый игрок выигрывает, если выбранные числа совпадают. Постройте схему, определяющую выигрыш 1-го игрока. Ее входы x1,x2 представляют число, выбранное 1-ым игроком, а y1,y2 - число, выбранное 2-ым игроком. Реализуемая функция F(x1,x2,y1,y2) равна 1 тогда и только тогда, когда x1=y1 и x2 =y2.
Задача 2.6. Постройте схему, определяющую результат голосования в комитете, состоящем из трех членов и председателя. В случае равенства голосов, голос председателя является решающим.
Задача 2.7. Пусть наборы аргументов булевой функции от трех аргументов упорядочены лексикографически, а ее значения задаются последовательностью 8 нулей и единиц. Постройте схемы, реализующие следующие функции.
  • f1=(1111 1011),
  • f2=(1001 1001),
  • f3 =(0011 1001).


Содержание раздела