Тема 5.3. Автомати і граматики. Синтаксичний аналіз.

Вказівки щодо використання літературних джерел.

Вправи до теми 5.3.

Розділ 6. ВСТУП ДО МАТЕМАТИЧНОЇ ЛОГІКИ

Тема 6.1. Алгебра висловлювань

[4, гл.15. § 4; 6 гл.І, 5 І, І; 10, гл.І, с.7, гл.2. с.25-54, 56-64, гл.З, с.70-83. 88-94, гл.4, с.125-128; 12, § І, 2.1, 2.3, 2.6, 2.6, 2.7, 3; 13. гл. 4; 2, гл.6, § 1-8; 12, § 8.1- 8.2; 16, гл.9, § 1-3; 3, гл. 4, § 7]

Вказівки щодо використання літературних джерел.

Перед вивченням цього розділу дискретної математики слід з’ясувати сутність логіки як науки, її роль у діяльності людини, зокрема форми абстрактного мислення - поняття, судження, висновок. Виходячи з того, що логіка разом з теорією множин складає основи математики, необхідно ознайомитися з парадоксами, зрозуміти їх руйнівний вплив, переконатися у незворотності процесу формалізації логіки й після цього перейти до вивчення основ математичної або символічної логіки у такій послідовності:

• сформувати уявлення про висловлювання, зв’язки, складні висловлювання;

• з’ясувати сутність проблеми встановлення істинності складних висловлювань і роль таблиць істинності;

• використати введену в розділі 2 бульову алгебру для визначення алгебри висловлювань як інструменту дослідження висловлювань, розв’язання проблеми встановлення істинності складних висловлювань, з’ясувати роль властивостей булевих операцій та алгебраїчний метод встановлення істинності;

• проаналізувати властивий математиці метод розв’язання проблем шляхом зведення складних висловлювань до нормальних форм та двоїстих висловлювань.

Слід пов’язати уявлення про вентильні схеми й висловлювання, надавши струнким математичним конструкціям здатності моделювати функціонування технічних пристроїв. Тим самим ми надаємо можливість застосування бульової алгебри дляя прийняття й обґрунтування інженерних рішень. У плані розвитку уявлень про прикладне значення бульової алгебри необхідно розглянути проблему структурного синтезу автоматів, розв’язання якої вимагає використання методів математичної логіки й теорії автоматів. Дійсно, скінчені автомати широко використовуються в техніці. З одно­го боку, вони виступають як засіб проектування нових пристроїв, а з іншого - як математична модель для описання функціонування створюваних пристроїв. Верстати з числовим програмним управлінням, комп’ютери, автомати для продажу поштових листівок, газованої води та багато інших пристроїв народилися у початковому вигляді у свідо­мості конструкторів як скінчені автомати. Проте, якщо скінчений автомат як математичний об’єкт можна задати матрицями й графами, то скінчений автомат як пристрій чи частина пристрою вимагає відповідної матеріальної реалізації. Звичайно автомати конструюють з більш простих, що називаються елементарними, автоматів, які виготовляє промисловість. Комп’ютер проектується як автомат, що складається з елементів логіки і пам’яті, кожен з яких є елементарним ав­томатом.

Задача структурного синтезу скінчених автоматів полягає у створенні структурної схеми (композиції елементарних автоматів), яка визначає те саме відображення Е*  В* що й вихідний скінчений автомат.

Рекомендується ознайомитись з існуючими методами структурно­го синтезу автоматів, докладно дослідити і застосувати один з них. Можна, наприклад, застосовувати метод структурного синтезу автоматів, викладений в працях [16, 3].

Фактично, задача структурного синтезу полягає у виборі типів елементарних автоматів і способу їхнього з’єднання, при якому одержана структурна схема поводить себе так само, як ви­хідний автомат.

Вибір елементарних автоматів визначається можливостями про­мисловості. За умов бурхливого розвитку технології мікросхем набір елементарних автоматів, особливо для проектування комп’ютерів, зазнає перманентних змін. У вигляді елементарних автоматів випус­каються пристрої, що складають цілі блоки й вузли сучасних комп’ютерів та інших автоматів.

Однак потреба у традиційних елементарних автоматах, таких як тригери, лінії затримки, логічні елементи (І, АБО, НІ), відчува­ється й відчуватиметься у багатьох галузях.

Розглянемо методи структурного синтезу скінчених автоматів з тригерів з окремими ходами (опис наведено у вправі 13 теми 6.1), логічних елементів І, АБО, НІ.

