Algebras of general non-deterministic predicates

M.S. Nikitchenko, O.S. Shkilniak, S.S. Shkilniak


Logics of general nondeterministic qua-siary predicates, called GND-predicates, are defined and investigated. These logics are program-oriented logical for-malisms that reflect such properties of programs as partiality, nondeterminism, and non-fixed arity. GND-predicates generalize partial predicates of the rela-tional type. The main attention is paid to the construction of composition algebras of GND-predicates. Compositions of GND-predicates are described, their properties are formulated. For these predicates, such important laws of tradi-tional logic as the law of absorption and the law of distributivity for for  and & are not valid. Various types of GND-predicates are identified. GND-predicates can be modeled as 7-value total deter-ministic predicates (TD7-predicates). A 7-element algebra of truth values of TD7-predicates is defined and all of its subalgebras are described. Each such subalgebra induces a corresponding al-gebra of TD7-predicates, which then in-duces the algebra of GND-predicates. This makes possible to identify a number of important composition algebras of general nondeterministic predicates. The languages of pure first-order logics of GND-predicates and their interpretations are described. The relations of a logical G-consequence and a logical G-equivalence are introduced. The relation of the logical G-consequence is mono-tonic, reflexive, and transitive; for it the properties of the decomposition of for-mulas are satisfied. On the basis of these properties, it is planned to construct cal-culi of sequential type for the logic of GND-predicates.

Problems in programming 2018; 1: 05-21


logic; algebra; non-deterministic predicate; logical consequence

Full Text:



Nikitchenko M. and Shkilniak S. (2008). Mathematical logic and theory of algorithms. Кyiv: VPC Кyivskyi Universytet (in ukr).

Nikitchenko M. and Shkilniak S. (2013). Applied logic. Кyiv: VPC Кyivskyi Universytet (in ukr).

Nikitchenko M. and Shkilniak S. (2015). Semantic Properties of Logics of Quasiary Predicates. In Workshop on Foundations of Informatics: Proceedings FOI-2015. Chisinau, Moldova. P. 180–197.

Shkilniak S. and Volkovytskyi D. (2016). Renominative logics of quasiary predicates. In Computer mathematics. 1, P. 46–57 (in ukr).

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. (2017). Logics of partial non-deterministic predicates. In International conference PDMU-2017: abstracts. Vilnius, Lithuania. P. 94–95.

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



  • There are currently no refbacks.