Булевы функции от 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. Функция

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

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

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

Функции

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

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

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

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

---

---