Оскільки практичний синтез автоматів пов’язаний з використан­ням автоматів з двома стійкими станами: 0 і 1, то стани автомата, вхідні й вихідні символи (сигнали) мають бути відповідно закодо­вані. Для цього вводяться відповідно двоїчні змінні

U_i , i= 1, …, n; m_j , j= 1, …, r; l_k , k= 1, ..., d

Реалізація функції переходів вихідного скінченого автомата пов’язана з необхідністю володіння автоматом пам’яттю (якщо авто­мат не тривіальний). Очевидно, пам’ять для структурного автомата може бути забезпечена тільки елементарними автоматами з пам’яттю. У нашому випадку такими елементарними автоматами є тригери. У зв’язку з тим, що кожний тригер має два стійкі стани, для коду­вання кожного із станів а₁, …, а_п вихідного автомата потрібен р-розрядний двоїчний код, де р = log₂ n. Роблять так, що розряд і цього коду - стан елементарного автомата U_i , який приписують як значення змінної U_i .

Для того щоб р елементарних автоматів з пам’яттю забез­печували перехід із стану в стан і вихід згідно з графом або мат­рицею вихідного автомата, необхідно визначити значення вхідних сигналів для кожного елементарного автомата і сформулювати код, що відповідає вихідному символу при даних вхідному символі й стані. Перша задача забезпечується введенням спеціальної функції збуд­ження елементарних автоматів. Кожен елементарний автомат 6 керується двома такими функціями: u_1i (t) і u_0i (t). Функція u_1i ( t ) визначає значення вхідного сигналу на одинич­ному вході тригера U_i залежно від станів усіх елементарних автоматів і коду вхідного символу висхідного автомата у момент часу t. Функція u_0i(t) виконує аналогічну роль для нульового входу U_i .

Кожна з функцій u_1i ( t), u_0i (t) i=1, …, p є булевою функцією (складним висловлюванням) змінних U_i, i= 1, …, n; m_j , j= 1, …, r. Реалізувати ці функції можна відповідними набора­ми логічних елементів І, АБО, НІ.

Друга задача (формування коду вихідного символу) розв'язуєть­ся введенням булевих функцій виходу l_k (t), k= 1,..., d. Кожна функція l_k (t), k= 1, ..., d формує k-й розряд коду вихідного символу залежно від станів усіх тригерів U_i і коду вхідного символу вихідного автомата. Роблять звичайно так, що l_k(t) визначає значення 1k-го розряду коду. Якщо l_k ( t ) вихідний сигнал не видає, то значення k-го розряду коду прий­мається 0. Функції l_k ( t ), k= 1, ..., d також реалізують за допомогою логічних елементів І, АБО, НІ.

Для визначення розрядності двоїчного коду вхідного або ви­хідного символу залежно від потужності множини вхідних або ви­хідних символів використовується той самий вираз, що й для довжи­ни коду стану.

За функціями збудження й виходів уже можна будувати структур­ну схему автомата. Для цього у створювану схему включають p тригерів. Потім для кожного тригера набором елементів І, АБО, НІ реалізують функції збудження. Аналогічно тим самим набором еле­ментів реалізують функції виходів. Приклад реалізації складного висловлювання (булевої функції) наведено у вправі 14 теми 6.1.

Один з найзручніших методів структурного синтезу автоматів - метод побудови функціональної (структурної) схеми за графом пере­ходів вихідного автомата.

Розглядається автомат Мура, заданий графом переходів або мат­рицею. Стани, вхідні й вихідні символи закодовані наборами значень змінних, відповідно . Далі стан 0 елементарного автомата v_i будемо позначати .

Аналогічно - нульо­ві значення відповідно j -го і k -го розрядів коду вхідного й вихідного символів. Значення 1 для всіх змінних співпадає з позначенням змінної. Кодування станів, вхідних і вихідних симво­лів для конкретного прикладу наведено у вправі 15 теми 6.1.

Для кожного елементарного автомата v_i записують дві узагальнені функції переходів у момент часу t+1 відповідно у стани 1 і 0.

Очевидно, функція має визначатися за матрицею або графом переходів і включати всі комбінації станів і вхідних символів, які переводять елементарний, автомат v_i. У мо­мент часу t +1 у стан 1/0/. Це дуже зручно зробити за матрицею переходів вихідного автомата.

