Розділ 1 ФУНКЦІЇ АЛГЕБРИ ЛОГІКИ ТА ЇХ ОСНОВНІ ВЛАСТИВОСТІ

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

     1.1     Основні поняття теорії елементарних функцій алгебри логіки

Функцію , яка набуває тільки значення 0 або 1, як і її аргументи, прийнято називати логічною функцією або булевою функцією. Аргументи булевої функції також називають булевими.

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

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

В табл. 1.1 задані дві логічні функції трьох аргументів і .

Таблиця 1.1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

1

1

0

0

1

0

1

1

0

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

а) будь-яка логічна функція n аргументів визначена на наборах.

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

б) число різних логічних функцій n аргументів скінченне і дорівнює .

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

в) кількість логічних функцій n аргументів різко зростає зі збільшенням n (табл. 1.2).

Таблиця 1.2

Кількість аргументів

1

2

3

4

5

Число переми-каючих функцій

4

16

256

65536

4,3Ч109

Логічна функція одного аргументу подана в табл. 1.3.

Таблиця 1.3

0

1

Умовне позначення

     Найменування функції

0

0

0

Константа нуля

0

1

Змінна

1

0

Інверсія

1

1

1

Константа одиниці

Логічні функції двох аргументів подані в табл. 1.4. Наведені булеві функції дозволяють будувати нові булеві функції за допомогою узагальненої операції, яка називається операцією суперпозиції. Операція суперпозиції полягає в підстановці замість аргументів інших булевих функцій (зокрема аргументів) [9].

Таблиця 1.4

Функція

0

0

0

1

1

0

1

1

Назва функції

Позна-чення

Функція, що виконується

0

0

0

0

константа нуль

0

 

0

0

0

1

Добуток (кон’юнкція)

0

0

1

0

f заборона по y

0

0

1

1

змінна х

X

0

1

0

0

f заборона по х

0

1

0

1

змінна y

Y

0

1

1

0

сума за модулем 2

0

1

1

1

диз’юнкція

1

0

0

0

операція Пірса

(функція Вебба)

1

0

0

1

логічна рівнозначність

~

1

0

1

0

інверсія y

1

0

1

1

імплікація від у до х

1

1

0

0

інверсія х

1

1

0

1

імплікація від х до у

1

1

1

0

операція Шеффера (штрих Шеффера)

1

1

1

1

константа одиниці

1

 

Існує 16 різних логічних функцій двох аргументів ( і ), кожна з яких визначена на 4-х наборах.

З 16-ти функцій, які подані в табл. 1.4, 6 функцій

;

;

;

;

;

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

Функція називається кон’юнкцією, логічним множенням або логічним І. Для її позначення використовуються: знак множення Ч - ; знак кон’юнкції Щ - ; знак логічного І - & - .

Функція носить назву диз’юнкції, логічного додавання, логічного АБО. Для позначення використовується знак Ъ: , іноді для зручності .

Функція називається функцією нерівнозначності або сумою за модулем 2:

          .

Функція називається функцією рівнозначності або еквівалентності:

          .

Функція називається штрихом Шеффера або запереченням кон’юнкції:

         

або

          .

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

Функція називається запереченням диз’юнкції, функцією Пірса або стрілкою Пірса:

         

або

          .

Функції і називаються імплікацією:

          і

або

          і .

Функція і називається функцією заборони або заперечення імплікації:

          і .

  Зміст