## Abstract

Programming languages admit the ternary operator if*p* then*f* else*g* where*p* is a test which may not halt. Here,*p* ranges over a suitable 3-valued logic. Guzmán and Squier recently introduced “C-algebras” and an equational 3-valued generalization of Boolean algebra based on “or”, “andrd and “not”. We incorporate their results and introduce as well the concept of “ada” (for Algebra of Disjoint Alternatives) which results when*C*-algebras are equipped with an oracle for the halting problem. The 3-element ada is functionally complete. For if-then-else over a Boolean algebra or over an ada, eight equations generate all. The resulting variety may be represented as a variety of modules over a Boolean algebra. Over a*C*-algebra, a ninth equation is required.

This is a preview of subscription content, access via your institution.

## References

- [1]
Bergman, G.,

*Actions of Boolean rings on sets*. Algebra Universalis*28*(1991), 153–187. - [2]
Bloom, S. L. andTindell, R.,

*Varieties of “if-then-else”*. SIAM J. Comput.*12*(1983), 677–707. - [3]
Cohn, P. M.,

*Universal Algebra*. Harper and Row, 1965. - [4]
Dijkstra, E. W.,

*A Discipline of Programming*. Prentice Hall, 1976. - [5]
Foster, A. L.,

*p-rings and their Boolean-vector representation*. Acta Mathematica*84*(1951), 231–261. - [6]
Foster, A. L.,

*Generalized “Boolean” theory of universal algebras, Part II. Identities and subdirect sums of functionally complete algebras*. Math. Zeit.*59*(1953), 191–199. - [7]
Gries, D.,

*The Science of Programming*. Springer-Verlag, 1981. - [8]
Guessarian, I. andMeseguer, J.,

*On the axiomalization of if-then-else*. SIAM J. Comput.*16*(1987), 332–357. - [9]
Guzmán, F. andSquier, C.,

*The algebra of conditional logic*. Algebra Universalis*27*(1990), 88–110. - [10]
Hoare, C. A. R.,

*Communicating Sequential Processes*. Prentice-Hall, 1985. - [11]
Hu, T.-K.,

*Stone duality for primal algebra theory*. Math. Z.*110*(1969), 180–198. - [12]
Huntington, E. V.,

*Sets of independent postulates for the algebra of logic*. Trans. Amer. Math. Soc.*5*(1904), 288–309. - [13]
Johnson, J. S. andManes, E. G.,

*On modules over a semiring*. J. Algebra*15*(1970), 57–67. - [14]
Kleene, S.,

*Introduction to Metamathematics*. Van Nostrand, 1952. - [15]
Lawvere, F. W.,

*Functorial Semantics of Algebraic Theories*. Dissertation, Mathematics Department, Columbia University, 1963. - [16]
Manes, E. G.,

*Guard modules*. Algebra Universalis*21*(1985), 103–110. - [17]
Manes, E. G.,

*Predicate Transformer Semantics*. Cambridge University Press, 1993. - [18]
Manes, E. G. andArbib, M. A.,

*Algebraic Approaches to Program Semantics*. Springer-Verlag, 1986. - [19]
McCarthy, J.,

*A basis for a mathematical theory of computation*. In P. Braffort and D. Hirschberg (eds.),*Computer Programming and Formal Systems*. North-Holland (1963), 33–70. - [20]
McCarthy, J.,

*Predicate calculus with “undefined” as a truth value*. Stanford A. I. memo, Feb., 1979. - [21]
McCoy, N. H. andMontgomery, D.,

*A representation of generalized Boolean rings*. Duke Math. J.*3*(1937), 455–459. - [22]
Mekler, A. H. andNelson, E. M.,

*Equational bases for if-then-else*. SIAM J. Comput.*16*(1987), 465–485. - [23]
Mitchell, B.,

*Theory of Categories*. Academic Press, 1965. - [24]
Stone, M. H.,

*The theory of representations of Boolean algebras*. Trans. Amer. Math. Soc.*40*(1936), 37–111. - [25]
Taylor, W.,

*Equational Logic*. Houston J. Math.*5*(1979), 86pp.

## Author information

### Affiliations

## Rights and permissions

## About this article

### Cite this article

Manes, E.G. Adas and the equational theory of if-then-else.
*Algebra Universalis* **30, **373–394 (1993). https://doi.org/10.1007/BF01190447

Received:

Accepted:

Issue Date:

### Keywords

- Programming Language
- Boolean Algebra
- Equational Theory
- Ternary Operator
- Ninth Equation