Кожну з узагальнених функцій для елементарного автомата v_i тепер зручно записати у вигляді ДНФ, де кожна елементарна кон’юнк­ція містить значення змінних коду вхідного символу і коду стану вихідного автомата у момент часу t, при яких елементарний автомат v_i перейде у стан 1 (для у момент часу t + 1.

Легко помітити, що в ДНФ для можуть входити елементарні кон’юнкції, що містять значення у момент часу t . Звичайно, ці елементарні кон’юнкції не впли­вають на правильне функціонування автомата, оскільки автомат зали­шається у тому самому стані. Тому їх можна і включати ї не вклю­чати в ДНФ для .

Відомо, що однакові таблиці істинності можуть мати різні складні висловлювання (булеві функції). Це приводить до можли­вості вибору найзручнішої форми висловлювання для даної таблиці істинності. Цей процес називають спрощенням висловлювань. У за­дачі структурного синтезу автоматів цей процес набував величез­ного значення, оскільки дає змогу скоротити необхідну для реалі­зації автомата кількість елементарних автоматів (логічних елемен­тів І, АБО, НІ у даному випадку). Розроблені спеціальні процеду­ри мінімізації (спрощення) логічних висловлювань (булевих функцій). Але можна використовувати будь-які відомі методи.

Виявилось, що хоча включення або виключення згаданих елемен­тарних кон’юнкцій для не впливає на функціо­нування автомата, воно дуже істотно може допомогти спростити функції . Таким чином, згадані елементар­ні кон’юнкції включаються, якщо це приводить до знаходження більш зручних форм.

Для вибраних елементарних автоматів пам’яті (тригерів з роз­дільними ходами) функціями збудження елементарного автомата v_i, якщо вихідний автомат всюди виз­начений. Проте для часткових автоматів або якщо log₂ n дає не ціле число, функції збудження можуть бути записані так:

де x_1i , x_0i можуть набирати значень 0 або 1.

Функції виходів також мають вигляд ДНФ з описаними вище особ­ливостями. Очевидно, функції виходів також будуються за матрицею переходів. Визначається функція виходів для значення 1 кожною змінною коду вихідних символів. Кожна елементарна кон’юнкція ДНФ функції виходу l_і ( t ) містить код вхідного символу і стани вихідного автомата, при яких автомат видає вихідний символ, в код якого змінна l_і входить зі значенням 1.

Використовуючи відомі методи, функції виходів зводять до найзручнішого вигляду.

Після цього можна приступати до побудови структурної схеми автомата.

Приклад структурного синтезу автомата, заданого графом пере­ходів, наведений у вправі 15 теми 6.1.

Із задачею структурного синтезу автоматів пов’язані деякі важливі теоретичні проблеми. У першу чергу, варто сказати про проблему повноти. У рамках цієї проблеми можна отримати відпо­відь на важливе запитання про можливість розв’язання задачі структурного синтезу будь-якого скінченного автомата на даному наборі елементарних автоматів. Докладніше ознайомитися з цими проблемами можна в [28].

Повертаючись до теми помилок, продемонструємо тупикову циклічність визначень відомих математичних об’єктів. Досить часто на запитання про визначення класів абсолютго істинних та абсолютно хибних висловлювань можна отримати парну відповідь, що абсолютно істинне висловлювання – це заперечення абсолютно хибного висловлювання, а абсолютно хибне висловлювання – це заперечення абсолютно істинного висловлювання.

Вправи до теми 6.1.

Вправа І. Побудувати таблиці істинності висловлювань:

1) A /\ 7B \/ A /\ B \/ 7A /\ C;

2) A /\ B \/ 7A \/ 7B \/ A /\ C \/ 7C \/ A /\ C;

3) A /\ B \/ 7A \/ 7B \/ A /\ C /\ 7B \/ 7A /\ 7C;

4) C /\ B \/ 7C \/ 7B \/ C /\ A \/ 7A \/ C /\ A;

5) 7(A \/ B \/ 7C) \/ A /\ 7B /\ C \/ 7(B \/ C) \/ B /\ D;

6) С \/ С /\ B \/ B /\ A \/ 7(C /\ A) \/ 7A /\ 7C;

7) (A /\ C \/ 7A \/ 7C) /\ A /\ C /\ B \/ 7B /\ C /\ A \/ 7A /\ C;

8) A /\ B /\ C \/ A /\ B /\ 7C \/ A /\ 7B /\ C \/ 7A /\ B /\ C;

9) (A \/ B) /\ (B /\ 7C \/ 7B) \/ 7A /\ B \/ 7B /\ (7A \/ C);

10) 7(A /\ B \/ 7(A \/ 7C)) \/ 7A /\ C \/ 7B /\ (A \/ C);

11) 7(A \/ B) \/ 7(A \/ C) \/ 7(7B \/ 7C) \/ 7A /\ (B \/ C) \/ 7(7B \/ C);

