вход Вход Регистрация



 

Базисом, функционально полной системой булевых функций (ФПСБФ) называют совокупность таких булевых функций , что произвольная ФАЛ может быть записана в виде формулы через функции этой совокупности.

ФПСБФ:

Определим свойства, которыми должна обладать функция, составляющие ФПСБФ. Рассмотрим предполные классы ФАЛ. Проведённые исследования показали, что предполных классов – 5, а для построения ФПСБФ необходимо и достаточно, чтобы её функции не содержались полностью ни в одном из 5 предполных классов.

Предполные классы ФАЛ:

1. класс функций, сохраняющих const 0

2. класс функций, сохраняющих const 1

3. класс самодвойственных булевых функций

4. класс линейных булевых функций

5. класс монотонных булевых функций

Функции класса 2. Если функция на единичном наборе = 1, то говорят, что она сохраняет единицу .

Функция класса 1. – .

Функции класса 3. ФАЛ называют самодвойственной, если на каждой паре противоположных наборов она принимает противоположные значения, то есть

Функции класса 4. К линейным ФАЛ относятся функции, которые могут представить в виде , где .

Функции класса 5. ФАЛ называют монотонной, если при любом возрастании набора значения этой функции не убывают.

Теорема Поста-Яблонского. Для того, чтобы система ФАЛ была функционально полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию:

- не сохраняющую 0,

- не сохраняющую 1,

- не являющуюся линейной,

- немонотонную,

- не самодвойственную.

 

Рассмотрим примеры ФПСБФ:

 

Функция классы
00 01 10 11
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0 + + + + +
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0 + + + + +
1 1 1 1

 

Функции и являются ФПСБФ. Из таблицы можно получить и другие ФПСБФ:

 

 

 

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру