В очень далеком 1997 году я опубликовал в «Компьютерре» статью под названием «Этюд о двух отрицаниях, или Точка опоры». Статья была посвящена задаче о реализации логических операторов AND, OR, NOT с ограничением на число используемых NOT. А именно, я считал тогда (и утверждал это в статье), что любое количество входов можно инвертировать («перевернуть») с помощью всего двух элементов NOT, если количество AND и OR не ограничено. А теперь я так не считаю, потому что в той моей статье была допущена (глупая, хотя и очень поучительная) ошибка.
Статья начиналась с конструктивного доказательства следующей «леммы о трех входах»
Значения трех бинарных величин можно заменить на противоположные, использовав только две операции NOT. (При этом разрешается использовать любое число операций AND и OR, а также любое число вспомогательных величин).
А после доказательства леммы был примерно такой вывод.
«А теперь рассмотрим такую процедуру: пользуясь доказанной выше леммой, заменим первые три инвертора на два. Добавим к ним следующий инвертор. Снова воспользуемся леммой и уменьшим число инверторов до двух. Потом возьмем следующий инвертор и т.д. - до тех пор, пока у нас не останется всего два инвертора.»
Кажется, всё верно, не так ли? Если лемма доказана (а это на самом деле верная лемма, и у меня было верное ее доказательство), то ведь математическую индукцию никто не отменял? И тем не менее, вывод ошибочен. Возможно, чтобы его ошибочность стала более наглядной, мне стоит повторить доказательство леммы? Ну что ж, поехали. Я изменю это доказательство только стилистически.
Пусть даны бинарные величины X, Y, Z. Выходные величины будем обозначать буквами X', Y', Z', а вспомогательные - другими буквами. Вместо OR я буду писать «+», а AND буду рассматривать как умножение (собственно, на этом базируется вся булева алгебра). И только NOT я буду писать буквами, чтоб он был заметен.
Алгоритм INVERT3.
1. S1 := X+Y+Z
2. S2 := XY+YZ+ZX
3. S3 := XYZ
4. A := NOT (S2)
5. C := NOT (AS1 + S3)
6. X' := AY + AZ + AC + CYZ
7. Y' := AX + AZ + AC + CXZ
8. Z' := AX + AY + AC + CXY
Докажем, что мы получили именно то, что хотели получить. Первые три действия вычисляли симметрические многочлены от X,Y,Z. Нетрудно убедиться, что их результаты имеют следующий очень простой смысл: Si (i=1,2,3) равно 1 тогда и только тогда, когда [дальше я буду писать в таких случаях iff] не менее чем i входов равны 1. Так как NOT(S2) S1=1 iff S1=1 и S2=0, то это бывает iff ровно один вход равен 1. Следовательно, AS1+S3=1 iff «один или три входа равны 1», а C=1 iff «0 или 2 входа равны 1».
Операции 6-8 аналогичны друг другу, поэтому достаточно разобраться с первой из них. AY=1 iff Y=1 и «не более одного входа равно 1». То есть когда три входа равны (0,1,0). Аналогично AZ=1 только на наборе (0,0,1). AC=1 iff одновременно A и C равны 1, а это бывает только когда нет входов, равных 1, то есть на наборе (0,0,0). И, наконец СYZ = 1 iff 2 входа равны 1, причем Y=Z=1, то есть только на наборе (0,1,1). Таким образом, сумма четырех выписанных слагаемых принимает значение 1 на наборах (0,0,0), (0,0,1), (0,1,0) и (0,1,1), то есть равна 1 iff X=0. Иначе говоря, эта сумма равна NOT(X). Аналогично, результаты операций 7 и 8 равны NOT(Y) и NOT(Z) соответственно.
Итак, лемма доказана. В ней ошибок нет. Где же тогда была ошибка?
Если индукционное доказательство приводит к неверному утверждению, а в базе индукции ошибок нет, значит, ошибки есть в индукционном переходе. И действительно, если мы применим базу к первым трем входам, то для инвертирования их нам нужно будет вычислить отрицания от S2 и AS1+S3. Но одно из этих выражений содержит внутри себя уже построенное отрицание другого, так что мы не можем считать их независимыми входами. В частности, мы не можем с самого начала вычислять симметрические выражения от двух этих выражений и третьего входа.
Но, может быть, существует другой алгоритм, в котором два инвертируемых промежуточных выражения будут независимыми? Увы, тоже нет (доказать это не очень трудно, но я знаю только переборное доказательство).
А сколько всего операций NOT потребуется для инвертирования, например, четырех входов? Три штуки. А для инвертирования пяти, шести, семи входов? Тоже три! Точно три? Да, точно. Следите за руками. Я запишу алгоритм, а справа от номера шага буду в квадратных скобках фиксировать, при каком количестве единиц среди входов вычисляемая величина будет равна 1. Входы я буду обозначать буквами X1, …, X7.
Алгоритм INVERT7.
1. S1 := X1 + … + X7 [1,2,3,4,5,6,7]
2. S2 := X1X2 + … + X6X7 [2,3,4,5,6,7]
3. S3 := X1X2X3 + … + X5X6X7 [3,4,5,6,7]
4. S4 := X1X2X3X4 + … + X4X5X6X7 [4,5,6,7]
5. S5 := X1X2X3X4X5+ … + X3X4X5X6X7 [5,6,7]
6. S6 := X1X2X3X4X5X6 + … + X2X3X4X5X6X7 [6,7]
7. S7 := X1X2X3X4X5X6X7 [7]
8. A1 := S4 [4,5,6,7]
9. B1 := NOT (A1) [0,1,2,3]
10. A2 := B1S2 + S6 [2,3,6,7]
11. B2 := NOT (A2) [0,1,4,5]
12. A3 := B1B2S1 + B1S3 + B2S5 + S7 [1,3,5,7]
13. B3 := NOT(A3) [0,2,4,6]
Кроме того, введем обозначения для симметрических выражений, содержащих все переменные кроме X1, а именно, P0=1, P1 := X2 + … + X7, P2 := X2X3 + … + X6X7, …, P6 := X2X3X4X5X6X7.
Тогда
X1' = B1B2B3P0 + B1B2A3P1 + B1A2B3P2 + B1A2A3P3 + A1B2B3P4 + A1B2A3P5 + A1A2B3P6
В этом выражении множители вида {A,B}1{A,B}2{A,B}3 выделяют строго «своё» количество входов, равных 1 (в соответствии с двоичной записью числа i), а умножение на Pi гарантирует, что среди этих входов не окажется вход X1. [Часть этих выражений можно было бы сократить, например, A1A2 это просто S6, но я не стал этого делать ради единообразия записи слагаемых.]
Выражения для X2', …, X7' строятся аналогично.
Контрольный вопрос: для какого наибольшего количества входов будет достаточно четырех инвертирований?
Комментариев нет:
Отправить комментарий