загрузка...
загрузка...
На головну

Опис ФАЛ у вигляді алгебраїчного виразу

Дивіться також:
  1. II. опис моделі
  2. VI. Фразеологізми і крилаті вирази.
  3. Аналітичний опис дроблень
  4. Аналітичний опис крайових спотворень
  5. Аналітичний опис процедури вимірювань
  6. арифметичні вирази
  7. арифметичні вирази
  8. Арифметичні вирази і операції
  9. Арифметичні ВИРАЗУ І ОПЕРАЦІЇ
  10. Архітектурний креслення як засіб вираження проектного задуму
  11. Бароко - це театр. Архітектура бароко - пишні декорації. А статуї, статуї стали схожі на акторів. Рухи, жести вирази облич повторювали те, що створювалося на сцені.
  12. Байка Вовк і Ягня - крилаті вирази

Таблиця істинності для трьох змінних

Словесний опис ФАЛ

Проілюструємо словесний опис ФАЛ на прикладі.

Приклад 1.5.Логічна функція трьох змінних дорівнює одиниці, якщо хоча б дві вхідні змінні дорівнюють одиниці (рис.1.1).

Даний вид опису найбільш часто застосовується для початкового, вихідного опису поведінки логічного пристрою.

Опис ФАЛ у вигляді таблиці істинності

Таблиця, що містить всі можливі комбінації вхідних змінних хn-1 ... х1хо і відповідні їм значення вихідних змінних zi; називається таблицею істинності або комбінаційної таблицею. У загальному випадку таблиця істинності містить 2n рядків і т + n стовпців. Існують таблиці істинності змінних і функцій.

Таблиця істинності змінних

Проілюструємо побудову таблиці істинності на прикладі.

Приклад 1.6.Скласти таблицю істинності (табл. 1.4) для ФАЛ з прикладу 1.5.

Р і ш е н і е. Ця таблиця має по чотири стовпці і рядки.

Таблиця 1.4

Таблиця істинності функцій

Таблиця істинності для функцій одного аргументу представлена в табл.1.5

 аргументx
 табл.1.5

Якщо число аргументів функції одно n, то число різних сполучень (наборів) значень

n

аргументів становить 2n, А число різних функцій і аргументів 22 . Так, при n = 2 число наборів значень аргументів дорівнює 22 = 4, число функцій 24 = 16. Таблиця істинності функцій двох аргументів представлена табл. 1.6.


Табл. 1.6

У табл. 1.7 наведено перелік логічних операцій, які використовуються під час запису логічних виразів.

Таблиця 1.7

Таблиця логічних операцій

 Позначення логічних операцій  Таблиця істинності  як читається  Назва операції
x1
 Основне  Додаткові тільні x2
x1 x2 x1 x2 x1 U x2 x1 & x2 x1 · x2 x1 и x2  кон'юнкція; логічне І; логічне твір
x1 U x2 x1 + x2 x1 U x2 x1 або x2  диз'юнкція; логічне АБО; логіческаясумма
x1 ® x2 x1 E x2 x1 ® x2  якщо x1 , то x2; x1 тягне x2; x1 имплицирует x2  імплікація
x1 ~ x2 x1 ? x2 x1 « x2 x1 ~ x2 x1 еквівалентно x2  еквівалентність; рівнозначність
x1 A x2 x1 E x2 x1 A x2  або x1, або x2; x1 нееквівалентно x2  Сума по модулю; нерівнозначності; виключає АБО
x1 r x2 x1 ® x2 x1 E x2 x1r x2 x1 заборона по x2; x1, але не x2  заборона; заперечення імплікації
x1 i x2 - x1 i x x1 и x2несумісні  Логічне І-НЕ; елемент (штрих) Шеффера; заперечення кон'юнкції
x1 ? x2 - x1 ? x2  ні x1, ні x2  Логічне АБО-НЕ; стрілка Пірса; функція Вебба; заперечення диз'юнкції
х х  НЕ х  Логічне НЕ; інверсія; логічне заперечення
х

Таблиці істинності дають повну інформацію про пристрій і широко використовуються для їх опису. Для цього вхідні змінні мають в таблиці істинності так, що їх послідовність утворює двійковечисло x1x0 , соответствующееномерунабора i в десятковій системі числення (тому колонку з номерами наборів часто в таблицю не включають).

Складемо таблицю (табл.1.8) повного набору логічних функцій для пристрою з двома входами і 16-ю виходами. Кожна функція Yn є результатом виконання однієї з 16-ти операцій над вхідними змінними x1 и x0 на всіх i -их наборах.

Таблиця 1.8

 Табл. істинності    Назва операції (функції)
