2014 dxdy logo

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

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




 
 Класс булевых функций
Сообщение29.11.2011, 20:51 
Добрый день!

Меня интересует класс булевых функций $f(x_1,\dots, x_n)$ , таких что
существуют дизъюнкции литералов (то есть булевых переменных и их отрицаний)
$\varphi_1, \dots, \varphi_n$, такиe что
$f(x_1, \dots, x_n) = 1 $ т. и т. т., когда
$ \{ \varphi_i \mid x_i = 1\}$ противоречиво.

Совпадает ли этот класс с классом монотонных функций?
Если нет, то есть ли какое-нибудь более-менее явное описание функций этого класса?
Лежит ли в этом классе функции клики и большинства ?

 
 
 
 Re: Класс булевых функций
Сообщение30.11.2011, 01:23 
С классом монотонных функций не совпадает. Потому, что $f(0,0,\ldots,0)=0$ всегда, если я правильно
понял. Однако $1\in M.$

Понятно, что любая такая функция монотонна.

Теперь возьмем произвольную монотонную булеву функцию, сохраняющую 0. И рассмотрим все её нули и нижние единицы. Необходимо задать систему дизъюнктов, которая в соответствующих множествах непротиворечива и противоречива соответственно. Понятно, что на остальных она будет противоречива.

Теперь вопрос, всегда ли можно задать такую систему?

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


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