Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[12]

Окончательно получаем Аг Аг

А0 Аг

Аг А,

Pi Р1Р2.

Р2 Pl

Pl

(3.21)

Pi Р1Р2 Рг

P1P2 РгРг

Из МСА (3.21) легко получить систему ФП: А0Рг Аг V ~р~г А2, Аг -г Рг р2 Аг V~Рг А3 V РгРг Ah ; А2 - Pj, Аг V Р2 А2 ; Аг-ргА Plp2A2y рхр2А3.

Как известно [3], МСА и ФП обладают двумя следующими свойствами:

]) /=IV & «у = 1; 2) ow а;г = 0, /# /.

iicpouc Лииииво указывает на полноту алгоритма, а второе-на его непротиворечивость. При этом формально считается, что алгоритм функционирования составлен правильна in »n л.л ..л ?лливооечив Таким образом, для того чтобы проверить, правильно ли соллфункционирования.

Достаточно прорить выполнение указанных выше двух свойств для всех сцюк

К сЛжаЛникЛсеквенции этими свойствами не обладают, поэтому по нТмпЛТоту и непротиворечивость алгоритма проверить значительно сложнее. Вот почему желательно от секвенции перейти к формулам Дьяченко или к МСА.

Следует заметить, что полнота алгоритма функционирования таким образом, проверяется лишь с формальной точки зрения без л-чета смыслового содержания алгоритма. Полнота алгоритма фунционирования с содержательной точки зрения условии работы проектируемого ДУ должна проверяться непосредственно проектиЛПЛоЛьку при использовании секвенции проверка па полноту и непротиворечивость условий работы автомата затруднительна, проектировщик можетне учесть каких-либо переходов (т. е. составить алгоритм функционирования не полно) или ошибочно включить в условия работы противоречивые переходы. Неполнота или (и) противоречивость алгоритма функционирования проектируемого ДУ проверяется при составлении МСА или Ф11.

Пример 3.8. Пусть проектировщик составил условия работы в виде смешанного описания, состоящего из трех ФП

А2 -+~рг Аг V Pl Az J

А3-+~РгАг\1 Pi Ai

и четырех секненций

Рг p2Ax\J PiP3Ai h А«;

Pi Рг Аг V PiA2\f Рг~р3 Ai h Aa ;

Pi

Pi Л h Ak.

Решение. Составим матричную схему алгоритма

Аг

51 = А2 А,

Ai 1

Pi Pi

Ai A„

PiPi PiP% Pi

P1P3 PiPs

Pi

Pi

(3.22)

Из рассмотрения (3.22) видно, что составленные условия раооты незлые, так как не выполняется первое условие для строки оператора Л,, и противоречивые, так как не выполняется второе условие для строки оператора А,

При выявлении неполноты и (или) противоречивости условий работа ?е составляемого алгоритма функционирования, последние должны быть скорректированы. В том случае, когда человек, формулирующий условия работы, выступает в качестве заказчика, а формализация условий работы в виде алгоритма функционирования, представляемого на одном из формальных языков (в нашем случае на языках ФП и секвенциях), с последующим проектированием ДУ осуществляется проектировщиком, в частности ЭВМ, корректировка условий работы осуществляется в процессе диалога «проектировщик-заказчик». В таком диалоге активным является проектировщик. Продолжим рассмотрение нашего примера.

Устраняем вначале неполноту условий работы. Для этого проектировщик спрашивает заказчика: «Что следует за оператором Ai, если логическое условие р2==0?». Если от заказчика ответа не последует, то это означает, что он не знает условий работы проектируемого ДУ. В противном случае он должен ответить (например, что после оператора Ai следует выполнить оператор Ai.). Следовательно, проектировщик в МСА (3.22) добавят элемент aii=p2.

Теперь устраняем противоречие. Здесь может быть несколько вариантов вопросов. Однако наиболее естественным вопросом является следующий: «Какой оператор должен выполняться после оператора Ai,, если ЛУ /?i=0?». Этот вопрос возникает вследствие того, что ни в одном из элементов нет pi, из-за чего и появилось противоречие. При pi=0 ответов может быть несколько:


1.После оператора Л* следует оператор Ah.

2.После оператора Ал следуют операторы А-г и Аз.

3.После оператора Ai, следует оператор АЛ