i 0 1 2 3  Запис операції (функції)
x1 0 0 1 1
x0 0 1 0 1
yo 0 0 0 0 0  постійний 0
Y1 0 0 0 1 x1 · x0  Кон'юнкція (І)
Y2 0 0 1 0 x1 ® x0 = x1 x0  заборона по x0
Y3 0 0 1 1 x1  Мінлива x1
Y4 0 1 0 0 x0 ® x1 = x1 x0  заборона по x1
Y5 0 1 0 1 x0  Мінлива x0
Y6 0 1 1 0 x1A x0 = x1 x0 + x1 x0  нерівнозначності
Y7 0 1 1 1 x1 + x0  Диз'юнкція (АБО)
Y8 1 0 0 0 x1 ? x2 = x1 + x0  Стрілка Пірса (АБО-НЕ)
Y9 1 0 0 1 x1 ~ x0 = x1 x0 + x1 x0  рівнозначність
Y10 1 0 1 0 x0  Інверсія (НЕ) x0
Y11 1 0 1 1 x0 ® x1 = x1 + x0  імплікація від x0 к x1
Y12 1 1 0 0 x1  Інверсія (НЕ) x1
Y13 1 1 0 1 x1 ® x0 = x1 + x0  імплікація від x1 к x0
Y14 1 1 1 0 x1 i x0 = x1 x0  Штрих Шеффера (І-НЕ)
Y15 1 1 1 1 1  Постійна 1

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

Функції одного аргументу (табл. 1.5) видаються такими виразами:

f0 (х) = 0 (константа 0), f1 (Х) = х,

f2 (х) = х, f3 (х) = 1 (константа 1).

Пристрої, що реалізують функції f0 (х), f1 (х) і f3 (х), Виявляються тривіальними. Як видно з рис. 1.1, формування функції f0 (х) Вимагає розриву між входом і виходом з підключенням виходу до загальної точки схеми, формування функції f1 (х) - З'єднання входу з виходом, формування функції f3 (х) - Підключення виходу до джерела напруги, відповідного лог.1. Таким чином, з усіх функцій одного аргументу практичний інтерес може представляти лише функція f2 (х) = х (Логічне НЕ).

З порівняння таблиць істинності функцій f0 (х), ... f15 (х) (Табл. 1.6) з таблицями істинності логічних операцій (табл. 1.7) слід:

 x f0 (X) x f1 (X) f3 (X)

+

-

Мал. 1.1

При описі ФАЛ алгебраїчним виразом використовуються дві стандартні форми її подання.

Диз'юнктивній нормальною формою (ДНФ) називається логічна сума елементарних логічних творів, в кожне з яких аргумент або його інверсія входить один раз.

Отримано ДНФ може бути з таблиці істинності з використанням наступного алгоритму:

а) для кожного набору змінних, на якому ФАЛ дорівнює одиниці, записують елементарні логічні твори вхідних змінних, причому змінні, рівні нулю, записують з інверсією. Отримані твори називають констітуентамі одиниці;

б) логічно підсумовують все констітуенти одиниці.

Приклад 1.7.Запис ДНФ для ФАЛ, заданої в прикладі 1.6.

Р і ш е н і е. Відповідно до наведеного алгоритму з табл. 1.4 отримаємо:

           
     


y (x2, x1, x0) = X2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0

Діз'юнктівную нормальну форму, отриману внаслідок підсумовування констітуєнт одиниці, називають досконалої (СДНФ).

Кон'юнктівной нормальною формою (КНФ) називається логічне твір елементарних логічних сум, в кожну з яких аргумент або його інверсія входять один раз.

Отримано КНФ може бути з таблиці істинності з використанням наступного алгоритму:

а) для кожного набору змінних, на якому ФАЛ дорівнює нулю, записують елементарні логічні суми вхідних змінних, причому змінні, значення яких дорівнюють одиниці, записують з інверсією. Отримані суми називають констітуентамі нуля;

б) логічно перемножують всі отримані констітуенти нуля.

Приклад 1.8.Запис КНФ для ФАЛ, заданої в прикладі 1.6.

Р і ш е н і е. Застосовуючи вищенаведений алгоритм до табл. 1.4, отримуємо.

y (x2, x1, x0) = (X2 + x1 + x0) (X2 + x1 + x0 ) (X2 + x1 + x0) (X2 + x1 + x0)

Кон'юнктівную нормальну форму, отриману внаслідок підсумовування констітуєнт нуля, також називають досконалої (СКНФ).

Розглянуті методики дозволяють отримати математичну форму запису для самої функції. Іноді зручніше застосовувати не саму ФАЛ, а її інверсію. В цьому випадку при використанні вищеописаних методик для запису СДНФ необхідно вибирати нульові, а для запису СКНФ - одиничні значення функції.

Приклад 1.9.Для ФАЛ з прикладу 1.6 записати СДНФ і СКНФ инверсной функції.

Р і ш е н і е. Скориставшись табл. 1.4, запишемо:

                                       
                   


СДНФ: y (x2, x1, x0) = X2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0

                                       
                   


СКНФ: y (x2, x1, x0) = (X2 + x1 + x0) (X2 + x1 + x0 ) (X2 + x1 + x0) (X2 + x1 + x0)

СПОСОБИ ЗАВДАННЯ ЛОГІЧНИХ ФУНКЦІЙ «-- попередня | наступна --» Основні аксіоми алгебри-логіки
загрузка...
© om.net.ua