Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 5
Текст из файла (страница 5)
. . ) + p1 B(p3 , . . . ) + p2 C(p3 , . . . ) + D(p3 , . . . ).При этом многочлен A(p3 , . . . ) заведомо отличен от нуля, поэтомуможно так подставить константы вместо p3 , . . . , pn , чтобы первоеслагаемое не обратилось в нуль. Тогда получим либо p1 p2 + d, либоp1 p2 + p1 + d, либо p1 p2 + p2 + d, либо p1 p2 + p1 + p2 + d. Свободныйчлен d можно менять, если нужно (у нас есть отрицание), так чтополучается либо p1 p2 (конъюнкция, и всё доказано), либо p1 p2 +p1 == p1 (p2 + 1) = p1 ∧ ¬p2 (убираем отрицание, получаем конъюнкцию,всё доказано), либо p1 p2 + p2 (аналогично), либо p1 p2 + p1 + p2 == (1 + p1 )(1 + p2 ) − 1 = ¬(¬p1 ∧ ¬p2 ) = p1 ∨ p2 (дизъюнкция, всёдоказано). 22Логика высказываний[гл.
1]1.3. Схемы из функциональных элементовФормулы представляют собой способ записи композиции функций. Например, если мы сначала применяем функцию f , а потомфункцию g, это можно записать формулой g(f (x)). Но есть и другойспособ: можно изобразить каждую функцию в виде прямоугольникас «входом» и «выходом» и соединить выход функции f со входомфункции g (рис. 1).f -gg(f (x))Рис. 1. Два способа изобразить композицию g ◦ f .Такое представление отнюдь не является чисто теоретическим.Уже больше полувека электронная промышленность выпускает микросхемы, которые выполняют логические операции. Такая микросхема имеет электрические контакты, напряжение на которых кодируетлогические значения И и Л. Конкретное напряжение зависит от типасхемы, но обычно это несколько вольт, и высокий потенциал (относительно заземления) считается единицей, а низкий нулём.Одной из типичных схем является схема И-НЕ, она имеет двавхода и один выход.
Сигнал на выходе является отрицанием конъюнкции сигналов на входе. Другими словами, на выходе появляетсявысокий потенциал (сигнал 1) тогда и только тогда, когда на одном из входов потенциал низкий (0). Из такой схемы легко получитьсхему НЕ (изменяющую уровень сигнала на противоположный), соединив проводом два входа. При этом на оба входа поступает один итот же сигнал, и операция И его не меняет (p∧p = p), а НЕ меняет напротивоположный.
Взяв два элемента И-НЕ и используя второй изних в качестве элемента НЕ, инвертирующего сигнал с выхода первого элемента, получаем схему, которая реализует функцию И. А еслипоставить два элемента НЕ перед каждым из входов элемента И-НЕ,получим схему, реализующую функцию ИЛИ: ¬(¬p ∧ ¬q) ↔ (p ∨ q).Теорема 3 о полноте системы связок теперь гарантирует, что любую булеву функцию можно реализовать в виде схемы.
Надо иметьв виду, однако, что предлагаемая в её доказательстве конструкция(дизъюнктивная нормальная форма) имеет скорее теоретический интерес, поскольку приводит к схемам очень большого размера дажедля простых функций (если число аргументов велико). Например,[п. 3]Схемы из функциональных элементов23схема, сравнивающая два 16-битных числа, должна иметь 32 входаи поэтому в её реализации с помощью дизъюнктивной нормальнойформы будет порядка 232 элементов — что мало реально.
(Междутем такую схему можно построить гораздо проще, из несколькихсотен элементов.)Поэтому вопрос о том, сколько элементов нужно для реализации той или иной функции, представляет большой интерес — какпрактический, так и философский. (Одна из центральных проблемматематики и информатики, так называемая «проблема перебора»,может быть сформулирована в этих терминах.)Мы сейчас дадим более формальное определение схемы и реализуемой ей булевой функции. Но прежде всего ответим на такойвопрос — почему мы вообще говорим о схемах? Ведь можно записать композицию булевых функций в виде формулы, не будет ли этото же самое?Оказывается, не совсем, и разницу легко увидеть на примере(рис. 2).g1fhh(g1 (f (x)), g2 (f (x)))g2Рис.
2. Элемент входит в формулу дважды.Здесь один и тот же элемент схемы (f ) приходится указывать вформуле дважды, поскольку его выход используется в качестве входа двух других элементов. Схемы, в которых такого ветвления нет(на практике ветвление вполне возможно, хотя и ограничено «нагрузочной способностью выхода», как говорят инженеры), как рази соответствуют формулам. Но в общем случае полученная из данной схемы формула может быть длинной, даже если схема содержитнебольшое число элементов, поскольку число копий может расти экспоненциально с ростом глубины схемы.Хотя идея построения схемы из функциональных элементов, реализующих булевы функции, достаточно наглядна, дадим более формальное определение.
Фиксируем некоторый набор булевых функций B. Пусть имеется n булевых (принимающих значения 0 и 1)переменных x1 , . . . , xn , называемых входами. Пусть также имеется24Логика высказываний[гл. 1]некоторое число булевых переменных y1 , . . . , ym , называемых проводниками. Пусть для каждого проводника схемы задана булева функция из B, выражающая его значение через другие проводники и входы.
При этом требуется, чтобы не было циклов (цикл образуется,когда yi зависит от yj , которое зависит от yk , . . . , которое зависитот yi ). Пусть, кроме того, среди проводников выделен один, называемый выходом. В таком случае говорят, что задана схема из функциональных элементов в базисе B с n входами. Число m называютразмером схемы. (С точки зрения инженера размер — это число использованных элементов, а базис B — это ассортимент доступныхему элементов.)Отсутствие циклов гарантирует, что есть проводник, зависящийтолько от входов (иначе можно было бы найти цикл: возьмём какой-то проводник, затем возьмём тот проводник, от которого он зависит и т.
д.). Значение этого проводника, таким образом, однозначноопределяется сигналами на входах. Среди оставшихся проводниковтакже нет цикла, поэтому можно найти один из них, зависящий только от уже известных, и определить его значение. Перенумеровав проводники в таком порядке, мы можем записать последовательностьприсваиванийy1 := f1 (. . .
);y2 := f2 (. . . );.............ym := fm (. . . ),в правых частях которых стоят функции из B, применённые ко входам и уже найденным значениям. При этом можно считать, что результат схемы есть ym (как только результат получен, дальнейшиеприсваивания уже не нужны). Такая программа определяет ym приизвестных значениях входов, и тем самым вычисляет некоторую булеву функцию.Теперь набор булевых функций B можно назвать полным, еслилюбая булева функция может быть задана схемой из B-элементов(существует программа, её вычисляющая, при этом в правых частяхприсваиваний стоят функции из B).
Ясно, что это определение полноты равносильно прежнему, то есть возможности записать булевуфункцию в виде формулы со связками из B (как мы говорили, разница только в том, что один и тот же элемент будет фигурироватьв формуле многократно).[п. 3]Схемы из функциональных элементов25Сложностью булевой функции f относительно B называют минимальный размер схемы из B-элементов, вычисляющей функцию f .Его обозначают sizeB (f ).Теорема 7. Пусть B1 и B2 — два полных набора булевых функций.Тогда соответствующие меры сложности отличаются не более чемна постоянный множитель: найдётся такое число C, что sizeB1 (f ) 66 C sizeB2 (f ) и sizeB2 (f ) 6 C sizeB1 (f ) для любой функции f .
Утверждение почти очевидно: поскольку наборы B1 и B2 полны, то каждая функция одного из наборов может быть вычисленакакой-то схемой, составленной из элементов другого набора. Теперьможно взять в качестве C наибольший размер таких схем, и неравенства будут выполняться: каждую строку программы можно заменить на C (или меньше) строк с использованием функций другогонабора.
Что можно сказать о сложности произвольной булевой функцииn аргументов? Следующая теорема показывает, что она экспоненциально зависит от n (для «наугад взятой» функции).Теорема 8. (а) Пусть c > 2. Тогда сложность любой булевой функции n аргументов не превосходит cn для всех достаточно больших n.(б) Пусть c < 2. Тогда сложность большинства булевых функций nаргументов не меньше cn для всех достаточно больших n. Прежде всего заметим, что по предыдущей теореме не имеетзначения, какой полный базис выбрать (изменение значения c болеесущественно, чем умножение сложности на константу).Первое утверждение теоремы очевидно: размер схемы, реализующей дизъюнктивную нормальную форму с n переменными, естьO(n2n ), поскольку имеется не более 2n конъюнктов размера O(n).(Напомним смысл O-обозначений: O(n2n ) означает, что существуетверхняя оценка вида Cn2n для некоторой константы C.) Осталосьзаметить, что O(n2n ) < cn при достаточно больших n (напомним,что c > 2).Чтобы доказать второе утверждение, оценим число различныхсхем (скажем, в базисе И, ИЛИ, НЕ) размера N с n аргументами.Каждая такая схема может быть описана последовательностью изN присваиваний, выражающих одну из переменных через предыдущие.
Для каждого присваивания есть не более 3(N + n)2 вариантов(три типа операций — конъюнкция, дизъюнкция, отрицание, и каждый из не более чем двух аргументов выбирается среди не более чемN +n вариантов). Отсюда легко получить оценку 2O(N log N ) на числовсех функций сложности не более N (считая N > n).26Логика высказываний[гл. 1]nВсего булевых функций с n аргументами имеется 22 . Из сравнения этих формул видно, что что при c < 2 и при достаточно большихn булевы функции сложности меньше cn составляют меньшинство,nnnтак как 2O(c log c ) много меньше 22 . 12. Проведите вторую часть рассуждения более подробно и покажите,что при некотором ε > 0 сложность большинства булевых функций с nаргументами не меньше ε2n /n.Верхнюю оценку теоремы 8 можно усилить и показать, что сложность любой булевой функции n аргументов не превосходит O(2n /n).13.
(а) Покажите, что можно построить схему размера O(2m ) с 2mвыходами, реализующую все 2m возможных конъюнктов длины m (длякаждого — свой выход). (Указание: такую схему можно построить инmдуктивно.) (б) Покажите, что можно построить схему размера O(22 )2m2mбулевых функций m аргуменвыходами, реализующую все 2с 2тов. (Указание: эту схему также можно построить индуктивно.) (в) Пустьϕ(x1 , . .
. , xk , y1 , . . . , yl ) — булева функция, аргументы которой разбиты надве группы. Покажите, что её можно записать в виде дизъюнкции 2k членов, каждый из которых имеет вид C(x1 , . . . , xk ) ∧ D(y1 , . . . , yl ), где C —конъюнкт, а D — произвольная булева функция. Вывести отсюда упомянутую выше оценку O(2n /n). (Указание: разумно положить k = n − log n + c,l = log n − c. См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
