Функции алгебры логики. Стасюк В.В. - 4 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

Булевы функции
Обозначим через
множество, состоящее из нулика и единички, а через
2
E
2
n
E
— -ю
декартову степень этого множества:
n
{
}
2
0, 1E =
,
222
раз
n
n
2
E
EE E
=
××⋅⋅⋅×
1
442443
.
В частности, при и имеем: 2n = 3n =
(
)
(
)
(
)
(
)
{
}
2
2
0, 0 , 0, 1 , 1, 0 , 1, 1E =
,
Определение. Функцией алгебры логики или булевой функцией
переменных, по
имени Дж. Буля, называется отображение
n
22
:
n
f
EE→ .
Множество всех булевых функций от переменных обозначается через :
n
n
P
{
}
22
:
n
n
PffEE=→
.
Булеву функций от переменных можно задать таблицей (истинности):
n
11
, ..., ,
nn
xx
−
1
( ,..., )
n
f
xx
0 ... 0 0
0 ... 0 1
0 ... 1 0
... ... ... ...
1 ... 1 1
1
1
0
…
1
Если число переменных равно
, то таблица содержит строк (проверьте!).
n
2
n
Пример 1. Пусть
(, ,)
f
xyz зависит от трех переменных. Тогда ее таблица должна со-
держать
строк, например,
3
2= 8
х у z
(, ,)
f
xyz
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
1
0
0
Замечание. В силу того, что левая часть таблицы для каждой булевой функции стро-
ится стандартным образом, для задания такой функции достаточно перечислить последова-
тельность ее значений, обычно записываемую в строку. Так, функцию из предыдущего при-
мера можно задать (также таблично) в виде
( , , ) (0001 1100)fxyz
=
.
Две функции от
переменных различны, если различны двоичные наборы их значе-
ний. Таким образом, число булевых функций от
переменных равно
n
n
2
2
n
n
P =
(проверьте!). 
                                      Булевы функции

      Обозначим через E2 множество, состоящее из нулика и единички, а через E2n — n -ю
декартову степень этого множества:

                             E2 = {0, 1} , E2n = E2 × E2 ×⋅⋅⋅× E2 .
                                                 1442443
                                                                 n раз

В частности, при n = 2 и n = 3 имеем:

                                E22 = {( 0, 0 ) , ( 0, 1) , (1, 0 ) , (1, 1)} ,

      Определение. Функцией алгебры логики или булевой функцией n переменных, по
имени Дж. Буля, называется отображение f : E2n → E2 .
      Множество всех булевых функций от n переменных обозначается через Pn :


                                                 {
                                             Pn = f f : E2n → E2 .       }
      Булеву функций от n переменных можно задать таблицей (истинности):

                               x1 , ..., xn −1 , xn         f ( x1 ,..., xn )
                                0     ...      0 0                 1
                                0      ...     0 1                 1
                                0      ...     1 0                 0
                                ...   ...     ... ...              …
                                1     ...     1    1               1

Если число переменных равно n , то таблица содержит 2n строк (проверьте!).
      Пример 1. Пусть f ( x, y, z ) зависит от трех переменных. Тогда ее таблица должна со-
держать 23 = 8 строк, например,

                                      х      у    z     f ( x, y , z )
                                      0      0   0           0
                                      0      0   1           0
                                      0      1   0           0
                                      0      1   1           1

                                      1      0   0           1
                                      1      0   1           1
                                      1      1   0           0
                                      1      1   1           0

       Замечание. В силу того, что левая часть таблицы для каждой булевой функции стро-
ится стандартным образом, для задания такой функции достаточно перечислить последова-
тельность ее значений, обычно записываемую в строку. Так, функцию из предыдущего при-
мера можно задать (также таблично) в виде f ( x, y, z ) = (0001 1100) .
       Две функции от n переменных различны, если различны двоичные наборы их значе-
                                                                                  n
ний. Таким образом, число булевых функций от n переменных равно Pn = 22 (проверьте!).

Страницы