В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 28
Текст из файла (страница 28)
л) Выразим сначала данную функцию через функции ',, ч, причем так, чтобы знак ' стоял бы лишь на переменных и не стоял на скобках: (х -+ (у -+ ~')) ч (ху++ я) = (х' ч (У -+ -+ т')) ч (ху -+ ~)(т -+ ху) = х' ч у' ч 2' ч (х' ч у' ч ~)(~ ч ху) Соответствующая схема имеет вид 7.5. Проверьте равносильность следующих релейно-контактных схем: 133 и) — х х' х х — у к) — у — г' х — — х — у — г'— у х — 1 Р е ш е н и е.
л) Сначала составим функцию проводимости первой из двух данных схем, а затем преобразуем ее: к(х, у, ~) = х ч (х ч у ) (у ч г. )ч у ч г, = х ч [(х ч у') (уч 2 )ч у 1 ч 2 = = х ч (х ч у 'ч у )(у ч г' ч у ) ч г. = х ч(х ч у )( у ч у' ч ~') ч х = х ч (х ч ч у)(1 ч ~) ч а=хч (хч у)1 ч ~=хч (хчу) ч ~=х чу' ч ~. Ясно, что полученная функция (булева функция, конечно, осталась той же самой, а изменилась лишь форма ее аналитической записи) является функцией проводимости второй из двух данных схем. 7.б. Упростите следующие релейно-контактные схемы: У', Я ' — Е х у' г) 135 э) У вЂ” 1 х' — + — е' — г— х у у Решение.
л) Ток может протекать через контакты хну, если они замкнуты, т.е. если конъюнкция ху равна 1. Далее ток может пройти через контакты х, и, и, если они замкнуты, т.е. если коньюнкция хои равна 1. Аналогично, ток может пройти через контакты х, и или ~, и, у, т.е. ток проходит через схему, если одна из конъюнкций хи или хеу равна 1. Итак, ток пройдет через схему в том и только в том случае, когда хотя бы одна из конъюнкций ху, хеи, ~и или хэу равна 1, т.е. когда равна 1 дизъюнкция всех этих конъюнкций.
Следовательно, функция проводимости данной схемы такова: я(х, у, ~, и, и) = хуч хиич гич хеу, а сама схема может быть реализована обычной (не мостиковой) схемой, но с большим числом контактов, чем исходная схема: 137 Синтез релейно-контактных схем. Решить задачи 7.8 — 7.26. 7.8. Постройте наиболее простые релейно-контактные схемы по заданным условиям работы: а) я(0, О, 0) = х(1, О, 1) = 1; б) к(1, 1, 0) = я(0, О, 0) = я(1, О, 0) = 1; в) к(0, О, 0) = я(0, 1, 0) = я(1, О, 0) = к(0, 1, 1) = 1; г) к(0, О, 1, 1) = к(1, 1, 1, 0) = я(0, 1, 1, 0) = 1; д) я(0, О, 1, 1) = х(0, О, О, 1) = к(1, О, О, 1) = 1; е) л(1, 1, 1, 1) = х(0, 1, О, 1) = 1; ж) я(0, 1, 1) = х(0, 1, 0) = я(0, О, 1) = 1; з) я(1, 1, 0) = я(1, О, 0) = я(0, 1, 0) = 1; и) х(0, О, О, 1) = я(1, О, О, 1) = я(0, О, 1, 1) = л(1, О, 1, 1) = 1; к) я(1, О, О, 0) = х(1, 1, О, 0) = х(1, О, О, 1) = х(1, 1, О, 1) = х(0, 1, О, 1) = 1.
Указание. Используя СДН-форму (или СКН-форму), найдите сначала аналитическое выражение для функции х проводимости исходной схемы. Максимально упростите полученное выражение. После этого начертите релейно-контактную схему, для которой полученное выражение представляет собой функцию проводимости. 7.9.
Постройте наиболее простую релейно-контактную схему с четырьмя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнено по меньшей мере одно из следующих трех условий: а) переключатель х замкнут и только один из переключателей у или ~ замкнут; б) ! разомкнут и только два из остальных переключателей разомкнугы; в) только два переключателя, но не переключатели у и 1, замкнуты. Р е ш е н и е. Используя условия, которым должна удовлетворять искомая схема, составим сначала таблицу значений функции проводимости я этой схемы (в последнем столбце таблицы указано то условие, по которому функция к принимает значение 1 на данном наборе значений аргументов).
Зная теперь все наборы значений аргументов, на которых функция и обращается в О, запишем выражение для нее, используя совершенную конъюнктивную нормальную форму (потому что наборов значений аргументов, на которых функция обращается в О, значительно меньше, чем наборов, на которых функция обращается в 1, и, значит, СКН-форма будет более простой„нежели СДН-форма), и затем упростим его: я(х, у, ~, !) =(х ч у ч ~ч Ях ч у ч т ч !) (х ч у' ч г ' ч !)(х 'ч у' ч г 'ч ч !)(х 'ч у' ч ~" ч !')= х(х ч у ч Л ч 1!')(х ч у 'ч 22' ч !')(х' ч у 'ч ~' ч и') = = (х ч у ч я)(х ч у' ч ! )(х' ч у 'ч Л ) = (х ч (у ч л)(у' ч ! )](х' ч у' ч л ) = = (х ч у '~ ч у!' ч Л!')(х' ч у' ч ~') = х'у'~ ч х'у!' ч х'~!' ч ху' ч у'~ ч у'гу ч чхг.'чуя !'=ху!' чх1 учу уд!'чху'чу ячх1 учу ~у.' ч(хчх )у~!'= = х у! ч х улд ч х'у г! ч ху ч у я ч ху~ ч ху л ч худ ! ч х'у~ ! .
138 Далее используется закон поглощения. Внимательно разьпците в последнем выражении все слагаемые, из которых одно поглощается другим. Например, ху' ч ху'~' = ху', х'уг' ч х'у~'г' = х'уг'. Продолжаем упрощение функции: а(х, у, ~, г) = х'у1' ч ху" ч у'т„ч худ' = х'у('ч х(у 'ч уг,') ч у'~ = х'УГ' ч чху'чхг.'чу~=(хч~)у'чх'уГ чх~'. Изображаем релейно-контактную схему, обладающую найденной функцией проводимости: У 7.10. Каждый из трех членов комитета, голосуя «за», нажимает на кнопку. Построить по возможности более простую схему, через которую проходил бы ток и включал электрическую лампочку тогда и только тогда, когда не менее двух членов комитета голосуют «за». 139 7.11. Комитет состоит из пяти человек. Решение выносится большинством голосов.
Если председатель «против», то решение не принимается. Построить такую схему, чтобы, голосуя «за», каждый из пяти человек нажимал бы на кнопку, и в случае принятия решения зажигалась бы сигнальная лампочка. 7.12. Постройте релейно-контактную схему с четырьмя переключателями, которая проводит ток тогда и только тогда, когда замыкаются некоторые, но не все переключатели. 7.13.
Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда замкнуты все ее переключатели или когда не замкнут ни один из них. 7.14. Постройте схему с тремя переключателями, которая замыкается тогда и только тогда, когда замкнуты либо ровно один„ либо ровно два переключателя. Используйте не более шести контактов. 7.15. Начертите схему с пятью переключателями, которая замыкается, если и только если замкнуты ровно четыре из этих переключателей.
7.16. Начертите схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замыкаются ровно два или ровно три из этих переключателей. 7.17. Требуется составить схему с четырьмя переключателями х, у, ~, ь Схема должна проводить ток тогда и только тогда, когда будут замкнуты переключатели х и у или х и ь 7.18. Начертите схему, которая замыкается тогда и только тогда, когда либо переключатель х замкнут, либо переключатель у замкнут, либо переключатель х разомкнут. 7.19.
Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда меньшая часть переключателей замкнута, но если последний переключатель замкнут, то схема проводит ток, независимо от положения остальных переключателей. 7.20.
Имеется одна лампочка в лестничном пролете двухэтажного дома. Постройте схему так, чтобы на каждом этаже своим выключателем можно было бы включать и выключать лампочку, независимо от положения другого выключателя. Р е ш е н и е. Функция проводимости я(х, у) такой схемы должна обладать тем свойством, что ее значение меняется всякий раз, когда меняется значение одного ее аргумента. Следовательно, например: я(1, 1) = я(0, 0) = 1; я(0, 1) = я(1, 0) = О. Используя СДН-форму, отсюда легко получаем: я(х, у) = ху ~ х'у', а соответствующая схема имеет вид 140 7.21. Спроектируйте релейно-контактную схему, позволяющую включать и выключать электрическую лампочку с помощью трех независимых переключателей. Сколькими способами можно сконструировать такую схему? 7.22.
Спроектируйте релейно-контактную схему, которая позволяла бы включать и выключать электрическую лампочку с помощью четырех независимых переключателей. 723. Постройте релейно-контактную схему с пятью переключателями, каждый из которых позволял бы включать и выключать в любой момент одну и ту же лампочку. 7.24. Опишите функцию проводимости релейно-контактной схемы с п переключателями, позволяющей включать и выключать лампочку любым из них (см. задачи 7.20 — 7.23).
Сколько существует таких булевых функций от л аргументов? 7.25. Схема должна быть замкнута, если переключатель х разомкнут, но без того, чтобы у и г (но не оба вместе) были замкнуты: в последнем случае цепь разомкнута. Кроме того, цепь должна быть замкнута, когда х замкнут, но при этом у и х не должны быть одновременно замкнуты или одновременно разомкнуты; в последнем случае цепь также размыкается. Постройте удовлетворяющую этим условиям релейно-контактную схему с наименьшим возможным числом контактов. 7.26. Какой контакт, х, у, х' или у', необходимо вставить в вакантное место релейно-контактной схемы, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции: б) х(х, у) = х м у а) х(х, у) =х в) я(х, у) = ху', г) я(х, у) = ху; -Е'~л- С д) я(х, у) =у е) х(х, у) =х ч у Г' И 141 ж) л(х, у) = х и у з) х(х, у, г) =хну че; У х и) х(х, у, е) =х', х) л(х, у) =х ч у х' — у' — е' х л) Р е ш е н и е.
л) Обозначим искомый контакт Ф и составим функцию проводимости данной схемы: к(х, у) = (х ч у) у' ч х'Ф. Упростим ее, используя свойства булевых функций: к(х, у) = = ху "ч уу"ч х'Ф = ху' ч О ч х'Ф = ху' ~ х'© По условию должно быть: ху' ч хФ = х' г у'. Сравнивая выражения в левой и правой частях последнего равенства, заключаем, что Ф = х'.
Глава П1 ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ Эта глава состоит из одного параграфа. В нем осуществляется глубокое развитие аксиоматической теории высказываний в форме задач на базе системы аксиом, принятой в Учебнике (З 15), а также рассматриваются задачи о независимости этой системы аксиом. й 8. Построение формализованного исчисления высказываний и исследование системы аксиом на независимость В качестве аксиом выбираются формулы следующих видов: (А1) (Г-+ (б -+ Г)), (А2) ((Г -+ (6 -+ Н)) -+ ((Г -+ 6) -+ (Г -+ Н)), (АЗ) ((-юб -+ -1Г) -+ ((-16 -+ Г) -+ 6)), где Г, б, Н вЂ” произвольные формулы. Таким образом, каждое из выражений (А1), (А2), (АЗ) задает лишь форму аксиомы. Они пре- вращаются в аксиомы, если вместо Г, 6, Н подставить конкрет- ные формулы (в частности, пропозициональные переменные). Следовательно, каждое из этих выражений задает бесконечное множество формул.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