4.После оператора Ai, следует оператор Л.ч.

Если заказчик дает первый или второй варианты ответа, в результате коррекции строки At для нее будут выполняться первое и второе условия.

Скорректированная МСА будет описывать полный и непротиворечивый алгоритм функционирования проектируемого ДУ. В том случае, когда заказчик даст ответ по третьему или четвертому варианту, диалог между проектировщиком 11 заказчиком несколько удлиняется. Рассмотрим продолжение диалога при ответе по третьему варианту.

В данном случае по-прежнему не выполняется второе условие, так как №4зи4л=р1рзр1=р1рз=тЛ0. Поэтому естествен вопрос проектировщика: «Не будет ли выполняться оператор Аз после оператора Ai., если pi=0?». Если ответ будет отрицательным, то заказчик сам не знает условий работы проектируемого ДУ и поэтому процесс проектирования прекращается. Проектировщик предлагает заказчику уточнить условия работы автомата. Если ответ будет положительным, то строка Ад корректируется, после чего для нее будут выполняться первое и второе условия и диалог между проектировщиком и заказчиком оканчивается, а заказчику выдается для контроля составленная МСА (ФП или секвенпии). Условия работы могут быть выданы и на неформализованном (русском) языке. В нашем случае для первого ответа скорректированная МСА будет иметь, следующий вид:

Я =

А

А2 А3

Ai

Pi P~i

PiPi

P1P2 Pi

Ai Ah

Pi

Pi

P1P3 P1P3

Pi

