Логічні функції

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

Означення 2.2.Функція f(x₁, x₂, ..., x_n) называється логічною (перемикальною, булевою), якщо вона, так само як її аргументи (логічні змінні) x_i, i= , може приймати тільки два значення: 0 та 1.

Означення 2.3.Упорядкована множина значень аргументів логічної функції називається набором і позначається кортежем (а₁, а₂, ..., а_і, ..., а_n), а_іÎ{0, 1}, i= .

Областю визначення логічної функції (ЛФ) n змінних є сукупність всіх можливих упорядкованих наборів. Набір уявляє собою число у двійковій системі числення, якому відповідає певне число в десятковій системі числення (Додаток А). Ці числа можна розглядати як номер набору у відповідній системі числення. У такий спосіб встановлюється порядкова нумерація наборів для будь-якої ЛФ, як це показано в таблиці 2.2. Таким чином, будь-яким набором (а₁,а₂,...,а_і,...,а_n) задається його власний порядковий номер у двійковій та десятковій системах числення і в той же час в його i-му розряді (i = 1, 2, …, n) знаходиться значення 0 або 1 змінної x_i даного набору.

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

Означення 2.4. логічною функцією (функцією алгебри логіки) називається функція f(x₁, x₂, ..., x_n), яка приймає значення 0 або 1 на наборах логічних змінних x₁, x₂, ..., x_n.

Оскільки кожний з n аргументів логічної функції може приймати два можливих значення, то очевидно, що областю визначення логічної функції n змінних є сукупність m=2ⁿ можливих наборів.

Оскільки логічна функція n аргументів може приймати тільки два з можливих значень (0 і 1) на кожному з m наборів, то кількість всіх різних логічних функцій n аргументів дорівнює k=2^m. Значення величин m і k обчислюються за формулами комбінаторики (Додаток Б).

Означення 2.5. Якщо логічна функція n змінних визначена на всіх 2ⁿ наборах, її називають повністю визначеною, в протилежному випадку – неповністю визначеною.

Для наборів, на яких ЛФ не визначена, її значення можна прийняти будь-яким із множини {0, 1} і таким чином привести її до повністю визначеної.

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

Для задання логічної функції можна застосувати табличний спосіб, коли функція представляється своєю таблицєю істинності. Прикладом може служити таблиця 2.2 істинності функції F= . При більшій ніж 2 кількості аргументів табличний спосіб незручний через великий розмір таблиці. Логічна функція може бути задана також у вигляді формули, наприклад: f(x₁,x₂,x₃)=x₁Ú Úx₃.

Логічні функції одного і двох аргументів називають елементарними. Їх можна задати як формулами, так і таблицями істинності.

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

f(x)=0, має назву “Константа нуль”;

f(x)=x, має назву “Змінна x” (повторення x);

f(x)= , має назву “Інверсія (заперечення) x”;

f(x)=1, має назву “Константа одиниця”.

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

Таблиця 2.3 – Таблиця істинності логічних функцій f(x)

Номер набору	x	f(x)=0	f(x)=x	f(x)=	f(x)=1

Для логічної функції двох аргументів існують чотири набори, кількість таких функцій – шістнадцять. Відповідність цих функцій переліку операцій алгебри логіки, наведеному в п.2.2, зручніше буде пояснити на підставі таблиці 2.4.

Таблиця 2.4 – Таблиця істинності логічних функцій f(x₁,x₂)

У 16 клітинках першого рядка таблиці 2.4 розміщені номери i=0, …, 15 функцій f_і(x₁,x₂), а в тих же за номерами клітинках інших рядків – виділені жирним шрифтом значення функцій f_і(x₁,x₂) для відповідних наборів. Неважко бачити, що немає жодної пари функцій з однаковими значеннями на всіх наборах, тобто всі функції різні. Наведемо назви цих функцій у відповідності до логічних операцій, які вони реалізують:

f₀(x₁,x₂)=0, має назву “Константа нуль”;

f₁(x₁,x₂)=x₁Ùx₂, має назву “Кон’юнкція” (функція “І”);

f₂(x₁,x₂)= , має назву “Заборона x₂”;

f₃(x₁,x₂)=x₁, має назву “Змінна x₁”;

f₄(x₁,x₂)= , має назву “Заборона x₁”;

f₅(x₁,x₂)=x₂, має назву “Змінна x₂”;

f₆(x₁,x₂)=x₁Åx₂, має назву “Сума за модулем 2” (логічна нерівнозначність, виключне “або” );

