Представление функции формулой, полные системы функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Представление функции формулой)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 1: Строка 1:
== Полные системы функций ==
+
== Представление функции формулой ==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}  
+
Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <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>\mathrm{TrCl}(R)</tex> отношения <tex>R</tex> на множестве <tex>X</tex> называется пересечение всех транзитивных отношений, содержащих <tex>R</tex> как подмножество (иначе, минимальное транзитивное отношение, содержащее <tex>R</tex> как подмножество).}}
+
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}
 +
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:
 +
 
 +
'''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.'''
  
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:<br/>
 
'''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.'''<br />
 
 
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
 
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
  
Строка 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> можно назвать базисом класса линейных функций.
  
== Представление функции формулой ==
+
==Источники==
Если задана какая-либо полная система функций <math>A</math>, то '''любую''' функцию можно выразить, составив формулу, содержащую только функции из множества <tex>A</tex>. Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>.
+
http://ru.wikipedia.org

Текущая версия на 19:14, 4 сентября 2022

Представление функции формулой

Определение:
Если выбрать некоторый набор булевых функций [math]A[/math], то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой.

Например, если [math]A = \left\{\land,\neg\right\}[/math], то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]

Полные системы функций

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


Определение:
Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.


Определение:
Множество [math]A[/math] функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций.

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:

Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math], [math]T_1[/math], [math]S[/math], [math]M[/math], [math]L[/math].

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

Широко известны такие полные системы булевых функций:

  • [math]\left\{\land,\lor,\neg\right\}[/math] (конъюнкция, дизъюнкция, отрицание);
  • [math]\left\{\land,\oplus,1\right\}[/math] (конъюнкция, сложение по модулю 2, константа 1).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

Определение:
Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента.

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

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему [math]\left\{\oplus,1\right\}[/math] можно назвать базисом класса линейных функций.

Источники

http://ru.wikipedia.org