(3.23

не только при корректировке условий

Диалог между проектировщиком и заказчиком возможен работы, но и в процессе состав ления секвенций и ФП.

После получения скорректированной МСА легко построить систему ФП.

Пример 3.9. Необходимо по МСА (3.23) построить систему ФП.

Решение. Функции ац отмечаем операторами Л, и получаем следующую систему ФП: f Д-Ai;

лl-P1P2-4aV ~Р1РгА»<~РчЛ\ \ Aa-PiAiV/ra;

аз - Pi Ai V Pi Ai;

[ A1-PlPsЛVЛlPsЛVP1лft-

Рассмотрим теперь процесс построения ЛСА по ФП [31. Пусть задана система ФП, полученная в примере 3.7. От ФП к ЛСА удобно переходить не непосредственно, а через так называемые скобочные ФП (иначе скобочные формулы Дьяченко), которые получаются из ФП следующим образом. В каждой ФП обязательно имеется такое одно ЛУ pj, которое входит во все ее члены. При этом говорят, что ФП приведена по ЛУ pj. Если таких ЛУ найдется несколько, то выбирают одно из них. В ФП выносят за скобки ЛУ без отрицания, т. е. pj, и с отрицанием, т. е. pj. Например, в ФП оператора а) получим Ai~7 (ргАЛрЛАЛУрЛАз. Это и есть скобочная ФП. Для нашего примера получим следующую систему скобочных ФП: Ло- рЛАЛрЛА.:, Лг~7 Pl(pl\/P,Ab}\/~PlAs,

At ~~7 Pi (Pa Л2 V йЛз) V Pi ai-

Из сравнения этой системы с исходной видно, что ФП для операторов Аа и a] остались без изменения. Если после вынесения за скобки переменной pj в каждом из заключенных в скобки выражений формулы переходов содержатся два и более ЛУ, то процедуру вынесения за скобки следует продолжить применительно к этим выражениям ФП. Например, пусть получена следующая ФП:

Pi (Рг Рз ai V Pt Рз А-г V Рз Ал) VPi ая-

В части, заключенной в скобки, вновь находим переменную, которую можно вынести за скобки. Таким образом, получаем

Pi (Рз (р2 A VЛa А) \/~Рз A,) \/pi Aa-

От скобочных ФП легко перейти к ЛСА. Вначале выписываем оператор Ао. После него выписываем ЛУ (со стрелкой), вынесенное за первую скобку. В нашем случае это pi, т. е. получаем AoPif. Затем выписываем оператор, выполняемый после Ац при р\=\, т. е:

получаем Aopi}Ai. После выписки оператора Л, (в нашем случае АЛ обращаемся к ФП оператора Л,, т. е. к ФП оператора Л,, н проделываем ту же процедуру. В результате получаем

А» Pi ЛЛаМгСЗ.24)

З*Ц.

Как видно из скобочной ФП оператора а], после pi стоит не оператор, а начинается скобка. Поэтому за pi выписывается рЛ, а затем уже оператор А]. Однако в том случае, когда оператор А,: уже выписан, его не повторяют в ЛСА, а вводят тождественно ложное ЛУ со стрелкой, оканчивающейся перед имеющимся оператором А{. В нашем случае оператор А\ выписан ранее. Поэтому вместо (3.24) получаем


А» PiH14 /"if/сЛМ1.

В том случае, когда таким образом прерывается выписывание нового оператора, необходимо обратиться к первому слева логическому условию в выписанной части ЛСА, у которого не отмечена номером стрелка. В нашем случае это логическое условие р\, стоящее после оператора Ац. Стрелку у pi пронумеруем и продолжим выписывание скобочной ФП оператора Ао (так как pi выполняется после Ао) при условии, что pi=0. В результате получаем

лоЛллйлм1!2л.

Продолжая процесс построения ЛСА таким же образом, получаем последовательно:

Л, ftf* А, дtftMVA, /jaicuf1;

Л ft j2 j1 Л ps ps№4* Л3 /72t«tH3 Л3;

А0 Pat2!1 Лг Р13 /Н11= Л2 раюН 3 ftAft>!2;

л0 н1 лх А t3 p2t4 а*нв Л л!«! V л3: л Ы<4 V Л; Л ftt ftt3 ftt4 «I1!2 А рг f2 ©t1!8 3ftA1 ftK2;4 Л

li окончательно

Я --= Л0 Л2 j,i Лх Plf ptf coH2 Л3 ft f (о> A, ft f1 ftt3©f2 4 Л,.

пример 3.10. пусть задана система фп, полученная в примере 2.9. необходимо построить лса.

Решение. по заданным фп получаем скобочные фп:

Аг -- р2 (ру А.\1 py А3) V Рг А ; [ A2-r Pl A3\J £, А г ; л3 - piv*/pii л* pi (рз 2V рз з) V pi Л • затем строим лса:

Л0 At рг, т pi ti1 Аг р± г л8 р! т А± рг t рз т <в т1 i Л. 1р2 т2 pi tl1 А2 рг г л3 pj ti2 Ai Рг т рз т ы tl i Л лх р2 г2 pi т3 i1 л2 pi tl3 л3 Рг ti2 л4 pi г р3 т » t1; Лi4 Аг р212 pi т3 -i1 л2 рх т413 А3 рг и2 л pi t рз т a т1; A, i* Аг р Т2 pi Т3 i1 А2 рг т4 i 3 л3 рх т* 42 л pi Т рз Г *> t1; £6

<4о i4 Aip, J2 л л л pt т4 i3 As Pi t412 A, Pi T5 Ps T <o T116 Ak. И, наконец, получаем ЛСА

SI = Ло i4 л Pa t2 Pi T311 Л2 Pi T4 i3 Лз Pi t4 л Л4 Pi t6 Рз Т3 ш T1 Is Ah.

3.5. Объединение логических схем алгоритмов

Как было отмечено в разд. 3.3, для удобства составления ЛСА весь алгоритм функционирования дискретного устройства представляют в виде алгоритма выполнения частных ЛСА, описывающих отдельные этапы работы ДУ. Однако в каждую из таких частных ЛСА могут входить одни и те же операторы и логические условия. Поэтому, когда вместо символов частных ЛСА будут подставлены соответствующие выражения из операторов и логических условий, общая ЛСА, описывающая весь алгоритм функционирования ДУ, может оказаться далеко не минимальной. При этом в такой ЛСА могут повторяться не только логические условия, но и операторы.

Для минимизации ЛСА с повторяющимися операторами и логическими условиями может быть использован так называемый метод объединения логических схем алгоритмов. Рассмотрим пример объединения двух ЛСА. Общий случай одновременного объединения нескольких ЛСА описан в [З].

Пример 3.11. Пусть необходимо объединить две частные ЛСА, полученные в примере 3.6 [см. (3.9) и (3.10)]. При этом общая ЛСА имеет вид

-aitiatJcuTain.i"(з.25)

Решение. На основе логических схем (3.9) и (3.10) составим матричные схе,мы алгооитма:



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36]