f₇(x₁,x₂)=x₁Úx₂, має назву “Диз’юнкція” (функція “Або”);

f₈(x₁,x₂)=x₁¯x₂, має назву “Функція (стрілка) Пірса” (функція “Або-Не”);

f₉(x₁,x₂)=x₁~x₂, має назву “Рівнозначність”;

f₁₀(x₁,x₂)= , має назву “Інверсія x₂” (функція “Не”);

f₁₁(x₁,x₂)=x₂®x₁, має назву “Імплікація від x₂ до x₁” (функція “Якщо-То”);

f₁₂(x₁,x₂)= , має назву “Інверсія x₁” (функція “Не”);

f₁₃(x₁,x₂)=x₁®x₂, має назву “Імплікація від x₁ до x₂” (функція “Якщо-То”);

f₁₄(x₁,x₂)=x₁|x₂, має назву “Функція (штрих) Шеффера” (функція “І-Не”).

f₁₅(x₁,x₂)=1, має назву “Константа одиниця”.

З числа ЛФ двох змінних f₀ – f₁₅ (табл. 2.4) можна виділити базисні, за допомогою яких можна одержати будь-які інші ЛФ. У той же час базисні ЛФ неможливо одержати за допомогою інших. До базисних належать такі елементарні ЛФ: f₀, f₁, f₃, f₅, f₇, f₁₀, f₁₂, f₁₅.

За допомогою елементарних ЛФ можна будувати складні ЛФ від довільної скінченної кількості аргументів. Будь-яка складна ЛФ може бути поданою у вигляді формули, яка вказує послідовність елементарних логічних операцій над логічними змінними. Пріоритет виконання операцій у формулах такий: спочатку виконуються операції всередині дужок, після чого – операції заперечення, потім кон’юнкції, а далі – диз’юнкції та всі інші операції в порядку запису зліва направо.

Логічні вирази, тобто формули, які містять операції диз’юнкції та кон’юнкції, можна перетворювати (розкривати дужки, виносити загальний множник, переставляти місцями члени і т.п.) за правилами алгебри чисел,вважаючи формально диз’юнкцію операцією додавання, а кон’юнкцію - операцією множення. Але потрібно чітко пам’ятати, що в алгебрі логіки, на відміну від алгебри чисел, знаки додавання і множення означають логічні зв’язки “Або” та“І”.

Формулу будь-якої ЛФ можна, використовуючи операції алгебри логіки та опис елементарних функцій, перетворити до такого виду, щоб усі логічні зв’язки проміж логічними змінними визначалися операціями диз’юнкції, кон’юнкції та інверсії. Покажемо це для ЛФ двох змінних f₂, f₄, f₆, f₈, f₉, f₁₁, f₁₃, f₁₄ (табл. 2.4), які не є базисними:

f₂(x₁,x₂)= = =x₁Ù ;

f₄(x₁,x₂)= = =x₂Ù ;

f₆(x₁,x₂)=x₁Åx₂= = =(x₁Ù )Ú( Ùx₂);

f₈(x₁,x₂)=x₁¯x₂= = Ù ;

f₉(x₁,x₂)=x₁~x₂=x₁Ùx₂Ú Ù ;

f₁₁(x₁,x₂)=x₂®x₁= Úx₁;

f₁₃(x₁,x₂)=x₁®x₂= Úx₂;

f₁₄(x₁,x₂)=x₁|x₂= = Ú .

Розглянемо особливі випадки, коли мають місце такі співвідношення між аргументи ЛФ: один з двох аргументів є константою 1 або 0; обидва аргументи дорівнюють один одному (x₁=x₂=x); один з аргументів є інверсією іншого (x₁=x, x₂= ). У таких випадках мають місце наступні тотожності:

xÚ1=1, xÙ1=x, x~1=x, xÅ1= ,

x®1=1, 1®x=x, x|1= , x¯1=0;

xÚ0=x, xÙ0=0, x~0= , xÅ0=x,

x®0= , 0®x=1, x|0=1, x¯0= ;

xÚx=x, xÙx=x, x~x=1, xÅx=0, x®x=1, x|x= , x¯x= ;

xÚ =1, xÙ =0, x~ =0, xÅ =1,

x® = , ®x=x, x| =1, x¯ =0.

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

Розглянути так само логічні функції трьох аргументів неможливо, оскільки їх кількість становить 2⁸= 256. Проте це не має принципового значення, бо аргументи будь-якої ЛФ також можуть бути логічними функціями. Це означає, що створювати складні ЛФ можна шляхом підстановки інших ЛФ в якості аргументів.

