В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

у(ан ан ..., а„) = = «(ан а,, ..., а„) для любых элементов а; ~ (О, Ц, где г' = 1, ..., л. 4.8. Постройте таблицы значений для следующих булевых функций: а) г(х, у, с) = ((х-+ ~)у') -+ х'; б) Ях, у, ~) =((х чу') -+ ~Н(х ~ у) ++ ~'); в) Ях, у, ~) = х' -+ (х ++ (у + (х~))); Г) Ях, у, а) = ((((х / у) 4 1)! у) 4, ~); д) )(х, у, ~) = (х'у'г') 4 (хут); е) Х(х у, ~)=х'у'+у~'+ху; ж)у(х, у, ~)=(х4 у)'+сх+ху; з) г"(х, у, ~) = ((х ~ у) + (у ~ ~)) + хуг.; и) Дх, у, ~) = ((х + у) (у + ~)')', к) Ях, у, ~) = (ху~) / (х'у'~'); л) Ях, у, ~) = ((х -+ (у ч ~))(у~)') -+ х Р е ш е н и е.

л) Построим таблицу значений для булевой функции ~(х, у, ~) = ((х -+ (у ч ~))((у~)') -+ х: 4.9. Построив соответствующую таблицу значений, выясните, равны ли следующие булевы функции: а) у(х, у, ~) =((хчу)чг)-+((хчу)(хч~)),я(х,у, ~)=хч(у++~); б) ~(х, у, ~) = (х 'ч у)(у ч 2), я(х,у, ~) =(хч у ч ~)(х' ч у ч ~)(х 'ч уч ч ~'); в) Ях, у, ~) = (х -+ у) -+ ~, «(х, у, ~) = х -+ (у -+ ~); 96 г) 7(х, у) = ((х + у) -+ (х ~ у))((х' -+ у) -+ (х 4- у)), л(х, у) = =х~у; д) 7'(х, у, ~) = ((х ~ у')~) ч (х~') ч (~(у м ~')), л(х, у, ~) = х ч ~; е) 7(х, у, ~) = ху ч хг ч уг., а(х, у, г) = (х + у) г.

м ~у; ж) 7(х, у, ~) = ху 'ч х'у ч х'~', л(х, у, ~) = (х 'ч у')(х ч у ~ ~'); з) г(х, у, г) =х'у'~' ~~ х'у~ ~ ху~ ~ ху'~, л(х, у, х) = (х-+у~)(у 4-+ ++ 2) ~ (У -+ х~)(х 4-+ ~); и) Ях, у, ~) =((у'+ х) + ~(х+ у'))', л(х, у, ~) = ~' -+ (у -+ х)', к) Дх, у, ~) = (х + ~')'(у + х'~), л(х, у, ~) = у + (~ -+ х)', л) Г(х, у, ~) = (х+ у)' ч (х+ ~)', л(х, у, ~) = ху~+ х'у'~'. Р е ш е н и е. л) Построим таблицы значений для функций 7'и л: Лх~ у~ 2) = (х + у) и (х + 1)' л(х, у, ~) = ху~ + х'у'~' 97 4 игошин Получили: ЯО, О, 1) ~ 8(0, О, 1), ДО, 1, 0) ~ 8(0, 1, 0), Д1, О, 1) ~ л(1, О, 1), Я1, 1, 0) ~ 8(1, 1„0). Следовательно, г(х, у, е) ~л(х, у, ~).

Свойства булевых функций. Некоторые из этих свойств, которые связаны с тождествами для булевых функций, приведены в З 9 Учебника. Рассмотрим здесь ряд дополнительных подобных свойств. 4.10. Проверьте справедливость следующих равенств, выражающих свойства дистрибутивности (распределительности) одних булевых функций относительно других: а) (х-+у) ч ~= (х ~ ~) -+ (у~~ ~); б) (х ++ у) ~ а = (х ч ~) ++ (у ~ ~); В) х -+ (У -+ ~) = (х -+ У) -+ (х -+ 2)1 г) х-+у~=(х-+у)(х-+ ~); д) х -+ (у ~ ~) = (х -+ у) ~ (х -+ ~); е) х-+ (у<-+ ~) =(х-+у) ++ (х-+ е); ж) х(у~) = (ху)(х~); 3) х у (у ' ' 2) = (х и у) ч (х '/ ~); и) х-+ ху=х-+у; к) (хчу) -+у=х-+у; л) х-+ (х-+у) =х-+у; м) х -+ (х ++ у) = х -+ у.

Заметьте, что свойства и), л), м) также представляют собой свойства дистрибутивности слева нли справа одних булевых функций относительно других. Так, для свойства и) имеем х -+ ху = = (х -+ х)(х -+ у) = 1(х -+ у) = х -+ у. 4.11. В задачах 4.10, в, г, д, е установлена левосторонняя дистрибутивность импликации относительно самой себя, конъюнкции, дизъюнкции и эквивалентности.

