Функціонально повні системи перемикаючих функцій алгебри логіки

Функціонально повною системою, або базисом, перемикаючих функцій називають систему перемикаючих функцій Х₁, Х₂, Х₃,..., за допомогою якої може бути представлена будь-яка функція алгебри логіки. Функціонально повними системами є базиси: І, АБО, НІ (базис 1); І, НІ (базис 2); АБО, НІ (базис 3); І-НІ або базис Шеффера (базис 4); АБО-НІ або Пірса (базис 5) і І-АБО-НІ (базис 6).

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

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

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

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

Структури логічних елементів НІ, АБО, І, які складаються з елементів Пірса, приведені на рис. 5.

При побудові вузлів і блоків ЕОМ часто застосовують базис І-АБО-НІ (рис. 6).

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

Х=А·В і = \/ .

Це означає, що один і той же елемент буде реалізовувати з точки зору позитивної логіки функцію кон’юнкції, а з точки зору негативної логіки — диз’юнкцію.

В подальшому в якості одиниці всюди буде прийнято високий рівень напруги (позитивна логіка).

Рис. 4. Логічні схеми І(а) та АБО(б), відповідно в базисах АБО-НІ та І-НІ.

Рис. 5. Структури логічних елементів НІ, АБО, І, що складаються з елементів Пірса.

Рис. 6. Умовне графічне позначення елемента І-АБО-НІ.

Порядок виконання роботи

1. Уважно опрацюйте запропонований теоретичний матеріал. Повторіть алгоритм перетворення перемикаючих функцій з нормальної на досконалу форму.

2. Залежно від варіанту виконайте завдання:

1 варіант.

Звести до ДКНФ:

Звести до ДДНФ:

2 варіант.

Звести до ДКНФ:

Звести до ДДНФ:

Продемонструйте викладачу результати виконання роботи.

3. Завантажте табличний процесор Excel. Викличте майстер функцій. Оберіть категорію «Логічні». Повторіть порядок побудови таблиць істинності у Microsoft Excel. За допомогою таблиць істинності перевірте, чи співпадають значення функції у нормальній формі зі значенням, що ви отримали після перетворення на досконалу форму. Виконуйте завдання поступово, враховуючи правила порядку дій в алгебрі логіки. Продемонструйте викладачу результати побудови таблиць істинності.

4. Прослідкуйте, щоб кожен стовпчик даних мав відповідний до назви операції заголовок, створений у Microsoft Equation.

5. Виконайте завдання графічним способом.

6. Підготуйте звіт відповідно до встановленого зразка.

Контрольні запитання.

1. Що називають конституентою одиниці, конституентою нуля?

2. Дайте означення ДДНФ та ДКНФ.

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

4. Що називають картою Карно?

5. Сформулюйте алгоритм перетворення перемикаючої функції із ДНФ в ДДНФ за допомогою карти Карно.

6. Що називають функціонально повною системою, або базисом, перемикаючих функцій?

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