Означення 2.6. Функція F(f₁,…, f_n), що одержується із функції F(x₁,…, x_n) шляхом підстановки функцій f₁(x₁,…, x_n),…, f_n(x₁,…, x_n) замість аргументів x₁,…, x_n, називається суперпозицією функцій f₁,…, f_n.

Таким чином, знаючи властивості логічних функцій та принцип су­перпозиції, можна з простих логічних висловлень утворювати складніші, або, що те ж саме, з простих логічних функцій одержувати складні. Слід помітити, що при виконанні операції підстановки функцій f₁,…, f_n замість аргументів у формулу функції F(x₁,…, x_n) не виключається можливість заміни не всіх аргументів. Крім того, серед аргументів функцій f₁,…, f_n можуть бути відсутніми деякі зі змінних x₁,…, x_n. тоді, після перейменування аргументів, буде одержана функція G(y₁,…, y_m) з числом аргументів m<n. Саме такі випадки віддзеркалює наступний приклад.

Результати наведених вище перетворень формул ЛФ та використання суперпозиції є такими, що всі логічні зв’язки проміж логічними змінними визначаються операціями диз’юнкції, кон’юнкції та інверсії. Це означає, що відповідні цим операціям елементарні функції f_І(x₁,x₂)=x₁Ùx₂ (функція “І”), f_Або(x₁,x₂)=x₁Úx₂ (функція “Або”), f_Не(x)= (функція “Не”) створюють систему логічних функцій, яка володіє властивістю функціональної повноти. Наведемо формальне означення цього поняття.

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

Система всіх розглянутих вище елементарних ЛФ є функціонально повною, однак надлишковою. Меншою за складом є згадана вище система базисних фнкцій f₀, f₁, f₃, f₅, f₇, f₁₀, f₁₂, f₁₅ (табл. 2.4), але й ця система є надлишковою. Найменшою надлишковістю володіє згадана вище функціонально повна система “І–Або–Не”: (2.1)

Система (2.1) надлишкова, оскільки з неї можна вилучити або диз’юнкцію, або кон’юнкцію без втрати повноти. Вилучену функцію мож­на дістати з інших двох, що залишилися, відповідно до законів алгебри ло­гіки. Наприклад, виключивши із (2.1) кон’юнкцію f_І(x₁,x₂), останню одержують, застосував­ши заперечення у функції до окремих доданків і до всього виразу в правій частині:

Отже, через вилучення із системи (2.1) кон’юнкції f_І(x₁,x₂) набір функцій та f_Не(x) не втрачає функціональної повноти. Однак, якщо із набору та f_Не(x) вилучити хоча б одну з цих функцій, то отриманий набір у складі однієї функції вже не буде функціонально повним.

Означення 2.8. Якщо з функціонально повного набору елементарних ЛФ не можна вилучити жод­ної функції без втрати його повноти, то такий набір називають базисом.

Базисами логічних функцій є: {Ù,` } – кон’юнктивний базис; {Ú,` } – диз’юнктивний базис; {®} – імплікативний базис, де x₁®x₂= Úx₂; {¯} – базис Вебба (Пірса), де х₁¯х₂= f₈(х₁,х₂)= =х₁Úх₂; {|} – базис Шеффера, де х₁|х₂=f₁₄(х₁,х₂)=`х<sub>1</sub>Ú`х₂= .

Для кожної складної ЛФ можна отримати еквівалентну до неї функцію в будь-якому з перерахованих базисів. Наприклад, `х₁Úх₂Ùх₃=х₁®( ).

Помітимо, що функціонально повна система (2.1) “І–Або–Не” формально не є базисом. Проте, вона широко застосовується при аналітичному поданні й перетвореннях логічних функцій та при технічній реалізації останніх у пристроях дискретної дії (дискретних пристроях). Тому набір функцій (2.1) умовно відносять до числа базисів.

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

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

Кожна з функцій f₀ – f₁₅ має інверсну (табл. 2.4). Наприклад, f₀=Øf₁₅, f₁=Øf₈, f₂=Øf₁₅.

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

Означення 2.11. Логічна змінна x_i є дійсною, якщо значення логічної функції f(x₁, x₂, ..., x_n) змінюється при зміні значення x_i. В протилежному випадку ця змінна для даної функції є фіктивною, тобто не є її аргументом.

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