12) (A \/ B) /\ (B \/ 7C) \/ (7A \/ 7B) /\ 7B \/ C;

13) A /\ B \/ 7A /\ 7B \/ A /\ 7B;

14) A /\ B \/ 7B /\ C \/ B;

15) (A \/ B) /\ (7B \/ A) \/ A /\ C;

16) 7(7(A \/ A) \/ (B \/ 7B)) \/ 7B;

17) 7(7A \/ B) /\ 7(A /\ B) \/ B;

18) (A \/ B) /\ ( 7B \/ A) \/ B /\ C \/ A /\ 7B \/ B /\ 7C;

19) 7A /\ B \/ A /\ 7B \/ A /\ B.

Вправа 2. Перевірити за допомогою таблиць істинності наведені властивості булевих операцій щодо відношення тотожності висловлювань:

1) A /\ A = A 2) A \/ A = A

3) A /\ B = B /\ A 4) A \/ B = B \/ A

5) A /\ (B /\ C) = (A /\ B) /\ C 6) A \/ (B \/ C) = (A \/ B) \/ C

7) A /\ (B \/ C) = (A /\ B) \/ (A /\ C) 8) A \/ (B /\ C) = (A \/ B) /\ (A \/ C)

9) A /\ X = X 10) A /\ I= A

11) A \/ X = A 12) A \/ I = I

13) A \/ 7A = I 14) A /\ 7A = X

15) 77A = A 16) 7(A /\ B) = 7A \/ 7B

17) 7(A \/ B) =7A /\ 7B

Вправа 3. Використовуючи властивості 1 - 17 булевих операцій (див. вправу 2), спростити висловлювання вправи 1.

Приклад. Спростимо висловлювання А /\ 7 В \/ A /\ B \/ 7 А /\ С

A /\ 7B \/ A /\ B \/ 7A /\ C = A /\ (7B \/ B) \/ 7A /\ C - використовуючи властивість 7);

A /\ (7B \/ B) \/ 7A /\ C = A /\ I \/ 7A /\ С -використовуючи властивість 13);

A /\ I \/ 7A /\ C^: = ^:A \/ 7A /\ C - використовуючи властивість 10);

A \/ 7A /\ C = (А \/ 7A) /\ (A \/ C) - використовуючи властивість 8);

(А \/ 7A) /\ (A \/ C) = I /\ (A \/ C) - використовуючи властивість 13);

I /\ (А \/ C) = A \/ C - використовуючи властивість 10).

Для зручності пропонується використовувати такий запис перетворень висловлювань:

(7) (13) (10)

A /\ 7B \/ A /\ B \/ 7A /\ C = A /\ (7B \/ B) \/ 7A /\ C = А /\ I \/ 7A /\ C = A \/

(8) (13) (10)

7A /\ C = (А \/ 7A) /\ (A \/ C) = I /\ (A \/ C) = A \/ C .

Вправа 4. Встановити наявність відношення логічного наслідку між висловлюваннями за такою таблицею:

A1	B1	C1	A	B	C	D	E	F	G	H
X	X	X	X	I	I	X	X	I	I	X
X	X	I	I	I	I	I	I	X	I	X
X	I	X	X	X	I	X	X	X	X	X
X	I	I	I	I	I	I	I	X	I	I
I	X	X	X	I	I	X	I	I	X	I
I	X	I	I	I	I	I	I	X	I	I
I	I	X	I	I	I	I	I	I	I	I
I	I	I	I	X	X	X	X	I	I	X

Вправа 5. Знайти досконалі ДНФ та КНФ для висловлювань, заданих таблицею істинності:

Прості висловлювання

Складні висловлювання

A

B

C

A1

A2

A3

A4

A5

A6

A7

A8

A9

A10

A11

A12

A13

A14

A15

Х

Х

X

Х

Х

X

X

Х

X

Х

Х

I

I

I

I

I

I

I

X

X

I

I

I

X

I

I

X

I

X

X

I

I

I

X

I

I

X

I

X

X

I

I

X

I

I

I

X

I

X

I

X

I

X

I

X

I

I

I

X

I

X

X

I

I

X

X

X

X

X

I

I

X

I

X

X

X

I

X

I

X

X

I

I

I

I

X

X

X

I

I

I

X

I

I

I

X

I

I

I

X

I

X

I

X

X

I

X

I

I

I

X

X

X

I

I

I

I

I

I

I

X

I

I

X

I

I

I

I

I

I

I

I

X

I

I

I

I

X

X

X

I

X

X

X

Приклад: Знайдемо досконалу ДНФ для складного висловлювання А₁ поєднуючи диз’юнкцією елементарні кон’юнкції, що відповідають рядкам, де висловлювання А₁ набуває значення І:

А₁= 7А /\ 7В /\ С \/ 7А /\ B /\ С \/ А /\ 7В /\ С \/ А /\B /\ C.

Приклад: Знайдемо досконалу КНФ для складного висловлювання А₇. Для цього знайдемо спочатку досконалу ДНФ для 7А₇:

7А₇ = 7А /\ 7B /\ 7С \/ А /\ 7В /\ С,

а потім використаємо властивості 16 і 17 вправи 2, щоб отримати досконалу КНФ для А₇ із знайденої досконалої ДНФ для 7А₇:

А₇ = 7(7А /\ 7B /\ 7С \/ А /\ 7В /\ С) = 7(7А /\ 7В /\ 7C) /\ 7(А /\ 7B /\ C) = (A \/ B \/ 7С) /\ (7А \/ B \/ 7С).

Вправа 6. Використовуючи тотожності бульової алгебри, звести до нормальної форми та визначити чи є абсолютно істинними або абсолютно хибними такі висловлювання:

1) А ~ (B /\ 7A) С 2) A /\ 7B ~ A 7C

3) (B \/ А) ~ (B /\ C)  7А 4) B  7С ~ A  7С

5) (B \/ 7A)  (B /\ C) \/ (B /\ 7C)6) A  (B \/ C) \/ (7B \/ C)

7) A \/ B  7A \/ C ~ A /\ C 8) (A  B) \/ (7A /\ C)

9) A  B ~ 7А  B 10) A  B ~ А  7B

11) 7А  (A  B) 12) (7B  7A)  ((7B  A) B).

Приклад: Розглянемо висловлювання 7(A \/ B) ((A \/ B) C). Спочатку спробуємо встановити його абсолютну істинність зведенням до КНФ. За допомогою тотожності 7A \/ B = A  B звільнимося від зв’язки "Імплікація", отримавши висловлювання 77(A \/ B) \/ (7(A \/ B) \/ C). Використовуючи послідовно тотожності 15, 17 вправи 2, спростимо висловлювання, отримавши (A \/ B) \/ ((7A /\ 7B) \/ C). Потім, двічі використовуючи тотожність 8 вправи 2, отримаємо КНФ початкового висловлювання: (A \/ B \/ 7A \/ C) /\ (A \/ B \/ 7B \/ C).

Оскільки в кожній диз’юнкції отриманої КНФ міститься пара висловлювань вигляду А_i та 7А_i (А та 7А в першій диз’юнкції, В та 7В - у другій), то висловлювання є абсолютно істинним.

Вправа 7. Навести приклади складних абсолютно істинних та абсолютно хибних висловлювань.

Вправа 8. Побудувати зі складних висловлювань А₁, А₂ ,..., А₁₅ вправи 5 абсолютно істинне та абсолютно хибне висловлювання. Довести абсолютну істинність та абсолютну хибність висловлювань, використовуючи властивості нормальних форм.

Вправа 9. Побудувати вентильні схеми, що відповідають висловлюван­ням вправи І теми 6.1.

Вправа 10. Навести складне висловлювання, яке реалізується такою вентильною схемою:

Вправа 11. Спростити висловлювання, які реалізуються вентильними схемами вправи 10. Навести вентильні схеми спрощених висловлювань.

Вправа 12. Задати матрицями переходів елементарні автомати без пам’яті, які реалізують операції булевої алгебри висловлювань: заперечення (НІ) , диз’юнкція (АБО), кон’юнкція (І).

Вправа 13. Тригер з окремими входами - один із елементарних автоматів з пам’яттю. Він має два стійких стани (0 і 1), два входи: нульовий і одиничний. На кожен із входів подається свій вхідний сигнал, причому кожен вхідний сигнал може мати значення 0 або І. Не можна на обидва входи подавати сигнал 1. Тригер залишається в стані 0, якщо на одиничний вхід подається сигнал 0 (сигнал на нульовому вході може бути будь-яким). Аналогічно, тригер залишається в стані 1, якщо на нульовий вхід подається сигнал 0, причому сигнал на одиничному вході може бути будь-яким. Перехід із стану 0 в стан 1 викликається подачею сигналу 1 на одиничний вхід. Зворотній перехід викликається подачею сигналу 1 на нульовий вхід. Задати тригер з окремими входами матрицею і графом переходів.

