Основы объектно-ориентированного программирования на языке C# book | Page 58
4 Булевi функцiı̈ та вирази
4.2 Булевi вирази
Iснують iншi способи задання булевих функцiй, досить поширеним з
яких є булевi вирази. Припустимо, що є перелiк деяких вiдомих (базо-
вих) булевих функцiı̈, для яких зафiксованi позначення. Тодi через них
шляхом пiдстановки можна виразити новi булевi функцiı̈. Наприклад,
за допомогою операцiı̈ ∧ можна виразити таку булеву функцiю 3 ар-
гументiв: f (x 1 , x 2 , x 3 ) = (x 1 ∧ x 2 ) ∧ x 3 (∧ застосовується до результату
∧ вiд перших двох аргументiв та до третього аргументу). З того, що
x ∧ y = x ∙ y при x ∈ 0, 1 та y ∈ 0, 1 випливає, що для операцiı̈ ∧ вико-
нується закон асоцiативностi (так само як для арифметичноı̈ операцiı̈
множенндя): (x 1 ∧ x 2 ) ∧ x 3 = x 1 ∧ (x 2 ∧ x 3 ). Тому дужки у правiй части-
нi визначення функцiı̈ f можна опустити: f (x 1 , x 2 , x 3 ) = x 1 ∧ x 2 ∧ x 3 .
Значення f (x 1 , x 2 , x 3 ) можна трактувати як “x 1 та x 2 та x 3 ”.
Отже через деякi базовi булевi функцiı̈ можна виражати iншi булевi
функцiı̈. Але виникає питання, якi функцiı̈ слiд узяти за базовi, щоб
через них можна було виразити будь-яку булеву функцiю. Виявляє-
ться, що булевоı̈ операцiı̈ заперечення, кон’юнкцiı̈, та констант 0, 1
достатньо, щоб виразити будь-яку булеву функцiю. В загальному ви-
падку, систему (базових) булевих функцiй, через якi можна виразити
будь-яку булеву функцiю називають функцiонально повною. Таким
чином, заперечення i кон’юнкцiя складають функцiонально повну си-
стему, але слiд зауважити, що це єдина функцiонально повна система
(iснує нескiнченно багато iнших систем булевих функцiй, якi мають
цю властивiсть).
Наприклад, булева операцiя АБО (диз’юнкцiю) має два аргументи,
позначається символом ∨ i задається таблицею iстинностi, наведеною
нижче (таб. 4.4).
x 1 x 2 x 1 ∨ x 2
0 0 0
0 1 1
1 0 1
1 1 1
Табл. 4.4: Таблиця iстинностi диз’юнкцiı̈.
Диз’юнкцiю можна виразити через заперечення i кон’юнкцiю таким
чином: x 1 ∨x 2 = x 1 ∧ x 2 . Справедливiсть цього виразу можна перевiри-
ти за допомогою таблиць iстинностi диз’юнкцiı̈, кон’юнкцiı̈ та запере-
чення. Цей вираз пов’язаний з такою логiчною iнтерпретацiєю: якщо
58