2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Какие базисы булевых функций существуют?
Сообщение19.04.2007, 01:11 
Аватара пользователя
Какие существуют базисы (минимальные полные наборы) булевых функций, кроме дизъюнктивного (или, не), конъюнктивного (и, не), Жегалкина (искл.или, и, истина), Пирса (или-не) и Шеффера (и-не)?

 
 
 
 
Сообщение19.04.2007, 06:15 
Аватара пользователя
Так критерий Поста в этом помогает или вы хотите спросить сколько систем будет полными из одной, двух.. бинарных( или n-арных) булевых функций?

 
 
 
 
Сообщение25.04.2007, 13:09 
Существует бесконечно много базисов (даже и одноэлементных — для всякого n найдется, к примеру, некое n-арное обобщение штриха Шеффера).
Полезным является тот факт, что в базисе не может быть больше четырёх функций.
Если Вас интересует полный список базисов из не более чем двуместных функций, то могу посмотреть в книжках, или подумать головой, или написать какой-нибудь «перебиратель».
Сразу же приходит в голову базис, образованный импликацией и отрицанием :)

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group