Вправа 14. Використовуючи логічні елементи І, АБО, НІ, побудувати схему, яка реалізує ту ж таблицю істинності, що й висловлювання вправи 1 теми 6.1.

Приклад: Розглянемо висловлювання 7(А /\ В \/ 7(A \/ 7C)) \/ 7A /\C \/ 7B /\ (A \/ C). Згідно з дужковим записом та уявленнями про ранги зв’язок, визначаємо порядок виконання зв’язок. Висловлювання 7С можна реалізувати за допомогою елемента НІ. Тоді висловлювання A \/ 7C буде реалізовано елементом АБО, на одному вході якого висловлення А, а на другому 7С. Висловлювання 7(A \/ 7C) реалізуємо, подавши вихід елемента АБО, який реалізує висловлення А \/ 7С , на елемент НІ. Подальшою повинна бути реалізована зв’язка А /\В, що можна виконати елементом I з входами А і В. Далі переходимо до реалізації висловлювання А /\ В \/ 7(A \/ 7C), що можна зробити за допомогою елемента АБО. Продовжуючи цей процес згідно з порядком виконання зв’язок, отримаємо таку схему:

Вправа 15. Синтезувати скінченні автомати, які задані у вправах 1, 6, 7 , 12, 13, 16, 19, 20 теми 5.1, використовуючи елементарні автомати таких типів: тригери з окремими входами; ло­гічні елементи І, АБО, НІ.

Приклад: Нехай скінчений автомат задано графом переходів:

Побудувати функціональну схему автомата, використовуючи три­гери з окремими входами, логічні елементи І, АБО, НІ.

І. Визначаємо кількість Р елементарних автоматів, необхід­них для побудови автомата з чотирма станами за формулою Р = log₂ 4 = 2. Позначимо елементарні автомати U₁ , U₂ .

2. Закодуємо стани автомата станами елементарних автоматів:

a₁ - U₁U_2, a₂ - U₁ Ū₂ a ₃ - Ū₁ U_2, a ₄ - Ū₁ Ū_2.

Побудуємо матрицю сполучень автомата:

Матрицю будуємо за графом переходів. Елемент на перетині рядка а_i. і стовпця а_j - позначення ребра графа, яке поєднує вершини а_i та а_j. Якщо є паралельні ребра, то використовуємо знак \/.

U₁

Ū₁

4. Для кодування трьох вхідних символів достатньо двох двійкових змінних m₁ і m₂ .

Закодуємо вхідні символи:

e ₁ - m₁ m_{2 ,} e₂ - m₁ m_{2 ,}

e ₃ - m₁ m_{2 .}

5. Запишемо узагальнену функцію переходів першого елементарного автомата U₁ :

U₁(t+1) = e₁ а₁ \/ e₂ а₁ \/ e₁ а₂ \/ e₃ а₂ \/ e₃ а₃ \/ e₃ а₄

При цьому включаємо в узагальнену функцію переходів автомату складову для кожного ненульового елемента матриці сполучень у стовпцях станів, код яких містить U₁.

Переписуємо отриману функцію, враховуючи кодові позначення станів і вхідних символів:

Ū ₁( t+1)=m₁ m₂ U₁U₂ \/ m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ \/ m₁ m₂ U₁Ū₂ \/ m₁ m₂ Ū₁ U₂ \/ m₁ m₂ Ū₁ Ū₂

Аналогічно робимо 1 для другого стану першого елементарного автомата U_1.

Ū₁(t+1)=e₃ a₁ \/ e₂ a₂.

Враховуючи кодові позначення, отримуємо

Ū ₁(t+1)=m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū_2.

6. Запишемо функцію збудження першого елементарного автомата:

U ₁₁(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ Ū₁ U₂ \/ b₁ m₁ m₂ U₁U₂ \/ b₂ m₁ m₂ U₁U₂ \/

\ / b₃ m₁ m₂ U₁Ū₂ \/ b₄ m₁ m₂ U₁Ū₂ \/ b₁₁ (U₁₁(t+1) \/ Ū₁(t+1) ),

де коефіцієнти b₁, b₂ , b₃, b₄ , b₁₁ можуть приймати значення із множини {0,1} і використовуються при мінімізації функцій.

Функція збудження будується за стовпцями матриці переходів, код яких містить, причому коефіцієнти b_i використовуються при включенні елементів рядків, код яких містить U₁ .

Аналогічно побудуємо функцію збудження першого елементарного автомату за другим входом /зараз вибираються тільки елементи зі стовпців, код яких містить Ū₁ , причому коефіцієнти b_i , використовуються для запису складових функції збудження для елементів рядків, код яких містить Ū₁. ):

