В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 27
Текст из файла (страница 27)
6.22. Докажите, что системы функций из задачи 6.1 являются базисами. Р е ш е н и е. Если из данной системы удалить функцию х ++ у, то получим неполную систему функций, так как функции ху и 0 обе монотонные. Если же удалить функцию ху, то снова приходим к неполной системе, так как функции х ++ у и 0 линейные. И наконец, если удалить О, система вновь будет неполной, так как функции х++ у и ху сохраняют единицу. Следовательно, удаление любой из функций данной полной системы функций приводит к неполной системе. Значит, данная система является базисом.
6.23. Докажите, что следующие системы булевых функций яв- ляются базисами: а) х+ у + е, ху, О, 1; ж) (у-+ х)(у' -+ х), О, 1; б) х + у + ~, х ч у, О, 1; з) ху ~ е, х ++ у, О; в) х + у + х, ху + х~ е уе, О, 1; и) ху ~ хг ~ уе, х++ у, х+ у; г) худ, х ++ у, 0; к) (х + у) ++ г, ху + х, х + у; д) ху ч у'х, О, 1; л) х ~у~, х+у, 1; е) ху ~ хг. ч ух, х', 1; м) (х ++ у) + х, ху + ~, О. 6.24. Из полной системы булевых функций выделите всевоз- можные базисы: а) (х чу)(х' чу'), ху+ е, (х+у) ++е, хуч х~ч уе; б) х+ у + г, 1, ху, х', в) худ, х + у + г, 1, ху', г) (х + у) е, 1, ху и у'г, х + у + х~ д) х'у' ~ х'г,' ~ у'х', х+ у, ху, 1; 128 е) (х -+ у) -+ х, х', худ, х + у + х; ж) х -+ (у -+ х), х+ у, О, ху + х; з) х ~ ух, х+ у, 1, х'; и) ху ч х, х ++ у, О, 1; к) худ у'х, О, 1, (у-+ х)(у' -~ х).
л) х и хх', х + у, х ++ у 1 У к а з а н и е. Сначала нужно составить таблицу Поста для данной системы и выяснить, является ли она полной. Затем проверить, является ли сама система нз четырех функций базисом (см. задачу 6.22). Если эта система не является базисом, то из нее выделяются всевозможные полные системы, состоящие из двух и трех функций. И наконец, нужно проверить, будут ли полные системы из двух и трех функций базисами.
6.25. Докажите, что базис не может содержать более пяти функций. Р е ш е н и е. Ясно, что из всякой полной системы функций можно выбрать не более пяти функций, удовлетворяющих теореме Поста. 6.26. Докажите, что базис не может содержать более четырех функций. Р е ш е н и е. Рассмотрим функцию, не сохраняющую нуль. В силу задачи 5.16, а она или является немонотонной, или является тождественной единицей, а следовательно, является несамодвойственной функцией. Это означает, что во всякой полной системе обязательно найдется функция, не принадлежащая сразу двум из пяти классов Р„Р,, о", А, М Тогда к этой функции можно присоединить не более трех функций из рассматриваемой системы так, чтобы удовлетворялись условия теоремы Поста. Следовательно, в базисе не может быть более четырех функций. 6.27.
Для каждого 1 = 1, 2, 3, 4 приведите пример базиса, состоящего из г' функций. 6.28. докажите, что если система функций л = И Ь " Х ) является базисом, содержащим функции-константы О и 1, то число т функций в нем равно 3 или 4. Причем, если и = 4, то из двух оставшихся функций одна представляет собой сумму нечетного числа своих аргументов, а другая — монотонная функция от не менее чем двух аргументов.
6.29. Докажите, что если базис содержит функцию-константу О и не содержит 1, то число функций в нем может быть равно либо 2, либо 3. 6.30. Докажите, что если базис содержит функцию-константу 1 и не содержит О, то число функций в нем может быть равно либо 2, либо 3. 6.31. Докажите, что базис, не содержащий функций-констант, может состоять из одной, двух или трех функций. 6.32.
Докажите, что пара функций (', у") образует базис в том и только в том случае, если 1' в (Е ~ о") г~ (Р, ~ Р,). 5 игошин 129 й 7. Применение булевых функций к релейио-контактным схемам Под релейно-контактной схемой понимают устройство из проводников и двухпозиционных контактов, через которое полюсы источника тока связаны с некоторым потребителем. Контакты могут быть замыкающими или размыкающими.
Каждый контакт подключен к некоторому реле (переключателю). Когда реле срабатывает (находится под током), все подключенные к нему замыкающие контакты замкнуты, а размыкающие контакты разомкнуты; в противном случае — наоборот. Каждому реле ставится в соответствие своя булева переменная х, которая принимает значение 1, если реле срабатывает, и 0 — в противном случае. На чертежах все замыкающие контакты, подюпоченные к реле х, обозначаются символом х, а размыкающие — символом х'. Это означает, что при срабатывании реле х все его размыкающие контакты х' не проводят ток и им сопоставляется О.
При отключении реле создается противоположная ситуация. Всей схеме также ставится в соответствие булева переменная у, которая равна 1, если схема проводит ток, и 0 в противном случае. Переменная у, соответствующая схеме, очевидно, является булевой функцией от переменных х„х,, ..., х„, соответствующих реле. Эта функция называется функцйей проводимости схемы, а ее таблица — условиями работы схемы. Две релейно-контактные схемы называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток, т.е.
если обе эти схемы обладают одинаковыми функциями проводимости. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. В теории релейно-контактных схем различают две главные задачи — анализа и синтеза. Задача анализа состоит в изучении характера работы данной схемы и ее упрощении. Задача синтеза состоит в построении схемы с наперед заданными условиями работы. Анализ релейно-контактных схем. Решить задачи 7.1 — 7.7.
7.1. Найдите функции проводимости следующих релейно-контактных схем: а) в) г) 130 д) е) ° ж) з) ") к) х — ( ~ — г л) м) Решение. л) Ясно, что данная схема проводит электрический ток тогда и только тогда, когда оба независимых переключателя х и у замкнуты. Следовательно, функцией проводимости этой схемы будет такая булева функция от двух аргументов, которая принимает значение 1 в том и только в том случае, когда оба ее аргумента принимают значение 1. Как известно, такой функцией является конъюнкция х . у. Итак, а(х, у) = х у.
м) Ясно, что данная схема проводит ток тогда и только тогда, когда по меньшей мере один из двух независимых переключателей х или у замкнут. Следовательно, функцией проводимости этой схемы будет такая булеза функция от двух переменных, которая принимает значение 1 в том и только в том случае, когда хотя бы одна из переменных х или у принимает значение 1. Такой функцией является, как известно, дизъюнкция ху у. Итак, а(х, у) = х ч у. 7.2. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы: а) х' у в) 131 с И л) Р е ш е н и е.
л) Схема состоит из трех параллельных ветвей. Первая ветвь, в свою очередь, состоит из двух параллельных ветвей, в одной из которых последовательно соединены два контакта х и ~', а в другой есть лишь один контакт у. Поэтому первая из трех параллельных ветвей имеет следующую функцию проводимости: Хг' дУ. Вторая параллельная ветвь состоит из двух последовательно соединенных контактов х и у и поэтому имеет следующую функцию проводимости: ху. Наконец третья параллельная ветвь схемы состоит из двух параллельных ветвей, в одной из которых единственный контакт х', а в другой последовательно соединены контакты у и ~.
Поэтому функция проводимости третьей ветви схемы есть х' )д уг.. Итак, поскольку данная схема состоит из трех параллельно соединенных ветвей, функции проводимости которых мы нашли, 132 то для нахождения функции проводимости всей схемы нужно рассмотреть дизъюнкцию найденных функций: а(х, у, а) = (х2' ч у) ч ч хуч (х' чу~). 7.3. Постройте релейно-контактную схему с заданной функцией проводимости: а) (хуч~'чх')(х'чу); ж) (хчуг)(харч ~(х' чу)); б) (х'чу)(укчх)чи~; 3) ху'ч л(тгч~)х"чх'ии; в) хууг ч у~') ч х'(у е ч у~'); и) ((ач х)у'и ч х' 4м:, г) (х' ч ууух'(у ч е); к) х (у ч ~') ч х 'ч (у ч х~')х; д) х(удач Е)чхуз.'ч~(учх); л) х(уччхчу). е) х'(у~'чх(~уч~(хчу'))); Р е ш е н и е.
л) Схема представляет собой последовательное соединение контакта и схемы с функцией проводимости у'~ ч х ч у. Последняя схема, в свою очередь, состоит из трех параллельных ветвей. В первой ветви последовательно соединены контакты у' и ~, вторая содержит контакт х, третья — лишь контакт у. Итак, искомая схема имеет вид 3— 7.4. Постройте релейно-контактную схему с заданной функцией проводимости: а) (ху-+х'у)(хчду); ж) (х+ у') ч (х+ ~)(у'+ ~'); б) (х -+ у) — э х'(у ч ~); з) (ху + а) -+ х'г; в) (х -+ (у -+ а)) -+ (у -+ х'); и) (х' + у')(х++ у); г) (х / у') -+ ((х ч у) ~ (х ч г)); к) ху ! (х' -+ х(у ч е)); д) (а 4, ху)((х ч ~') 4, у~); л) (х -+ (у -+ 2')) ч (ху++ ~). е) (х~(х4 у'))~(х'4 (уч~')); Р е ш е н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
