Geodesic
Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 1, pp. 83-95 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper examines graphs of 2-CNF of bijunctive functions and their order functions. The notion of depth of bijunctive function is introduced. Estimates of the weight of bijunctive function with a given depth are obtained. 
@article{MVK_2021_12_1_a3,
     author = {A. V. Tarasov},
     title = {Bijunctive {Boolean} functions, graphs of {2-CNF} and their order functions. {Estimates} of weight of a bijunctive function with a given number of layers},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {83--95},
     year = {2021},
     volume = {12},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a3/}
}
TY  - JOUR
AU  - A. V. Tarasov
TI  - Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 83
EP  - 95
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a3/
LA  - ru
ID  - MVK_2021_12_1_a3
ER  - 
%0 Journal Article
%A A. V. Tarasov
%T Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers
%J Matematičeskie voprosy kriptografii
%D 2021
%P 83-95
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a3/
%G ru
%F MVK_2021_12_1_a3
A. V. Tarasov. Bijunctive Boolean functions, graphs of 2-CNF and their order functions. Estimates of weight of a bijunctive function with a given number of layers. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 1, pp. 83-95. http://geodesic.mathdoc.fr/item/MVK_2021_12_1_a3/

[1] Allen P., “Almost every 2-SAT function is unate”, Israel J. Math., 161:1 (2007), 311–346 | DOI | MR | Zbl

[2] Gorshkov S. P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozr. prikl. i promyshl. matem., 2:3 (1995), 325–398

[3] Gorshkov S. P., Tarasov A. V., Slozhnost resheniya sistem bulevykh uravnenii, Kurs, M., 2017, 192 pp.

[4] Tarasov A. V., “O svoistvakh funktsii, predstavimykh v vide 2-KNF”, Diskretnaya matematika, 13:4 (2001), 99–115 | Zbl

[5] Tarasov A. V., “O metodakh otsenivaniya vesa bulevykh biyunktivnykh funktsii”, Matematicheskie voprosy kriptografii, 8:4 (2018), 125–142

[6] Gorshkov S. P.,Tarasov A. V., “O vese bulevykh funktsii, predstavimykh v vide 2-KNF ili 3-KNF”, Matematicheskie voprosy kriptografii, 9:4 (2018), 5–26 | MR

[7] Kofman A., Vvedenie v prikladnuyu kombinatoriku, Mir, M., 1975, 480 pp.