U ₀₁(t) = m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ \/ b₀₁ (U₁(t+1) \/ Ū₁(t+1) ),

де b₀₁ є {0, 1}.

7. Повторюємо крок 5 для запису узагальненої функції переходів другого елементарного автомата Ū₂ (тільки зараз включаємо складові для ненульових елементів матриці в стовпцях, код яких містить U₂ ).

U ₂(t+1) = m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ \/ m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ U₁Ū_2.

При перших зверненнях до алгоритму синтезу спочатку рекомендується записувати функції переходів /а також функції збудження/ насамперед без кодових позначень, а потім вже підставити коди вхідних символів і станів. Так, у нашому прикладі, узагальнені функції другого елементарного автомату можна записати у вигляді

U₂(t+1) = e₁ а₁ \/ e₁ а₂ \/ e₃ а₄ \/ e₃ а₁ ;

Ū₂(t+1) = e₂ а₁ \/ e₃ а₂ \/ e₃ а₃ \/ e₂ а₂ .

Підставимо коди вхідних символів і станів у вираз для Ū ₂(t+1) .

Ū ₂(t+1) = m₁ m₂ U₁U₂ \/ m₁ m₂ U₁ Ū₂ \/ m₁ m₂ Ū₁U₂ \/ m₁ m₂ U₁ Ū_{2 .}

8. Записуємо функції збудження другого елементарного автомату, повторюючи міркування кроку 6 відносно U₂ і Ū₂ :

U ₁₂(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ U₁ Ū₂ \/ b₁ m₁ m₂ U₁U₂ \/ b₂ m₁ m₂ U₁U₂ \/

\ / b₁₂ (U₂(t+1) \/ Ū₂(t+1) ),

U ₀₂(t) = m₁ m₂ U₁U₂ \/ m₁ m₂ Ū₁ U₂ \/ b₁ m₁ m₂ U₁Ū₂ \/ b₂ m₁ m₂ U₁Ū₂ \/

\/ b₀₂ (U₁(t+1) \/ Ū₂(t+1) ),

де b₁, b₂ , b₀₁, b₀₂ незалежні в кожному виразі , приймають значення з множини {0, 1} і використовуються для мінімізації виразів.

U₁₁(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ Ū₁U₂ .

9. Виконаємо мінімізацію виразів для функцій збудження. Найважливіші рішення в процесі мінімізації пов’язані з вибором значень b_і, i = 1,2,3,4, b_0i, b_1i ( i = 1,2) для кожного виразу. Після вдалого вибору значень цих коефіцієнтів мінімізація зводиться до використання відомих методів спрощення висловлювань, наприклад шляхом використання властивостей булевих операцій, наведених у вправі 2 теми 6.1.

У нашому прикладі знаку “7“ відповідає знак "-". Мається на увазі, що кожна складова функцій збудження є елементарною кон’юнкцією елементів m_i, U_i, m_i, Ū_i (і= 1,2).

Вибір значень коефіцієнтів b_і, b_0i, b_1i, як було вказано, пов’язаний тільки зі зручністю одержання мінімальних форм. На перший погляд може здатися, що мінімальна форма виразів буде одержана, якщо усі коефіцієнти отримають нульові значення. Але аналіз виразів для U₁₂(t), U₀₂(t) показує, що це не завжди так.

Дійсно, для U₁₁(t) зручніше прийняти для всіх коефіцієнтів нульові значення.

Тоді U₁₁(t) запишеться в такому вигляді:

U ₁₁(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ Ū₁U₂ .

Використовуючи властивості булевої алгебри, отримуємо:

U ₁₁(t) = m₁ m₂ Ū₁ (Ū₂ \/ U₂ )=m₁ m₂ Ū₁

Д алі спростити вираз для U₁₁(t) можна було б у випадку існування ще одного кон’юнкта, що відрізняється від m₁ m₂ Ū₁ знаком заперечення при одному з елементів. Отримати такий кон’юнкт, варіюючи значеннями коефіцієнтів b_і, b_1i і використовуючи властивості а), б), в) булевої алгебри, неможливо.

Для U₀₁(t) мінімальну форму отримаємо, прийнявши b₀₁ = 0,

U ₀₁(t) = m₁ m₂ U₁U₂ \/ m₁ m₂ U₁ Ū₂ .

Я кщо прийняти b₀₁ =1 , то до виразу для U₀₁(t) за допомогою знака “\/” додається вираз (U₁(t+1) \/ Ū₁(t+1)) , мінімальна форма якого мав вигляд (m₁ U₁ \/ m₁ m₂ ). Очевидно, це доповнення не спрощує вираз.

