Page 81 - 4570

80

Доведемо спочатку рівносильність 2.7 Нехай x , x , ..., x множина всіх
1 i 2 i n i
вільних змінних формули Р, відмінних від пов’язаних змінних х. Покажемо, що
на будь-якому наборі значень вільних змінних (a , a , ..., а ), а  М, формули
1 2 n і
  х Р(х) і х Р(х) набувають однакових значень істинності. При цьому
можливі два випадки.

1. Для будь-якого елемента а  М Р(х)= T на наборі (а, a , a , ..., а ).
1 2 n
2. Для деякого елемента а  М Р(х) = F на наборі (а , a , a , ..., а ).
0 0 1 2 n
У першому випадку для будь-якого елемента а  М маємо Р(х) = F на
наборі (a , a , ..., а ). Звідси за означенням х Р(х) = F на наборі (a , a , ...,
1 2 n 1 2
а ), з іншого боку,  х Р(х) = T, а   х Р(х) = F на наборі (a , a , ..., а ).
n 1 2 n
У другому випадку для елемента а  М маємо Р(х) = T на наборі (а ,
0 0
a , a , ..., а ). Звідси х Р(х) = T на наборі (a , a , ..., а ). З іншого боку,  х
1 2 n 1 2 n
Р(х) = F, а   х Р(х) = T на наборі (a , a , ..., а ), що й потрібно було довести
1 2 n
для рівносильності формули 2.7. Доведення рівносильності формули 2.8
аналогічне описаному для формули 2.7.

3. Елементарні функції алгебри логіки

Булеві функції однієї та двох незалежних змінних прийнято називати
елементарними булевими функціями. Вони використовуються як логічні
операції над булевими змінними при побудові булевих функцій багатьох
незалежних змінних. Алгебра з такими логічними операціями називається
алгеброю логіки, а булеві функції називаються ще функціями алгебри логіки.
Загальне число різних елементарних функцій (логічних операцій) дорівнює
загальному числу функцій двох змінних, тобто 2 2 2  16 (функції однієї змінної є
окремим випадком функцій двох змінних).
Основними в алгебрі логіки є три логічні операції:
1. Заперечення (інверсія) − функція y = f(х), яка набуває значення T, коли х
= F, і значення F − коли x = T. Позначення: y = x .
2. Диз’юнкція (логічне додавання) – функція y = f(х 1, x 2) яка набуває
значення F тоді і лише тоді, коли обидва аргументи дорівнюють F. Позначення:
y = х 1 + x 2 або y = х 1  x 2.
3. Кон’юнкція (логічне множення) – функція y = f(х 1, x 2), яка набуває
значення T тоді і лише тоді, коли обидва аргументи дорівнюють T.
Позначається: y = х 1  x 2 або y = х 1  x 2,.
Якщо операція містить один операнд, вона називається одномісною, або
унарною, а якщо два, то – двомісною, або бінарною. Заперечення – це
одномісна операція, а диз’юнкція та кон’юнкція − двомісні. При цьому вирази
x , х 1 + x 2, х 1  x 2 є прикладами логічних формул. Більш складні формули
дістаємо за рахунок суперпозиції логічних формул, які беруться у круглі дужки,
наприклад: у = х 1 + x 2( x + х 2)(х 1 + х 1 x ).
1 2
Елементарні функції однієї змінної. Таблиця істинності цих функцій має
вигляд: