Введение в схемы, автоматы и алгоритмы


Булевы функции от 1-ой и 2-х переменных


Перечислим вначале все булевы функции от 1-ой переменной

x_1
. Как мы знаем, их всего четыре.

  1. f_1(x_1)= 0
    - константа 0;
  2. f_2(x_1)= 1
    - константа 1;
  3. f_3(x_1)= x_1
    - тождественная функция;
  4. f_4(0)=1, f_4(1)=0.
    Эта функция называется отрицанием
    x_1

    и обозначается

    \neg x_1
    (используется также обозначение
    \overline{x}_1
    , а в языках программирования эта функция часто обозначается как
    NOT x_1
    ).

В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

Таблица 1.2. Булевы функции от 2-х переменных

x_1
  
x_2
f_1
f_2
f_3
f_4
f_5
f_6
f_7
f_8
f_9
f_{10}
f_{11}
f_{12}

0  0

0  1

1  0

1  1

0

0

0

0

1

1

1

1

0

0

1

1

1

1

0

0

0

1

0

1

1

0

1

0

0

0

0

1

0

1

1

1

1

1

0

1

0

1

1

0

1

0

0

1

1

1

1

0

Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

  • f_1(x_1,x_2)= 0
    - константа 0;
  • f_2(x_1, x_2)= 1
    - константа 1;
  • f_3(x_1,x_2)= x_1
    - функция, равная 1-му аргументу;
  • f_4(x_1,x_2)= \neg x_1
    - отрицание
    x_1
    ;
  • f_5(x_1,x_2)= x_2
    - функция, равная 2-му аргументу;
  • f_6(x_1,x_2)= \neg x_2
    - отрицание
    x_2
    ;
  • f_7(x_1,x_2)= (x_1 \wedge x_2)
    - конъюнкция, читается "
    x_1
    и
    x_2
    " (используются также обозначения
    (x_1 & x_2)
    ,
    (x_1x_2)
    ,
    \min(x_1,x_2)
    и
    (x_1
    AND
    x_2
    ));
  • f_8(x_1,x_2)= (x_1 \vee x_2)
    - дизъюнкция, читается "
    x_1
    или
    x_2
    " (используются также обозначения
    (x_1 + x_2)
    ,
    \max(x_1x_2)
    и
    (x_1
    OR
    x_2
    ));
  • f_9(x_1,x_2)= (x_1 \rightarrow x_2)
    - импликация, читается "
    x_1
    влечет
    x_2
    " или "из
    x_1
    следует
    x_2
    " (используются также обозначения
    (x_1 \supset x_2)
    , и ( IF
    x_1
    THEN
    x_2
    ));
  • f_{10}(x_1,x_2)= (x_1 + x_2)
    - сложение по модулю 2, читается "
    x_1
    плюс
    x_2
    " (используется также обозначение
    (x_1 \oplus x_2)
    );
  • f_{11}(x_1,x_2)= (x_1 \sim x_2)
    - эквивалентность, читается "
    x_1
    эквивалентно (равносильно)
    x_2
    " (используется также обозначение
    (x_1 \equiv x_2)
    );
  • f_{12}(x_1,x_2)= (x_1 | x_2)
    - штрих Шеффера (антиконъюнкция), иногда читается как "не
    x_1
    и
    x_2
    ".

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

Отметим, что функции

f_1(x_1,x_2)
и
f_2(x_1,x_2)
фактически не зависят от значений обоих аргументов, функции
f_3(x_1,x_2)
и
f_4(x_1,x_2)
не зависят от значений аргумента
x_2
, а функции
f_5(x_1,x_2)
и
f_6(x_1,x_2)
не зависят от значений аргумента
x_1
.

Определение 1.1. Функция

f(x_1,\ldots, x_i,\ldots, x_n)
не зависит от аргумента
x_i
, если для любого набора значений
\sigma_1,\ldots,\sigma_{i-1},\sigma_{i+1},\ldots, \sigma_n

остальных аргументов

f
имеет место равенство
f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots, \sigma_n)= f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots, \sigma_n)
. Такой аргумент
x_i
называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

Функции

f_1(x_1,\ldots, x_n)
и
f_2(x_1,\ldots, x_m)
называются равными, если функцию
f_2
можно получить из функции
f_1
путем добавления и удаления фиктивных аргументов.

Например, равными являются одноместная функция

f_3(x_1)
и двухместная функция
f_3(x_1,x_2)
, так как вторая получается из первой добавлением фиктивного аргумента
x_2
. Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.




Начало  Назад  Вперед



Книжный магазин