4.2 Булевi вирази
A – висловлювання, iстиннiсть якого визначається x 1, а B – висловлювання, iстиннiсть якого визначається x 2, то висловлювання“ A або B” iстинне тодi i тiльки тодi, коли iстинне заперечення висловлювання“ не A та не B”. Слiд зауважити, що як i кон’ юнкцiю, диз’ юнкцiю не складно виразити через числовi операцiï: x ∨ y = max x, y = x + y − xy при x ∈ { 0, 1 } та y ∈ { 0, 1 }. Хоча диз’ юнкцiя i виражається через заперечення i кон’ юнкцiю, ïï, як правило, включать до числа базових булевих операцiй, через якi виражають iншi булевi функцiï. Це є пiдставою визначення поняття булевого виразу, наведеного нижче.
Означення 4.2([ 1 ]). Нехай дано скiнчений перелiк рiзних символiв – iмен змiнних x 1,..., x n. Поняття булевого виразу вiд змiнних x 1,..., x n визначається iндуктивним чином:
( 1) константи 0, 1 та змiннi x 1,..., x n є булевими виразами вiд змiнних x 1,..., x n;
( 2) якщо E та E ′ – булевi вирази вiд змiнних x 1,..., x n, то вирази( E ∨ E ′,( E ∧ E ′, та E є булевими виразами вiд змiнних x 1,..., x n;
( 3) кожний булевий вираз можна отримати за допомогою скiнченого числа застосувань правил( 1) та( 2).
Наприклад, x 1 ∨ x 2,( x 1 ∨ 0) ∨ 1,( x 1 ∨ x 2) ∨( x 3 ∧ x 4) є булевими виразами( вiд змiнних x 1, x 2, x 3, x 4).
Для позначення довiльного булевого виразу вiд x 1, x 2,..., x n використовують позначення φ( x 1, x 2,..., x n).
Означення 4.3([ 1 ]). Для заданого булевого виразу φ( x 1, x 2,..., x n), булева функцiя, зображена φ – це булева функцiя f φ: { 0, 1 } n → { 0, 1 }, така, що для кожного кортежу( b 1, b 2,..., b n) ∈ { 0, 1 } n, f φ( b 1, b 2,..., b n) є значенням, отриманим шляхом пiдстановки b 1 замiсть x 1, b 2 замiсть x 2,..., b n замiсть x n у виразi φ( x 1, x 2,..., x n) та спрощеннi отриманого виразу до значення 0 або 1 за допомогою таких правил: 0 ∨ 0 = 0, 0 ∨ 1 = 1, 1 ∨ 0 = 1, 1 ∨ 1 = 1, 0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 0 = 0, 1 ∧ 1 = 1, 0, 1.
Легко бачити, що кожний булевий вираз зображає єдину булеву функцiю. Проте поняття булевого виразу вiдрiзняється вiд поняття булевоï функцiï: булевий вираз є лише символiчним записом, тому 0 та x 1 ∧ x – рiзнi булевi вирази вiд змiнноï x 1. В той же час вони зображають одну i ту ж булеву функцiю 0 1( для функцiï суттєвими є лише вiдповiднiсть мiж значеннями аргументiв та результатом). Означення 4 [ 1 ]. Два булевих вирази називаються еквiвалентними, якщо вони зображають одну i ту ж булеву функцiю.
59