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