XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 72
Текст из файла (страница 72)
Используя законы де Моргана, получим х1х2 Ч х1хз Ч х2хз = х1х2 х1хЗ х2хз. Учитывая,что х = хЩ 1, будем иметь х1х2 *1хЗ х2хЗ =(х1х291)(х1х391)(х2х391)91= = х1Х2хЗ Щ х1х2ХЗ Щ х1х2хз Щ х\х2 Щ х1Х2хз Щ Щ х1х3 Щ х2х3 Щ 1 Щ 1 = х1х2 Щ х1ХЗ Щ х2хз (напомним, что сумма по модулю л любого четного числа равных слагаемых равна 0). Итак, у1 = х1х2 9 х1хз Щ х2хз = х1Х2 Щ хз (х1 Щ х2). СФЭ для булеза оператора, заданного в табл. 6.9, над базисом Жегалкина приведена на рис. 6.27.
463 а8. .8. Сзиыы иэ фуиициоиазьиых элемеигов хз хззхз уз-хз ®из~из уз = хзхз®(из ~из)хз Рис. 6.37 При проектировании СФЭ полезно иметь в виду число числовои раметр, называемыи ее сложностью. С лоззсносзззь СФЭ вЂ” это число ее вершин, не являющихся входами. Приведенная на рис. 6.27 СФЭ над базисом Жегалкина имеет сложность 6. Рассмотрим теперь СФЭ для того же оператора над стандартным базисом. По таблице (см.
табл. 6.9) строим СДНФ для функции 9г: рг = хз хгхз Ч хз хгхз '4 хъхгхг Ч хзхгхз. Карша Ка но ля зт " р для этой функции, изображенная на рис. 6.28, показывает что е н е ельзя минимизировать (точнее, записанная вьппе СДНФ и е Д и есть минимальная ДНФ для этой функции). о можно пойти по другому пути. Мы можем рассматривать табл. 6.9 как табли таблицу, определяющую чесанную булаву уннпию уг уг(хз,хг,хз,рз). Минны~акру~ эту Фунюппо по 6. БУЛЕВЫ ФУНКЦИИ хх01 х1хО 1ххО 111х Рис.
6.26 Рис. 6.26 карте Карно', изображенной на рис. 6.29, получаем Д2 = Х1Х2ХЗ Ч р1(Х1 Ч Х2 Ч ХЗ). СФЭ над стандартным базисом для рассматриваемого булева оператора приведена на рис. 6.30. Сложность этой СФЭ составляет 11. Заметим, что вершина, вычисляющая функцию 91, не является выходом. Рис. 6.30 *На этой карте мы лево обозначили наборы, на которых фувкцил принвмает значение О, проставив нули в соответствувицнх клетках.
Тем самым мы хотим еще раз зафиксировать внимание на том, что ке следует путать нули с прочерками: прочерк в клетке карты, задавнцей частичную фувкцвю, означает, что на данном наборе значение функции ве определено, т.е. не равно ни О, ви 1. б.б. О(емм вэ фуввввовваъвых эвемевзов 455 Булез оператор, рассмотренный в этом примере, вычисляет двухразрядную сумму (по модулю 2) трех одноразрядных слагаемых. Его можно считать также одноразрядным двоичным сумматором — функциональным блоком многоразрядного двоичного сумматора — для двух слагаемых. Тогда функция у( интерпретируется как „сигнал переноса" в старший разряд. На рис. 6.31 изображено „соединение" трех СФЭ (таких, как показано на рис.
6.30), с помощью которого вычисляется сумма двух трехрэзрядных двоичных чисел. На третий вход сумматора для младшего разряда подается константа О, а „сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом. <з> <з> 1 2 (2) (2> 1 ~2 в в 0 Вз <з> <2> У> Уз 2> И> Уз Рис. 6.31 (1> (1) У< Уз Замечание 6.11. Если мы проектируем СФЭ над стандартным базисом и хотим минимизировать ее сложность, то нам необходимо прежде всего построить соответствующую минимальную ДНФ. В этом случае мы можем принять во внимание еще один критерий, по которому минимизируется сама ДНФ, — число отрицаний.
Среди всех минимальных (в смысле определения 6.6) ДНФ следует отобрать те, в которых число вхождений переменных под знаком отрицания являетсл наименьшим. С точки зрения сложности СФЭ, которая будет 6. БУЛЕВЫ ФУНКЦИИ 456 Ох10 011х х111 11я1 Рис. 6.32 построена по минимальной ДНФ, это означает, что в ней минимизируется число „инверторов" — вершин СФЭ, помеченных функцией отрицания. Например, для функции, заданной картой Карно (рис. 6.22), к ядру, состоящему из простых импликантп х1хзх4 и х1хзх4, следует добавить простую импликанту хгхзх4, а не х1хзхз, поскольку она не содержит отрицаний.
Вопросы и задачи 6.1. Найти число дуг в булевой п-сети. 6.2. Доказать, что объединение двух соседних граней размерности и — Й булеза куба В" является гранью размерности и — я+ 1. Как найти направление этой грани? 6.3. Найти число вершин Й-слоя булеза куба В". 6.4. Построить таблицы для булевых функций, заданных формулами: а) (х -1 у) Ч (х -+ (х у)); б) (х -+ (х ° у) ) -+ (х Ч я); в) (х (у -4 х)) -+ х; г) (х -~ (у -+ «)) -+ ((х -+ у) -4 (х -+ я)); д) (х (у Ч х)) ((у -+ х) Ч у). 457 Воиросм и задачи 6.5.
Доказать, что если высказывания У и (У =ь В) тождественно истинны, то высказывание В тождественно истинно. 6.6. Доказать, что если формулы (У Ч В) и (УЧИ~) тождественно истинны, то формула (В Ч Ю) тождественно истинна. 6.7. Найти фиктивные переменные функции у, заданной вектором значений: а) у = (0,0,1,1,0,0,1,1); б) 1 = (0,0,1,1,1,1,0,0). 6.6. Показать, что х является фиктивным переменным функции у, представленной формулами: а) У = ((» -~ д) Ч х) (д -+ х)зх; б) у = ((хЧ9)(ХЧУ) -+ (х-~ дх))д.
6.0. Доказать, что для любой булевой функции ~ от п переменных имеет место следующее равенство: Дхм...,х;,...,ха) = х;У(хм...,1,...,х„) Чх;Дхм...,О,...,х„). (Это равенство называют разложением функции у по перемен- ному х;.) 6.10. Пусть булевы функции у и д имеют одно и то же число существенных переменных, равное г.
Тогда каждый набор а Е Е (О, Ц~ однозначно определяет набор значений существенных переменных каждой из функций. Пусть для любого такого сз значения функций у и д на соответствующих наборах своих существенных переменных равны. Следует ли отсюда, что эти функции равны? 6.11. Используя алгоритм Квайна — Мак-Клоски, найти минимальные ДНФ для функций: а) у = (0,1,1,0,1,0,0,1); б) у = (1,0,0,1,0,0,1,1); в) ~ = (1,3,4,7,8,11,14,15); г) ~ = (2,4,6,9,10,11,13). 458 и няпны оункции 6.12. Каждый из четырех членов комитета голосует „за", нажимая на кнопку.
Решение считается принятым, когда не менее трех членов комитета голосуют „за". Найти минимальную ДНФ для функции голосования. 6.13. Определить число булевых функций от п переменных: а) сохраняющих константу (О или 1); б) самодвойственных; в) несамодвойственных; г) линейных. 6.14. Доказать, что замыкание множества функций, состоящего из дизъюнкции и суммы по модулю 2, совпадает с классом Те.
6.15. Доказать, что множество Те ОТ1 является замыканием однозлементного множества (у = ху Э я Ю $1. 6.16. Доказать, что число всех монотонных функций от п переменных равно числу всех антицепей булеза куба размерности и. Однозлементное множество считать антицепью. 6.17. Доказать, что сокращенная ДНФ, представляющая монотонную функцию, является минимальной. 6.18.
Доказать, что любая монотонная функция, отличная от константы, может быть представлена ДНФ без отрицаний. 6. 19. Доказать, что в булевом кубе размерности и существует антицепь, мощность которой составляет С~~~ ). Используя этот результат, доказать, что число монотонных функций от си~и и переменных не меньше 2с" 6.20. Доказать, что число монотонных функций от и переменных не меньше ~ 2 2 ~ — и. с~~ в=о Указ ание: используйте результаты задач 6.3 и 6.16. 6.21. Методом неопределенных коэффициентов найти поливом Жегзлкина для функций: а) у = (О, 1, 1, О, 1, О, О, 1); б) г = (х1/хг) 4 хз; Вопросы и задачи 459 в) ~ = (1, О, 1, О, О, О, 1, 1); г) у' = (1001110000011000). 6.22. Выяснить, являются ли самодвойственными следующие функции: а) ху(х(у ~ х)) -+ (х у); б) (((хЧу) х) (у х)) -+ (хЧх); в) ~ = (01101001); г) У = (10101011); д) у = (1100100101101100). Для несамодвойственных функций найти двойственные функции.
6.23. Выяснить, полно ли множество булевых функций Р: а) Р=(~1=х,~э=х(у-х)-ух,~з=хЩуЩх); б) Р = (Л = ху ® ух 9 хФ Ь = О, Уз = 1, ~4 = х Ч у)' в) Р = (~4 = 0110, ~э = (11000011), 5 = (10010110)); г) Р = Ц4 = х Ч у, Ь = (1001101111110110)1. Для полного множества Р построить формулы над Р, представляющие элементы стандартного базиса и базиса Жегалкина.
Реализовать эти формулы схемами из функциональных элементов. 6.24. Полное множество булевых функций называют базисом, если оно не содержит полных собственных подмножеств (т.е. является минимальным по включению полным множе. ством). Найти любой базис, содержащий импликацию (~). 6.25. Проверить полноту множества Р, состоящего из функций у4 = хуЧхя, ~~ = х -+ у, 0 и х Эху. Выделить в нем всевозможные базисы.
7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ В этой главе мы начинаем изложение элементов теории формальных языков. Говоря „формальный язык", мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый „научно разработанный" язык программирования содержит „темные места", однозначное понимание которых является проблемой.
Изучая языки, следует иметь в виду три основных аспекта. Первый из них — синеамсис языка Язык — это какое-то множество „слов", где „слово" есть определенная конечная последовательность „букв" — символов какого то заранее фиксированного алфавита. Термины „буква" и „слово" могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, „буквами" могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования „Паскаль". Тогда „словами" будут конечные последовательности „букв": „крокодил", „1пСе~ег".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
