2014 dxdy logo

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

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




 
 Многомерные булевые функции
Сообщение02.02.2018, 09:00 
Задана некоторая булевая функция $\mathbf f:\{0,1\}^n \to \{0,1\}^n$, которая удовлетворяет условию $\forall \mathbf x = \{0,1\}^n \quad \mathbf f(\mathbf x) \leq \mathbf x$. Здесь мы считаем, что $\mathbf x \leq \mathbf y$ тогда и только тогда, когда $\mathbf x_i \leq \mathbf y_i \quad \forall i=1,2,\dots,n$.

Будем говорить, что функция $\mathbf f$ удовлетворяет Н-свойству, если $$\forall \mathbf y \leq \mathbf x \quad \mathbf f(\mathbf x) \wedge \mathbf y \leq \mathbf f(\mathbf y),$$

где $\wedge$ обозначает покомпонентную конъюнкцию.

Я искал в интернете, но я не нашёл, есть ли способ проверить это свойство, не используя прямой перебор?

 
 
 
 Re: Многомерные булевые функции
Сообщение02.02.2018, 12:37 
Аватара пользователя
А каким образом задана функция?

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


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