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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Булева функция от <tex>n</tex> переменных — отображение <tex>B_n</tex> → <tex>B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}}
+
Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}}  
{{Определение
 
|definition=
 
Если выбрать некоторый набор булевых функций <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}}  
 
 
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>
 
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>
  
Строка 17: Строка 14:
 
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}}
 
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}}
 
{{Определение
 
{{Определение
 +
|id=def1
 
|definition=
 
|definition=
 
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}  
 
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}  
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:<br/>
+
[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:
'''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <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>.'''
 +
 
 
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
 
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
  

Текущая версия на 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