Вираз для U₁₂(t) , якщо прийняти для коефіцієнтів нульові значення, набуває вигляду

U ₁₂(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ U₁ Ū₂ .

Але якщо прийняти значення коефіцієнту b₁ =1, то U₁₂(t) приймає простіший вигляд:

U ₁₂(t) = m₁ m₂ Ū₁ Ū₂ \/ m₁ m₂ U₁ .

Таким чином, прийнявши b₁ =0 , b₂ =1 , b₀₂ =0 ,спростимо вираз для U₀₂(t):

U ₀₂(t) = m₁ m₂ U₁ \/ m₁ m₂ Ū₁U₂ .

З начення коефіцієнтів b₂ та b₀₂ прийняті нульовими, оскільки мінімальна форма (U₂(t+1) \/ Ū₂(t+1)) має вигляд

m ₁ m₂ \/ Ū₁ m₁ \/ Ū₁ m₂ \/ Ū₂ m₂.

і не дозволяє опростити вираз для U₁₂(t) і . U₀₂(t).

1 0. Для кодування вихідних сигналів достатньо двох змінних. Закодуємо вхідні символи:

b ₁ - l₁ l₂ ; b₂ - l₁ l₂ ; b₃ - l₁ l₂ ; b₄ - l₁ l₂ .

11. Запишемо функції виходів для змінних l₁ , l₂ . По-перше, за матрицею переходів знаходимо елементи e_j /b_j , які містять вихідний символ b₁ або b₂ . Для кожного такого елемента матриці до функції l _i ( t ) включаємо двійку e_j a_i , де e_j cимвол вхідний із знайденого елемента матриці, а a_i. - стан, що визначає рядок, якому належить знайдений елемент матриці. Тоді функцію l _i ( t ) можна записати у вигляді диз"юнкції двійок такого вигляду.

У нашому прикладі

l₁(t)= e₂ a₁ \/ e₃ a₁ \/ e₁ a₂ \/ e₃ a₂ \/ e₃ a₄ .

Підставляючи кодові позначення станів та вхідних символів, отримуємо:

l ₁(t) = m₁ m₂ U₁U₂ \/ m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ \/ m₁ m₂ U₁Ū₂ \/ m₁ m₂ Ū₁ Ū₂ .

Цей вираз можна мінімізувати, використовуючи властивості булевої алгебри:

l ₁(t) = m₁ m₂ (U₁U₂ \/ U₁Ū₂ \/ Ū₁ Ū₂ ) \/ m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ =

m₁ m₂ U₁ \/ m₁ m₂ Ū₂ \/ m₁ m₂ U₁U₂ \/ m₁ m₂ U₁Ū₂ =

m ₂ U₁ (m₁ \/ m₁Ū₂) \/ m₁ m₂ Ū₂ \/ m₁ m₂ U₁U₂ =

m₁ m₂ U₁ \/ m₂ U₁Ū₂ \/ m₁ m₂ Ū₂ \/ m₁ m₂ U₁U₂

Продовжуючи процес мінімізації, отримуємо:

l ₁(t) = m₁ m₂ U₁ \/ m₂ U₁Ū₂ \/ m₁ U₁Ū₂ \/ m₁ m₂ Ū₂ .

Функцію l₂(t) можна записати в такому вигляді /вибираємо елементи матриці переходів, які містять вихідні символи b₁ , b₃ /:

l₂(t)= e₁ a₁ \/ e₂ a₁ \/ e₃ a₁ .

Підставляючи кодові позначення, отримуємо:

l ₂(t) = m₁ m₂ U₁U₂ \/ m₁m₂ U₁U₂ \/ m₁m₂ U₁U₂ .

Мінімальна форма l₂(t) має такий вигляд:

l₂(t) = m₁ U₁U₂ \/ m₂ U₁U₂ .

Функціональна схема скінченного автомату, заданого в нашому прикладі графом переходів

Вправа 16. Довести, що не кожне складне висловлювання може бути зображене у вигляді елементарних кон’юнкції чи диз’юнкції.

Вправа 17. Установити умови, яким повинні відповідати таблиці істинності складних висловлювань, які можуть бути зображеними у вигляді елементарних кон’юнкції чи диз’юнкції.

Вправа 18. Нехай виконується умова A B, A C. Чи можна у загальному випаджку стверджувати, що між формулами B, C існує відношення логічного слідування, тобто виконується B C чи C B.