Computations in Boolean Algebra with Approximation

• Autorzy: Kostanyan A. , Khnkoyan P.

Identyfikatory

DOI

10.3233/FI-2014-1120

• Języki publikacji: EN

Abstrakty

EN

Computations in Boolean algebra extended by adding an undefined element are investigated in the present paper. These computations (also known as approximative computations) are based on Lukasiewicz three-valued logic and are widely used in those applications where it is necessary to perform logical operations under uncertainty. The approximative computations are carried out as follows: if all instantiations of undefined operands produce the same result then this ascertained result is taken as final; otherwise, the final result is defined to be unknown. The key question in theory of approximative computations is whether a given Boolean formula is closed in the sense that the stepwise approximative computations in compliance with a given formula produce a result as accurate as possible. This question is investigated for the classes of disjunctive and algebraic normal forms.

Słowa kluczowe

EN

Lukasiewicz three-valued logic; Boolean algebra; approximative computations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 3
• Strony: 229--241
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Kostanyan A.

• Educational and Research Center of Information Technologies, Yerevan State University, Alex Manoogian 1, 0025 Yerevan, Armenia

autor

Khnkoyan P.

• Educational and Research Center of Information Technologies, Yerevan State University, Alex Manoogian 1, 0025 Yerevan, Armenia

Bibliografia

• [1] Chandra, A. K., Markowsky, G.: On the number of prime implicants, Discrete Mathematics, 24(1), 1978, 7–11.
• [2] Glushkov, V., Ceytlin, G., Yushenko, E.: Algebra. Languages. Programming, “Naukova dumka”, Kiev, 1985, (In Russian).
• [3] Hassoun, S., Sasao, T., Eds.: Logic Synthesis and Verification, Kluwer Academic Publishers, 2003.
• [4] Kleene, S.: Introduction to Metamathematics, Ishi Press International, New York, 2009.
• [5] Kostanyan, A.: Approximative Computations over the Boolean Algebra, in: Proceedings of the conference “Computer Science & Information Technologies (CSIT)”, Yerevan, Armenia, 2003, 135–139.
• [6] Kostanyan, A., Shoukourian, S., Varosyan, A.: Solvability of Formal Verification Problem for Business Process Templates, in: M&S Applications in Industry and Academia Symposium 2010 (EAIA 2010), SpringSim’2010 Multi-conference of Society for Computer Simulation, ACM Press, Orlando, FL, USA, April 2010, 11–15.
• [7] Kostanyan, A., Varosyan, A.: Partial Recognizing Algorithm for Verification of Workflow Processes, in: Proceedings of “The Future Business Technology Conference” (FUBUTEC’2008), Porto, Portugal, 2008, 89–94.
• [8] Letichevsky, A.: Algebras with approximation and recursive data structures, Kibernetika, (5), 1987, 32–37.
• [9] Shoukourian, S.: A Unified Design Methodology for Offline and Online testing, IEEE Design & Test of Computers, 15(2), 1998, 73–79.
• [10] Sloan, R. H., Szörényi, B., Turàn, G.: On k-term DNF with the largest number of prime implicants, SIAM Journal on Discrete Mathematics, 21(4), 2008, 987–998.
• [11] Zaslavsky, I.: Three-value logical function realization by means of recursive and Turing operators, in: “Issledovaniya po teorii algoritmov i matematicheskoy logike”, “Nauka”, 1979, 52–61, (In Russian).