Властивості логічних функцій

Властивості логічних функцій розглянемо на прикладі двозначної логічної функції Властивості логічних функцій - №1 - открытая онлайн библиотека яка на практиці зустрічається найчастіше. Для цього складемо табл. 1.5 всіх можливих наборів аргументів у вигляді двійкових чисел: 00, 01, 10, 11; всі 16 значень функції розміщено у порядку зростання двійкових чисел (від 0000 до 1111).

Таблиця 1.5 Двозначні логічні функції

Фун-кція Набір аргументів Назва логічної функції Визначення логічної Функції
Властивості логічних функцій - №2 - открытая онлайн библиотека Константа нуль
Властивості логічних функцій - №3 - открытая онлайн библиотека Кон’юнкція Властивості логічних функцій - №4 - открытая онлайн библиотека
Властивості логічних функцій - №5 - открытая онлайн библиотека Заборона Властивості логічних функцій - №6 - открытая онлайн библиотека Властивості логічних функцій - №7 - открытая онлайн библиотека
Властивості логічних функцій - №8 - открытая онлайн библиотека Повторення Властивості логічних функцій - №9 - открытая онлайн библиотека Властивості логічних функцій - №9 - открытая онлайн библиотека
Властивості логічних функцій - №11 - открытая онлайн библиотека Заборона Властивості логічних функцій - №9 - открытая онлайн библиотека Властивості логічних функцій - №13 - открытая онлайн библиотека
Властивості логічних функцій - №14 - открытая онлайн библиотека Повторення Властивості логічних функцій - №6 - открытая онлайн библиотека Властивості логічних функцій - №6 - открытая онлайн библиотека
Властивості логічних функцій - №17 - открытая онлайн библиотека Виняткове АБО Властивості логічних функцій - №9 - открытая онлайн библиотека Å Властивості логічних функцій - №19 - открытая онлайн библиотека v Властивості логічних функцій - №13 - открытая онлайн библиотека
Властивості логічних функцій - №21 - открытая онлайн библиотека Диз’юнкція Властивості логічних функцій - №9 - открытая онлайн библиотека v Властивості логічних функцій - №6 - открытая онлайн библиотека
Властивості логічних функцій - №24 - открытая онлайн библиотека Функція Пірсона Властивості логічних функцій - №25 - открытая онлайн библиотека
Властивості логічних функцій - №26 - открытая онлайн библиотека Рівнозначність Властивості логічних функцій - №9 - открытая онлайн библиотека ~ Властивості логічних функцій - №28 - открытая онлайн библиотека
Властивості логічних функцій - №29 - открытая онлайн библиотека Інверсія Властивості логічних функцій - №6 - открытая онлайн библиотека Властивості логічних функцій - №31 - открытая онлайн библиотека
Властивості логічних функцій - №32 - открытая онлайн библиотека Імплікація від Властивості логічних функцій - №6 - открытая онлайн библиотека до Властивості логічних функцій - №9 - открытая онлайн библиотека Властивості логічних функцій - №35 - открытая онлайн библиотека
Властивості логічних функцій - №36 - открытая онлайн библиотека Інверсія Властивості логічних функцій - №9 - открытая онлайн библиотека Властивості логічних функцій - №38 - открытая онлайн библиотека
Властивості логічних функцій - №39 - открытая онлайн библиотека Імплікація від Властивості логічних функцій - №9 - открытая онлайн библиотека до Властивості логічних функцій - №6 - открытая онлайн библиотека Властивості логічних функцій - №42 - открытая онлайн библиотека
Властивості логічних функцій - №43 - открытая онлайн библиотека Функція Шефера Властивості логічних функцій - №44 - открытая онлайн библиотека
Властивості логічних функцій - №45 - открытая онлайн библиотека Константа одиниця

Всі наведені 16 логічних Функцій на практиці не застосовуються, бо, як видно з табл. 1.5, яка, до речі, має симетрію, функції Властивості логічних функцій - №2 - открытая онлайн библиотека і Властивості логічних функцій - №45 - открытая онлайн библиотека тривіальні, Властивості логічних функцій - №8 - открытая онлайн библиотека , Властивості логічних функцій - №14 - открытая онлайн библиотека , Властивості логічних функцій - №50 - открытая онлайн библиотека Властивості логічних функцій - №36 - открытая онлайн библиотека - не залежать від одного з аргументів. Хоча решта десять функцій залежать від двох аргументів, однак і серед них е такі, які можна одержати через інші.

Аналогічно арифметичним операціям у бульовій алгебрі також існує поняття "першості виконання" операції, що визначає, яка з логічних операцій має виконуватися раніше. Отже, для логічних операцій першість визначається у такій послідовності: 1 - заперечення, 2 –кон’юнкція, 3 – диз’юнкція, 4 - імплікація, 5 - рівнозначність. При наявності у виразі логічної функції круглих дужок ступінь першості збільшується на одиницю.

