Основы объектно-ориентированного программирования на языке C# book | Page 56

4 Булев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муму двох чисел таким чином: x ∧ y = min x, y
при x ∈ {0, 1} та y ∈ {0, 1}.
Розглянемо iнший приклад. Якщо A – висловлювання, то вислов-
лювання “не A” (заперечення A) є iстинним тодi i тiльки тодi, коли
висловлювання A хибне. Нехай x – значення, яке рiвне 0, якщо A
iстинне, або 1, якщо А хибне. Аналогiчно, нехай y – значення, яке
рiвне 0, якщо висловлювання “не A” iстинне, або 1, якщо висловлю-
вання “не A” хибне. Тодi значення y можна однозначно визначити,
знаючи значення x, а саме:
– якщо x = 0, то y = 1;
– якщо x = 1, то y = 0.
Наведенi правила визначають функцiю вiд одного аргументу, який
може приймати значення 0 або 1, яка сама може приймати значення 0
або 1. Цю функцiю називають булевою операцiєю заперечення i часто
позначають горизонтальною рискою згори над ı̈ı̈ аргументом: z =
x. Дана операцiя має властивостi 0, 1. Значення x можна виразити,
застосувавши до x арифметичну операцiю вiднiмання вiд одиницi:
x = 1 − x (при x ∈ {0, 1}). Вiдмiннiсть арифметичноı̈ операцiı̈ вiд
булевоı̈ аналогiчна поясненiй вище вiдмiнностi ∧ на арифметичного
множення.
Математичне визначення булевоı̈ функцiı̈ наведено нижче.
Означення 4.1 ([1]). Булевою функцiєю n змiнних (де n ≥ 1 – нату-
ральне число) називається функцiя, яка вiдображає множину {0, 1} n
(декартовий степiнь множини {0, 1}, що складається з усiх можли-
вих n-ок елементiв множини {0, 1}) в множину {0, 1}.
Прикладом булевоı̈ функцiı̈ 2 змiнних є булева операцiя ∧.
Булеву функцiя n змiнних, яка приймає значення 1 для всiх можли-
вих наборiв значень ı̈ı̈ аргументiв будемо позначати як 1 n , а булеву
функцiя n змiнних, яка приймає значення 0 для всiх можливих наборiв
значень ı̈ı̈ аргументiв будемо позначати як 0 n . Наприклад, 0 1 (0) = 0,
0 1 (1) = 0, 1 2 (0, 0) = 1, 1 2 (0, 1) = 1, 1 2 (1, 0) = 1, 1 2 (1, 1) = 1.
В силу скiнченностi множини {0, 1} n , будь-яку булеву функцiю n
змiнних можна задати табличним способом, вказавши ı̈ı̈ значення на
кожному можливому наборi значень аргументiв (табл. 5.1).
56