Locally monotone Boolean and pseudo-Boolean functions (Q444430): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
Several generalizations of monotonicity for Boolean functions \(f:\{0,1\}^n\longrightarrow\{0,1\}\) and pseudo-Boolean functions \(f:\{0,1\}^n\longrightarrow{\mathbb R}\) are introduced. They are defined in terms of the discrete partial derivatives \(\Delta_kf(\mathbf{x})=f(\mathbf{x}_k^1)-f(\mathbf{x}_k^0)\), where \(\mathbf{x}_k^i=(x_1,\dots,x_k=i,\dots,x_n)\) (\(i \in \{0,1\}\)), as follows: for \(p\in\{1,\dots,n\}\), \(f\) is said to be \(p\)-locally monotone if \[ \sum_{i\in[n]\setminus[k]}| x_i-y_i|<p\Longrightarrow\Delta_k f(\mathbf{x})-\Delta_k(\mathbf{y})\geq0. \] Any \(p\)-locally monotone pseudo-Boolean function is also \(p'\)-locally monotone for every \(p'\leq p\). Every pseudo-Boolean function \(f\) is 1-locally monotone, and \(f\) is \(n\)-locally monotone iff it is monotone (i.e., isotone or antitone). A 2-locally monotone function is said to be locally monotone. A section of a function \(f\) is the function obtained from \(f\) by replacing some of its variables by constants. Sample results: A function is \(p\)-locally monotone iff every \(p\)-ary section of it is monotone. A Boolean function \(f\) is locally monotone iff neither \(x\oplus y\) nor \(x\oplus y\oplus 1\) is a section of \(f\). The partial lattice derivatives of a pseudo-Boolean function are defined by \(\bigwedge_kf(\mathbf{x})=f(\mathbf{x}_k^0)\wedge f(\mathbf{x}_k^1)\) and \(\bigvee_kf(\mathbf{x})=f(\mathbf{x}_k^0)\vee f(\mathbf{x}_k^1)\). A Boolean function \(f\) is locally monotone iff \(\bigvee_k\bigwedge_j f=\bigwedge_j\bigvee_k f\) for every \(j\neq k\). A more general concept of \(p\)-permutability of lattice derivatives is defined and the relationship between this property and local monotonicity is studied in detail. If two functions \(f,g:\{0,1\}^n\to{\mathbb R}\) have equal lattice derivatives then either \(f=g\) or there is an injection \(\alpha:\{0,1\}\to{\mathbb R}\) such that \(f(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n)\) and \(g(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n\oplus 1)\). The last section deals with special properties of symmetric functions. Finally, two open problems are stated. The paper is carefully written, with illustrative examples and two counterexamples to certain suppositions. Interesting connections with game theory are established. | |||
Property / review text: Several generalizations of monotonicity for Boolean functions \(f:\{0,1\}^n\longrightarrow\{0,1\}\) and pseudo-Boolean functions \(f:\{0,1\}^n\longrightarrow{\mathbb R}\) are introduced. They are defined in terms of the discrete partial derivatives \(\Delta_kf(\mathbf{x})=f(\mathbf{x}_k^1)-f(\mathbf{x}_k^0)\), where \(\mathbf{x}_k^i=(x_1,\dots,x_k=i,\dots,x_n)\) (\(i \in \{0,1\}\)), as follows: for \(p\in\{1,\dots,n\}\), \(f\) is said to be \(p\)-locally monotone if \[ \sum_{i\in[n]\setminus[k]}| x_i-y_i|<p\Longrightarrow\Delta_k f(\mathbf{x})-\Delta_k(\mathbf{y})\geq0. \] Any \(p\)-locally monotone pseudo-Boolean function is also \(p'\)-locally monotone for every \(p'\leq p\). Every pseudo-Boolean function \(f\) is 1-locally monotone, and \(f\) is \(n\)-locally monotone iff it is monotone (i.e., isotone or antitone). A 2-locally monotone function is said to be locally monotone. A section of a function \(f\) is the function obtained from \(f\) by replacing some of its variables by constants. Sample results: A function is \(p\)-locally monotone iff every \(p\)-ary section of it is monotone. A Boolean function \(f\) is locally monotone iff neither \(x\oplus y\) nor \(x\oplus y\oplus 1\) is a section of \(f\). The partial lattice derivatives of a pseudo-Boolean function are defined by \(\bigwedge_kf(\mathbf{x})=f(\mathbf{x}_k^0)\wedge f(\mathbf{x}_k^1)\) and \(\bigvee_kf(\mathbf{x})=f(\mathbf{x}_k^0)\vee f(\mathbf{x}_k^1)\). A Boolean function \(f\) is locally monotone iff \(\bigvee_k\bigwedge_j f=\bigwedge_j\bigvee_k f\) for every \(j\neq k\). A more general concept of \(p\)-permutability of lattice derivatives is defined and the relationship between this property and local monotonicity is studied in detail. If two functions \(f,g:\{0,1\}^n\to{\mathbb R}\) have equal lattice derivatives then either \(f=g\) or there is an injection \(\alpha:\{0,1\}\to{\mathbb R}\) such that \(f(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n)\) and \(g(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n\oplus 1)\). The last section deals with special properties of symmetric functions. Finally, two open problems are stated. The paper is carefully written, with illustrative examples and two counterexamples to certain suppositions. Interesting connections with game theory are established. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sergiu Rudeanu / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06E30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C09 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 91A99 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94C10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6065729 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Boolean function | |||
Property / zbMATH Keywords: Boolean function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pseudo-Boolean function | |||
Property / zbMATH Keywords: pseudo-Boolean function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
local monotonicity | |||
Property / zbMATH Keywords: local monotonicity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
discrete partial derivative | |||
Property / zbMATH Keywords: discrete partial derivative / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
join and meet derivatives | |||
Property / zbMATH Keywords: join and meet derivatives / rank | |||
Normal rank |
Revision as of 02:49, 30 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Locally monotone Boolean and pseudo-Boolean functions |
scientific article |
Statements
Locally monotone Boolean and pseudo-Boolean functions (English)
0 references
14 August 2012
0 references
Several generalizations of monotonicity for Boolean functions \(f:\{0,1\}^n\longrightarrow\{0,1\}\) and pseudo-Boolean functions \(f:\{0,1\}^n\longrightarrow{\mathbb R}\) are introduced. They are defined in terms of the discrete partial derivatives \(\Delta_kf(\mathbf{x})=f(\mathbf{x}_k^1)-f(\mathbf{x}_k^0)\), where \(\mathbf{x}_k^i=(x_1,\dots,x_k=i,\dots,x_n)\) (\(i \in \{0,1\}\)), as follows: for \(p\in\{1,\dots,n\}\), \(f\) is said to be \(p\)-locally monotone if \[ \sum_{i\in[n]\setminus[k]}| x_i-y_i|<p\Longrightarrow\Delta_k f(\mathbf{x})-\Delta_k(\mathbf{y})\geq0. \] Any \(p\)-locally monotone pseudo-Boolean function is also \(p'\)-locally monotone for every \(p'\leq p\). Every pseudo-Boolean function \(f\) is 1-locally monotone, and \(f\) is \(n\)-locally monotone iff it is monotone (i.e., isotone or antitone). A 2-locally monotone function is said to be locally monotone. A section of a function \(f\) is the function obtained from \(f\) by replacing some of its variables by constants. Sample results: A function is \(p\)-locally monotone iff every \(p\)-ary section of it is monotone. A Boolean function \(f\) is locally monotone iff neither \(x\oplus y\) nor \(x\oplus y\oplus 1\) is a section of \(f\). The partial lattice derivatives of a pseudo-Boolean function are defined by \(\bigwedge_kf(\mathbf{x})=f(\mathbf{x}_k^0)\wedge f(\mathbf{x}_k^1)\) and \(\bigvee_kf(\mathbf{x})=f(\mathbf{x}_k^0)\vee f(\mathbf{x}_k^1)\). A Boolean function \(f\) is locally monotone iff \(\bigvee_k\bigwedge_j f=\bigwedge_j\bigvee_k f\) for every \(j\neq k\). A more general concept of \(p\)-permutability of lattice derivatives is defined and the relationship between this property and local monotonicity is studied in detail. If two functions \(f,g:\{0,1\}^n\to{\mathbb R}\) have equal lattice derivatives then either \(f=g\) or there is an injection \(\alpha:\{0,1\}\to{\mathbb R}\) such that \(f(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n)\) and \(g(\mathbf{x})=\alpha(x_1\oplus\dots\oplus x_n\oplus 1)\). The last section deals with special properties of symmetric functions. Finally, two open problems are stated. The paper is carefully written, with illustrative examples and two counterexamples to certain suppositions. Interesting connections with game theory are established.
0 references
Boolean function
0 references
pseudo-Boolean function
0 references
local monotonicity
0 references
discrete partial derivative
0 references
join and meet derivatives
0 references