Geodesic
On the properties of functions representable in the form of a 2-CNF
Diskretnaya Matematika, Tome 13 (2001) no. 4, pp. 99-115 
A. V. Tarasov. On the properties of functions representable in the form of a 2-CNF. Diskretnaya Matematika, Tome 13 (2001) no. 4, pp. 99-115. http://geodesic.mathdoc.fr/item/DM_2001_13_4_a6/
@article{DM_2001_13_4_a6,
     author = {A. V. Tarasov},
     title = {On the properties of functions representable in the form of a {2-CNF}},
     journal = {Diskretnaya Matematika},
     pages = {99--115},
     year = {2001},
     volume = {13},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_4_a6/}
}
TY  - JOUR
AU  - A. V. Tarasov
TI  - On the properties of functions representable in the form of a 2-CNF
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 99
EP  - 115
VL  - 13
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_4_a6/
LA  - ru
ID  - DM_2001_13_4_a6
ER  - 
%0 Journal Article
%A A. V. Tarasov
%T On the properties of functions representable in the form of a 2-CNF
%J Diskretnaya Matematika
%D 2001
%P 99-115
%V 13
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2001_13_4_a6/
%G ru
%F DM_2001_13_4_a6

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider properties of Boolean bijunctive functions. The class of the Boolean bijunctive functions consists of the functions which can be represented as a 2-CNF\@. We give an algorithm to minimise a bijunctive function.

[1] Schaefer T., “Complexity of satisfiability problems”, Proc. 10th Annual ACM Symp. on Theory of Computing, 1978, 216–226 | MR

[2] Dantsin E. Ya., “Algoritmika zadachi vypolnimosti”, Voprosy kibern, 131 (1987), 7–21 | MR

[3] Gorshkov S. P., “Primenenie teorii $NP$-polnykh zadach dlya otsenki slozhnosti resheniya bulevykh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 325–398 | MR

[4] Gorshkov S. P., “O slozhnosti zadachi nakhozhdeniya chisla reshenii sistem bulevykh uravnenii”, Diskretnaya matematika, 8:1 (1996), 72–85 | MR

[5] Gorshkov S. P., “O peresechenii klassov multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Obozrenie prikladnoi i promyshlennoi matematiki, 4:2 (1997), 238–259

[6] Gizunov S. A., Nosov V. A., “O klassifikatsii vsekh bulevykh funktsii 4-kh peremennykh po klassam Shefera”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 440–467

[7] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[8] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, Moskva, 1979 | MR | Zbl

[9] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, Moskva, 1979 | MR

[10] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR

[11] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1979 | MR | Zbl