Зауважимо, що деякі з наведених у табл. 1.5 функцій одержують методом перенумерації (перейменування або декомпозиції) аргументів логічних функцій. Наприклад, функція Властивості логічних функцій - №32 - открытая онлайн библиотека отримується з функції Властивості логічних функцій - №39 - открытая онлайн библиотека , якщо Властивості логічних функцій - №9 - открытая онлайн библиотека перенумерувати на Властивості логічних функцій - №6 - открытая онлайн библиотека і навпаки, беручи набір аргументів справа наліво або зліва направо. Функцію Властивості логічних функцій - №43 - открытая онлайн библиотека можна отримати з функції Властивості логічних функцій - №36 - открытая онлайн библиотека підстановкою замість Властивості логічних функцій - №9 - открытая онлайн библиотека іншою функції Властивості логічних функцій - №3 - открытая онлайн библиотека (тобто проінвертувавши набір аргументів). Така операція називається суперпозицією. Отже, застосовуючи метод суперпозицій, можна одержати більш складні логічні функції. При цьому виникає питання, чи можливий набір більш простих функцій, за допомогою яких можна було б отримати як завгодно складну логічну функцію. З практичної точки зору це дуже важливе питання, бо воно стосується технології виготовлення мікросхем і т. ін. З теоретичної точки зору воно пов’язане з основним поняттям бульової алгебри - функціональною повнотою системи логічних функцій.

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

Функціонально повних наборів-базисів можна отримати досить багато. Найбільш поширені серед них наведені в табл. 1.6.

Найпростішим /елементарним/ базисом, що є основою бульової алгебри, е набір трьох основних логічних функцій (або операцій): Властивості логічних функцій - №3 - открытая онлайн библиотека і Властивості логічних функцій - №21 - открытая онлайн библиотека , Властивості логічних функцій - №29 - открытая онлайн библиотека або Властивості логічних функцій - №36 - открытая онлайн библиотека , на яких зупинимося більш детальніше (табл. 1.5, 1.6):

інверсія - логічне заперечення або функція НЕ; ця функція згадувалася раніше як однозначна, а тепер розглядається як двозначна ( Властивості логічних функцій - №29 - открытая онлайн библиотека і Властивості логічних функцій - №36 - открытая онлайн библиотека ), хоча залежить тільки від одної з двох змінних,

диз’юнкція - логічне додавання або функція АБО, яка істинна тоді, коли істинні або Властивості логічних функцій - №9 - открытая онлайн библиотека , або Властивості логічних функцій - №6 - открытая онлайн библиотека , або обидві змінні;

кон’юнкція - логічне множення або функція І, яка істинна тільки тоді, коли і Властивості логічних функцій - №9 - открытая онлайн библиотека і Властивості логічних функцій - №6 - открытая онлайн библиотека істинні.

До більш спрощених базисів, з допомогою яких можна побудувати будь-яку складну цифрову систему обробки інформації, належить, наприклад, набір з двох елементарних логічних функцій Властивості логічних функцій - №21 - открытая онлайн библиотека і Властивості логічних функцій - №36 - открытая онлайн библиотека або Властивості логічних функцій - №3 - открытая онлайн библиотека і Властивості логічних функцій - №36 - открытая онлайн библиотека і навіть набір лише з одної логічної функції Властивості логічних функцій - №24 - открытая онлайн библиотека або Властивості логічних функцій - №43 - открытая онлайн библиотека . Решту логічних функцій, які відсутні у цих базисах, можна одержати на основі правил (законів) алгебри логіки.

Елементи, що реалізують бульові (логічні) операції, називаються логічними елементами (ЛЕ). Якщо логічні операції і прийнято зображати у вигляді формул, то ЛЕ - графічно у вигляді схем. Умовне графічне позначення ЛЕ прийнято зображати прямокутником, у якого лінії зліва - входи аргументів Властивості логічних функцій - №76 - открытая онлайн библиотека , справа –функція Властивості логічних функцій - №77 - открытая онлайн библиотека . Тип логічної операції задається спеціальною позначкою: інверсія – кружком на вході або виході (ЛЕ - інвертор), диз’юнкція - 1, кон’юнкція - & (табл. 1.6).

Таблиця 1.6 Основні логічні функції.

Вхідні змінні Диз’юн-кція АБО: Властивості логічних функцій - №78 - открытая онлайн библиотека Властивості логічних функцій - №79 - открытая онлайн библиотека Кон’нкція І: Властивості логічних функцій - №80 - открытая онлайн библиотека Властивості логічних функцій - №81 - открытая онлайн библиотека Штрих Шефера І-НЕ: Властивості логічних функцій - №82 - открытая онлайн библиотека Властивості логічних функцій - №83 - открытая онлайн библиотека Стрілка Пірса АБО-НЕ Властивості логічних функцій - №84 - открытая онлайн библиотека Властивості логічних функцій - №85 - открытая онлайн библиотека Вийняткове АБО: Властивості логічних функцій - №86 - открытая онлайн библиотека Властивості логічних функцій - №87 - открытая онлайн библиотека Вийняткове АБО-НЕ Властивості логічних функцій - №88 - открытая онлайн библиотека Властивості логічних функцій - №89 - открытая онлайн библиотека
Властивості логічних функцій - №9 - открытая онлайн библиотека Властивості логічних функцій - №6 - открытая онлайн библиотека
Назва і умовне /схемне/ позна- чення Диз’юн- ктор Властивості логічних функцій - №92 - открытая онлайн библиотека Кон’юн-ктор Властивості логічних функцій - №93 - открытая онлайн библиотека Елемент Шефера Властивості логічних функцій - №94 - открытая онлайн библиотека Елемент Пірса Властивості логічних функцій - №95 - открытая онлайн библиотека Суматор   Властивості логічних функцій - №96 - открытая онлайн библиотека Суматор інвертор Властивості логічних функцій - №97 - открытая онлайн библиотека

