Deviant truth-values algebras and deviant classes of general non-deterministic predicates 14 Software environment and tools

O.S. Shkilniak


In this paper we study new classes
of program-oriented logical formalisms – logics of general non-deter­ministic (GND) predicates. These logics reflect such properties of programs as nondeterminism, partiality, and non-fixed
arity. GND-predicates can be modeled as 7-valued total deterministic (TD7) predicates. The main attention is paid
to algebras of truth values (TV-algebras) of TD7-predicates. The set of truth values TV7 = {T, F, T#, F#, #,  TF, TF#} defines TV-algebrа ATV7 = (TV7,  {Ø*, Ú*}). There 20 subalgebras of ATV7 exist, and each of them induces a corresponding algebra of GND-predicates. At the same time there is a very large number of 7-valued logics so a lot of TV7 subsets are not closed under Ø* or Ú* and do not form subalgebras of ATV7. We call such subsets with the corresponding classes of GND-predicates deviant, they are not closed under logical connectives of GND-predicates. In order for deviant TV Í TV7 to form an algebra we need to modify Ø* or Ú*. Modifications can be made in a large number of ways. Modification of Ø* leads to specific non-classical logics and lies outside the scope of this paper. Modifications of Ú* sa­tisfying the TFC condition of predicate algebras logical connectives correctness are the most important, otherwise we obtain deviant TV-algebra which does not induce an algebra of GND-predicates. For all TV7 subsets we study the possibility of Ú* modification with TFC condition. Such modifica­tion induces corresponding classes of GND-predicates. We describe “natural” modifications of Ú* without TFC condition obtaining a number of deviant TV-algebras. There are no modifications with TFC condition for de­viant sets {#, TF, TF#}, {TF, #}, {TF#, #}, so for them we specify “relatively natural” deviant TV-algebras.

Problems in programming 2019; 1: 14-26


logic; algebra; non-deterministic predicate; 7-valued predicate

Full Text:

PDF (Ukrainian)


Abramsky S., Gabbay D. and Maibaum T. (editors). (1993–2000). Handbook of Logic in Computer Science Oxford University Press, Vol. 1–5.

Avron A. and Zamansky A. (2011). Non-deterministic semantics for logical systems. In Handbook of Philosophical Logic, D.M. Gabbay, F. Guenthner (eds.), 2nd ed., vol. 16, Springer Netherlands. P. 227–304. CrossRef

Hähnle R. (2005). Many-valued logic, partiality, and abstraction in formal specification languages. In Logic Journal of the IGPL, 13. P. 415–433. CrossRef

Jones C. (2006). Reasoning about partial functions in the formal development of programs. In Proceedings of AVoCS'05. V. 145. Elsevier, Electronic Notes in Theoretical Computer Science. P. 3–25. CrossRef

Nikitchenko M., Shkilniak O. and Shkilniak S. (2016). Pure first-order logics of quasiary predicates. In Problems in Progamming. N 2–3. P. 73–86 (in ukr).

Nikitchenko M. and Shkilniak S. (2017). Algebras and logics of partial quasiary predicates. In Algebra and Discrete Mathematics. Vol. 23. N 2. P. 263–278.

Nikitchenko M., Shkilniak O. and Shkilniak S. (2018). Algebras of general non-deterministic predicates. In Problems in Progamming. N 1. P. 5–21 (in ukr). CrossRef

Nikitchenko M., Shkilniak O. and Shkilniak S. (2018). Logics of general non-deterministic predicates: semantic aspects. In Problems in Progamming. N 2–3. P. 31–45 (in ukr).

Belnap N. and Steel T. (1976). The Logic of Questions and Answers. New Haven and London: Yale Univ. Press.

Nikitchenko M., and Shyshatska E. (2018). Algebras of general non-deterministic predicates. In Problems in Progamming. N 1. P. 22–35 (in ukr). CrossRef



  • There are currently no refbacks.