1. Логічні основи ЕОМ Основні відомості з алгебри логіки

Логічні основи ЕОМ

Основні відомості з алгебри логіки

Теоретичною основою побудови ЕОМ служать спеціальні математичні дисципліни. Однією з них є алгебра логіки, або булева алгебра (Дж. Буль - англійський математик XIX ст., Основоположник цієї дисципліни). Її апарат широко використовують для опису схем ЕОМ, їх проектування та оптимізації.

Вся інформація в ЕОМ представляється в двійковій системі числення. Поставимо у відповідність вхідним сигналам окремих пристроїв ЕОМ відповідні значення , А вихідним сигналам - значення функцій ) ( ріс.14.1 ).

В цьому випадку залежностями

де - - й вхід;

- число входів;

- -й вихід;

- число виходів в пристрої, можна описувати алгоритм роботи будь-якого пристрою ЕОМ. Кожна така залежність є "булевої функцією, у якій число можливих станів і кожної її незалежної змінної дорівнює двом" (стандарт ISO 2382 / 2-76), тобто функцією алгебри логіки, а її аргументи визначені на множині . Алгебра логіки встановлює основні закони формування і перетворення логічних функцій. Вона дозволяє представити будь-яку складну функцію у вигляді композиції найпростіших функцій. Розглянемо найбільш часто вживані з них.

Мал.14.1.

Вхідні і вихідні сигнали в схемах комп'ютера

Відомо, що кількість всіляких функцій від аргументів виражається залежністю:

при можна визначити дві основні функції ( ), Які не залежать від будь-яких змінних: , Тотожне рівну нулю ( ), І , Тотожне рівну одиниці ( ). Технічної інтерпретацією функції може бути генератор імпульсів. При відсутності вхідних сигналів на виході цього пристрою завжди є імпульси (одиниці). функція може бути інтерпретована як відключена схема, сигнали від якої не надходять до жодних пристроїв.

при залежність (14.3) дає . Уявімо залежність значень цих функцій від значення аргументу у вигляді спеціальної таблиці істинності ( табл. 14.4 ).

Таблиці істинності отримали таку назву, тому що вони визначають значення функції в залежності від комбінації вхідних сиг-лів. У цій таблиці, як і раніше, і . функція , А функція (інверсія ).

Цим функціям відповідають певні технічні аналоги. Схема, що реалізує залежність , Називається повторювачем, а схема - інвертором.

при , Тобто від двох змінних можна побудувати шістнадцять різних функцій. В табл. 14.5 представлена ​​частина з них, що має фундаментальне значення при побудові основних схем ЕОМ.

У лівій частині таблиці перераховані всі можливі комбінації вхідних змінних (набори значень), а в правій - можливі реак-ції вихідних сигналів. В табл. 14.5 представлені функції , Повністю відповідають повноваженням табл. 14.4 , А також нові, часто використовувані і цікаві функції . При цьому місце розташування функцій і їх нумерація в таблиці особливого значення не мають. По даній таблиці неважко скласти аналітичний вираз (залежність) для кожної функції від двох аргументів виду (14.2). Для цього набори змінних, на яких функція приймає значення одиниці, записуються як кон'юнкції (логічне множення) і зв'язуються знаками логічного складання. Такі форми функцій отримали назву діз'юнктівних нормальних форм (ДНФ). Якщо в цих функціях кон'юнкції містять всі без винятку змінні в прямому або інверсному значеннях, то така форма функцій називається досконалою.

функція являє собою функцію логічного додавання, диз'юнкцію. Вона приймає значення одиниці, якщо значення одиниці має хоча б одна змінна або :

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

функція є инверсной функцією по відношенню до :

Вона має назву заперечення диз'юнкції. Іноді в літературі зустрічається її спеціальну назву "стрілка Пірса", по імені математика, що досліджував її властивості.

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

функція є инверсной функцією по відношенню :

Вона називається заперечення кон'юнкції або "штрих Шеффера".

функція називається логічною рівнозначно, вона приймає значення одиниці, якщо все її змінні мають однакове значення (або 0 або 1):

функція є инверсной по відношенню і називається не-рівнозначні:

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

З перерахованих функцій двох змінних можна будувати скільки завгодно складні залежності, що відображають алгоритми перетворення інформації, яка представлена ​​в двійковій системі числення. Алгебра логіки встановлює правила формування логічно повного базису найпростіших функцій, з яких можуть будуватися будь-які більш складні. Найбільш звичним базисом є набір трьох функцій {інверсія - , Диз'юнкція - , Кон'юнкція - або &}. Робота з функціями, представленими в цьому базисі, дуже схожа на використання операцій звичайної алгебри.

Алгебра логіки встановлює, що існують і інші комбінації найпростіших логічних функцій, що володіють властивістю логічної повноти. Наприклад, набори логічних функцій {інверсія, диз'юнкція} і {інверсія, кон'юнкція} також є логічно повними. Найцікавіші мінімальні базиси, що включають по одній операції { "заперечення диз'юнкції ( ) ", {" Заперечення кон'юнкції ( ) "} Або (&). Однак робота з функціями, представленими в зазначених базисах, вимагає від фахівців з проектування ЕОМ певних навичок.