3. Логічні операції та функції. Способи задання функцій. Функціонально повні системи логічних операцій

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

АБО (диз'юнкція) ,

І (кон'юнкція) ,

НЕ (інверсія) відповідно.

Логічна операція АБО-НЕ (операція Пірса) , . Логічна операція І-НЕ (операція Шеффера) , . Логічна операція Нерівнозначність (сумою за модулем 2) . Логічна операція Рівнозначність - .

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

Для виконання перетворень функцій в алгебрі логіки використовується ряд законів та тотожностей, основні з яких наведені нижче:

Закон перестановки (комутативний): , ;

Закон сполучення (асоціативний): , ;

Закон розподілу (дистрибутивний): , ;

Закон повторення: , ;

Закон інверсії (правило Де Моргана): , ;

Закон заперечення: ; ;

Закон подвійного заперечення: ;

Закон поглинання: ; ;

Закон склеювання: ;

Правила операцій з константами: , , , , , ;

Додаткові тотожності: , .

Крім того, необхідно враховувати наступні властивості логічних операцій:

Операція НЕ	Операція І	Операція АБО

Функціонально повна система логічних елементів - це такий набір елементів, за допомогою якого можна реалізувати будь-яку функцію, незалежно від її складності. Оскільки логічна функція є комбінацією простих функцій - диз'юнкції, кон'юнкції та інверсії, то набір з елементів АБО, І, НЕ є функціонально повним. Аналогічно можна сказати і про елементи, що реалізують функції І-НЕ та АБО-НЕ.

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

Аналітичний - використанням математичного апарату алгебри логіки. Координатний - карти Карно. При наявності n змінних карти Карно складаються з 2ⁿ полів, куди записують значення функції при відповідному наборі аргументів.

4. Форми запису логічних функцій. Диз'юнктивна (кон'юктивна) нормальна форма

Форми логічних функцій та їх використання для синтезу логічних схем

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

Мінтермом називають функцію, що набуває одиничного значення при одному з усіх можливих наборів аргументів, а макстермом називають функцію, яка набуває нульового значення при одному з можливих наборів і одиничного значення при всіх інших. Мінтерм алгебрично є кон'юнкцією аргументів, а макстерм — диз'юнкцією аргументів. Якщо використовують двійкову систему і число наборів аргументів п, то число мінтермів або макстермів N = 2ⁿ.

Диз'юнкцію будь-якого числа елементарних кон'юнкцій називають диз'юнктивною нормальною формою (ДНФ). Наприклад, а + be + abc + аbс.

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

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

• виразити всі операції через операції кон'юнкції, диз'юнкції та інверсії;

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

• розкрити дужки, застосувавши закон дистрибутивності;

• звести кон'юнкції (диз'юнкції) до елементарних операцій.

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

1. За кожним набором двійкових змінних, за яких функція набуває значення 1, скласти елементарні кон'юнкції (мінтерми).

2. В елементарну кон'юнкцію записати неінвертованими змінні, що задані одиницею в таблиці істинності, а інвертованими — ті змінні, які в таблиці істинності задані нулем. Здобутий результат називають конституентами одиниці.

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

1. За кожним набором двійкових змінних, за яких функція набуває значення 0, скласти елементарні диз'юнкції (макстерми).

2. В елементарні диз'юнкції записати неінвертованими змінні, задані нулем у таблиці істинності, а інвертованими — ті змінні, які в таблиці істинності задані одиницею. Здобуті суми називають конституентами нуля.

3. Елементарні диз'юнкції об'єднати знаком кон'юнкції.