Представление функции формулой, полные системы функций — различия между версиями
(→Представление функции формулой) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 22 промежуточные версии 5 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == | + | == Представление функции формулой == |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}} | |
| + | Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex> | ||
| + | == Полные системы функций == | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | '''Замкнутым множеством''' функций называется такое множество, что любая функция алгебры логики, выражаемая с помощью содержащихся в множестве функций, уже содержится в этом множестве.}} | ||
| + | {{Определение | ||
| + | |definition= | ||
| + | '''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}} | ||
{{Определение | {{Определение | ||
| + | |id=def1 | ||
|definition= | |definition= | ||
| − | ''' | + | Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} |
| + | [[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций: | ||
| + | |||
| + | '''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.''' | ||
| − | |||
| − | |||
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера. | В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера. | ||
| Строка 17: | Строка 27: | ||
* <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю 2, константа 1). | * <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю 2, константа 1). | ||
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]]. | Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]]. | ||
| − | + | {{Определение | |
| − | Полная система функций называется ''' | + | |definition= |
| + | Полная система функций называется '''безызбыточной''', если она перестаёт быть полной при исключении из неё любого элемента. | ||
| + | }} | ||
| + | Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. | ||
Максимально возможное число булевых функций в базисе — 4. | Максимально возможное число булевых функций в базисе — 4. | ||
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций. | Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций. | ||
| − | == | + | ==Источники== |
| − | + | http://ru.wikipedia.org | |
Текущая версия на 19:14, 4 сентября 2022
Представление функции формулой
| Определение: |
| Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой. |
Например, если , то функция представляется в виде
Полные системы функций
| Определение: |
| Замкнутым множеством функций называется такое множество, что любая функция алгебры логики, выражаемая с помощью содержащихся в множестве функций, уже содержится в этом множестве. |
| Определение: |
| Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций. |
| Определение: |
| Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. |
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов , , , , .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
Широко известны такие полные системы булевых функций:
- (конъюнкция, дизъюнкция, отрицание);
- (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
| Определение: |
| Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента. |
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему можно назвать базисом класса линейных функций.