Исследуйте вопрос о правосторонней дистрибугивности импликации относительно тех же функций. 4.12. Обладает ли импликация свойствами коммугативности и ассоциативности? 4.13. В задачах 4.10, а, б установлена правосторонняя дистрнбутивность дизъюнкции относительно импликации и эквивалентности. Будет ли дизъюнкция дистрибутивна слева относительно этих функций, т.е. будут ли справедливы равенства х ч (у -+ ~) = (х ч у) -+ (х ч е), х ~ (у++ ~) = (х ч у) ++ (х м е)? 4.14. Исследуйте вопрос о дистрибутивности конъюнкции относительно импликации и эквивалентности. 4.15.

Выясните, будет лн эквивалентность дистрибутивна относительно конъюнкции, дизъюнкции, импликации, а также относительно самой себя. 4.16. Проверьте, что сложение по модулю два (сумма Жегалкина) обладает следующими свойствами: 98 а) х + у = (х ++ у)', б)х+у=у+х; в) (х + у) + ~ = х + (у + е); г) (х + у)а = хе + у~; д) х+х=О; е) х+О=х; ж) если х = у + е, то у = х + е; з) если х + ~ = у + ~, то х = у; и) ху ~ ха ~ у~ = ху + х~ + у~; к) (х! + Хз + ".

+ Х~)у = х!у + кзу ь ... + хну; л) х, +хз+ ... +х„= О, если среди х„хм ..., х„четное число единиц, 1, если среди х„х,, ..., х„нечетное число единиц. Решение.л)Докажем сначала первое из этих утверждений. Пусть переменным хо х„..., х„придаются такие значения ао аь ..., а„соответственно, что общее число единиц среди них четно (а остальные значения а равны 0). Сгруппируем эти единицы в пары (остальные слагаемые равны 0): (1 + 1) + (1 + 1) + ...

+ + (1 + 1) + 0 + ... + О. В силу четности числа единиц для каждой единицы найдется пара. По определению суммы Жегалкина в каждой паре сумма равна 0 и общая сумма также равна О. Чтобы доказать второе утверждение настоящей задачи, нужно заметить, что при группировке в пары суммы нечетного числа единиц для одной единицы пары не найдется.

Эта единица, будучи прибавленной к остальной сумме, которая равна О, дает в итоге единицу. 4.17. Докажите, что булева функция штрих Шеффера ~ обладает следующими свойствами (наряду с другими булевыми функциями): а) х! 1 = х~ х = х'; ж) (х! у)' = (х' ч у)'; б) х ! О = 1; з) х ~ (х! у) = у ~~ (х ~ у); в) х!х'=1; и) (х1 х) !у=у-+ х; г) х!у=у~х; к) (х!х)~(у!у)=хчу; д) (х!у)'=х'1у', л) ((х!х)'!(у!у)')'=ху.

е) х! (ум х) =х', Р е ш е н и е. л) ((х ~ х)' ! (у ~ у)')' = (х" ! у")' = (х ~ у)' = (х' ~ у')' = = ((ху) )' = ху. 4.18. Докажите, что булева функция стрелка Пирса 4 обладает следующими свойствами (наряду с другими булевыми функциями): а) х4х=х', ж) (х 4 у)' = х' 4 у'; б) х4 у=у4 х; з) х 4 (ух) = х'; в) х41 =0; и) (х 4 у)' = (х'у')', г) х4 0 =х', к) (х4,х')'(х4 х)'=х; д) х4х'=0; л) х(х4 у) =х(14 у). е) х(х 4 у) =у(хну); 99 Р е ш е н и е. л) Данную задачу будет нетрудно решить с помощью таблицы значений. Составим ее для функций из левой и правой частей доказываемого равенства.

Из таблицы видно, что выделенные столбцы, соответствую- щие значениям данных функций, одинаковы. Следовательно, дан- ные функции действительно равны. Попутно мы доказали, что данные функции равны тождественно О. 4.19. Докажите, что булевы функции следующим образом вы- ражаются через отрицание (') и дизъюнкцию ч: а) ху=(х'чу')', б) х -+ у = х' ч у; в) х++ у = (х -+ у)(у -+ х) = (х' ч у)(х ч у'); г) х+у=(х' ~у)'~(х~у')', д) х)у=х'~у'; е) х1,у=(х~у)', ж) х,4 у = (х' ч у)' (знак 4 означает отрицание имплика- ции); з) х ~у=(х'~у)'~~у. Решение. з) Начнем преобразования с правой части равен- ства: (х' ч у)' ч у = (х "у') ч у = (х ч у')ч у = (х ь у)(у' ч у) = (х ч у) 1 = = х ч у.

Что и требовалось доказать. 420. Выразите через суперпозиции конъюнкции (.) и отрица- ния (') следующие булевы функции: а) дизъюнкцию ч; б) имп- ликацию -+; в) эквивалентность +~; г) сумму Жегалкина +; д) штрих Шеффера ~; е) стрелку Пирса 1; ж) отрицание импли- кации 4 . 4.21. Докажите, что булевы функции следующим образом вы- ражаются через сумму Жегалкина+ и константу 1: а) х'=х+1; б) х ~ у = (х + 1)(у + 1) + 1 = ху + х + у; в) х-+у=ху+х+ 1; г) х+~ у= х+ у+ 1; д) х ~ у = ху + 1; е) х 1,у=ху+х+у+ 1; ж) х 4 у = ху + х; з) х'у ч ху' = х+ у; 100 и) х'у' ч ху=х+у+ 1; к) (х ++ у)' = х + у; л) (х ++ у) ++ ~ = х + у + ~. Решение.

л) (х++у) ++ г= [(х+у+ 1+ е] + 1 = х+у+ е+ 0 = =х+у+~. 4.22. Докажите, что булевы функции следующим образом выражаются через штрих Шеффера !: а) х'=х[х; б) ху=(х]у) !(х]у); в) х ч у = (х ! х) ! (у ! У); г) х-+у=х](у]у); д) х 4 у=(х!(у!У)) ](х! (у/у)); е) х 1 у = [(х ! х) ! (у ! У)] ! [(х ! х) ! (у ! У)]; ж) х+ у = (х ! (у ! У)) ! (у ! (х ! х)); з) х++ у = [(х ! (у ! У)) ! (у ! (х ! х))] ! Кх ! (у ! У)) ! (у ! (х ! х))]; Р е ш е н и е. ж) х+ у = (х++ у)' = ((х -+ у)(у -+ х))' = (х -+ У) ! (У -+ -+ х) = (х ! (у ! У)) ! (у ! (х ! х)). 4.23.

Выразите с помощью суперпозиций функции стрелка Пирса 4 следующие булевы функции: а) отрицание ', б) конъюнкцию; в) дизъюнкцию ч; г) импликацию -+; д) отрицание импликации 4; е) штрих Шеффера ]; ж) сумму Жегалкина +; з) эквивалентность ++. Р е ш е н и е. з) х ++ у = (х -+ у)(у -+ х) = ((х -+ у)' ч (у -+ х)')' = = (х -+ у)' 4 (у -+ х)' = (х' ч у') 4 (х ч у)' = (х' 4 у) 4 (х 4 у') = ((х 4 4 х) 4 у) 4 (х [ (у 4 у)). 4.24. Выразите через отрицание ' и импликацию — ~ следующие булевы функции: а) дизъюнкцию ч; б) конъюнкцию; в) эквивалентность ++; г) сумму Жегалкина +; д) штрих Шеффера !; е) стрелку Пирса 4.

ф 5. Специальные классы булевых функций Речь пойдет о классах функций, играющих важную роль в теореме Поста, описывающей полные системы булевых функций, т.е. такие системы булевых функций, через которые все другие булевы функции могут быль выражены в виде суперпозиции. Зто— классы линейных булевых функций, самодвойственных булевых функций, монотонных булевых функций и функций, сохраняющих нуль и сохраняющих единицу. Полииомы Жегалвииа и линейные булевы фуивзщи. Полиномом Жегалкнна от переменных х), х)„..., х„называется булева функция вида )))ь ), )„х;, х), ...Х)„, (2-.) 101 представляющая собой сумму по модулю два (сумму Жегалкина) конъюнктивных одночленов х,. х,....х,.

Характеристики

Список файлов книги