Логічні функції багатьох змінних одержують аналогічно розглянутому випадку Властивості логічних функцій - №98 - открытая онлайн библиотека застосуванням методу суперпозиції та аксіом і законів алгебри логіки. Слід зауважити, що базисні функції обов'язково містять у собі операцію інверсії. Побудовані на їх основі логічні елементи (наприклад, на елементах Шефера або Пірса) дозволяють будувати функціональні вузли цифрових систем будь-якої складності.

Особливий інтерес для практики має функція Властивості логічних функцій - №17 - открытая онлайн библиотека сума за модулем 2, яку ще називають “виняткове АБО". Логічний елемент-суматор за модулем 2, що реалізує цю функцію, широко застосовують у різних цифрових функціональних пристроях комбінаційного типу.

Особливість функції “виключне АБО” в тому, що вона збігається з функцією АБО в усіх випадках, за винятком, одного, коли всі змінні набувають значення одиниці, а саме при Властивості логічних функцій - №100 - открытая онлайн библиотека . 3 цієї причини, очевидно, ця функція й називається "виняткове АВО” Символ Å псевдоплюс означає, що змінні (аргументи) Властивості логічних функцій - №9 - открытая онлайн библиотека і Властивості логічних функцій - №6 - открытая онлайн библиотека пов’язані логічною функцією “вийняткове АБО” яка істинна тоді, коли одна із змінних ( Властивості логічних функцій - №9 - открытая онлайн библиотека або Властивості логічних функцій - №6 - открытая онлайн библиотека ) є істинною:

Властивості логічних функцій - №9 - открытая онлайн библиотека Å Властивості логічних функцій - №106 - открытая онлайн библиотека

Виняткове АБО (цю функцію ще називають нерівнозначністю або нееквівалентністю) має властивості:

комутативності Властивості логічних функцій - №9 - открытая онлайн библиотека Å Властивості логічних функцій - №6 - открытая онлайн библиотека = Властивості логічних функцій - №6 - открытая онлайн библиотека Å Властивості логічних функцій - №9 - открытая онлайн библиотека ;

асоціативності Властивості логічних функцій - №9 - открытая онлайн библиотека Å Властивості логічних функцій - №112 - открытая онлайн библиотека Å Властивості логічних функцій - №113 - открытая онлайн библиотека )=( Властивості логічних функцій - №9 - открытая онлайн библиотека Å Властивості логічних функцій - №6 - открытая онлайн библиотекаВластивості логічних функцій - №113 - открытая онлайн библиотека ;

дистрибутивності відноснокон’юнкції Властивості логічних функцій - №117 - открытая онлайн библиотека Å Властивості логічних функцій - №118 - открытая онлайн библиотека Å Властивості логічних функцій - №119 - открытая онлайн библиотека .

Справедливі також аксіоми Властивості логічних функцій - №120 - открытая онлайн библиотека Å 0 Властивості логічних функцій - №121 - открытая онлайн библиотека ; Властивості логічних функцій - №120 - открытая онлайн библиотека Å Властивості логічних функцій - №123 - открытая онлайн библиотека ; Властивості логічних функцій - №120 - открытая онлайн библиотека Å Властивості логічних функцій - №125 - открытая онлайн библиотека ; Властивості логічних функцій - №120 - открытая онлайн библиотека Å Властивості логічних функцій - №127 - открытая онлайн библиотека .

На основі властивостей і аксіом функції ''вийняткове АВО” можна одержати функцію елементарного базису:

НЕ - Властивості логічних функцій - №128 - открытая онлайн библиотека Å 1; І - Властивості логічних функцій - №129 - открытая онлайн библиотека Å Властивості логічних функцій - №130 - открытая онлайн библиотека Å Властивості логічних функцій - №131 - открытая онлайн библиотека ;

АБО - Властивості логічних функцій - №132 - открытая онлайн библиотека Å Властивості логічних функцій - №6 - открытая онлайн библиотека Å Властивості логічних функцій - №4 - открытая онлайн библиотека

Для функції “вийняткове АБО-НЕ” (рівнозначність або еквівалентність) справедлива така рівність:

Властивості логічних функцій - №9 - открытая онлайн библиотека ~ Властивості логічних функцій - №136 - открытая онлайн библиотека