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

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


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

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

  1. - константа 0;
  2. - константа 1;
  3. - тождественная функция;
  4. Эта функция называется отрицанием

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

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

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

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

  

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

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

  • - константа 0;
  • - константа 1;
  • - функция, равная 1-му аргументу;
  • - отрицание
    ;
  • - функция, равная 2-му аргументу;
  • - отрицание
    ;
  • - конъюнкция, читается "
    и
    " (используются также обозначения
    ,
    ,
    и
    AND
    ));
  • - дизъюнкция, читается "
    или
    " (используются также обозначения
    ,
    и
    OR
    ));
  • - импликация, читается "
    влечет
    " или "из
    следует
    " (используются также обозначения
    , и ( IF
    THEN
    ));
  • - сложение по модулю 2, читается "
    плюс
    " (используется также обозначение
    );
  • - эквивалентность, читается "
    эквивалентно (равносильно)
    " (используется также обозначение
    );
  • - штрих Шеффера (антиконъюнкция), иногда читается как "не
    и
    ".

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

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

и
фактически не зависят от значений обоих аргументов, функции
и
не зависят от значений аргумента
, а функции
и
не зависят от значений аргумента
.

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

не зависит от аргумента
, если для любого набора значений

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

имеет место равенство
. Такой аргумент
называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

Функции

и
называются равными, если функцию
можно получить из функции
путем добавления и удаления фиктивных аргументов.

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

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



Содержание раздела