Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 21 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
67
Переменная
x
, принимающая два значения, 0 или 1, называется бу-
левой переменной.
Пусть
{
}
10 ,E =
. Тогда
4434421
разn
n
E...EEE ×××= — множество упорядоченных
двоичных наборов длины
n
:
(
)
{
}
.n,...,,,i,E,...,,E
in
n
321
21
=∈= αααα
Говорят , что задана булева функция
n
переменных
(
)
,x,...,x,xf
n21
если задан закон , по которому каждому двоичному набору
(
)
n
n
E,...,, ∈ ααα
21
ставится в соответствие 0 или 1: EE:f
n
→ .
Таким образом, область определения булевой функции
(
)
n
x,...,x,xf
21
есть
(
)
n
EFD =
, множество значений —
(
)
EfR =
, где мощ -
ность
(
)
(
)
.fR,fD
n
22 ==
Булева функция может быть задана при помощи:
1. описания;
2. таблицы истинности;
3. формулы алгебры высказываний;
4. множества истинности
(
)
(
)
{
}
1
2121
==
nnf
,...,,f,...,,fE αααααα ;
5. набора значений;
6. функциональной схемы.
Рассмотрим пример, на котором проиллюстрируем указанные спосо-
бы задания булевых функций.
Пример. Пусть булева функция
(
)
321
x,x,xf принимает значений 1
на наборах
(
)
321
ααα ,, , в которых большинство нулей, а на остальных на-
борах ее значение равно 0.
Описанная функция может быть задана с помощью таблицы истин -
ности (рис. 1):
В случае
n
переменных булева функция )x,...,x,x(f
n21
задается
таблицей, содержащей
n
2 строк, т.к.
n
n
n
EE 2 == . В дальнейшем всегда
будем располагать наборы в таблице истинности так, как показано на
рис.2. 
                                                 67
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Переменная x , принимающая два значения, 0 или 1, называется бу-
левой переменной.
     Пусть E ={0, 1}. Тогда E n =
                                 E×E
                                   ×
                                      ... ×
                                          E — множество упорядоченных
                                           
                                                  n   раз
двоичных наборов длины n :
                      E n ={(α 1 , α 2 ,...,α n ) α i ∈ E , i =1, 2 , 3, ... , n}.
          Говорят, что задана булева функция n переменных f ( x1 , x 2 , ... , x n ) ,
если задан закон, по которому каждому двоичному набору
(α 1 , α 2 ,...,α n )∈ E n ставится в соответствие 0 или 1: f : E n → E .
          Таким            образом, область       определения    булевой      функции
 f (x1 , x 2 , ... , x n ) есть D(F ) = E , множество значений — R( f ) = E , где мощ-
                                         n

ность D( f ) =2 n , R( f ) =2.
      Булева функция может быть задана при помощи:
      1. описания;
      2. таблицы истинности;
      3. формулы алгебры высказываний;
      4. множества истинности E f ={ f (α1 , α 2 , ... , α n ) f (α1 ,α 2 , ... ,α n ) =1};
      5. набора значений;
      6. функциональной схемы.
      Рассмотрим пример, на котором проиллюстрируем указанные спосо-
бы задания булевых функций.

      Пример. Пусть булева функция f ( x1 , x 2 , x 3 ) принимает значений 1
на наборах (α 1 , α 2 ,α 3 ) , в которых большинство нулей, а на остальных на-
борах ее значение равно 0.
      Описанная функция может быть задана с помощью таблицы истин-
ности (рис. 1):
      В случае n переменных булева функция f ( x1 , x 2 ,..., x n ) задается
                                                                  n
таблицей, содержащей 2 n строк, т.к. E n = E                          =2 n . В дальнейшем всегда
будем располагать наборы в таблице истинности так, как показано на
рис.2.

Страницы