Introduction to Circuits, I

Journal of Formalized Mathematics
Volume 6, 1994
University of Bialystok
Copyright (c) 1994 Association of Mizar Users

Introduction to Circuits, I

Yatsuka Nakamura: Shinshu University, Nagano
Piotr Rudnicki: University of Alberta, Edmonton
Andrzej Trybulec: Warsaw University, Bialystok
Pauline N. Kawamoto: Shinshu University, Nagano

Summary.

This article is the third in a series of four articles (preceded by [20],[21] and continued in [22]) about modelling circuits by many sorted algebras.\par A circuit is defined as a locally-finite algebra over a circuit-like many sorted signature. For circuits we define notions of input function and of circuit state which are later used (see [22]) to define circuit computations. For circuits over monotonic signatures we introduce notions of vertex size and vertex depth that characterize certain graph properties of circuit's signature in terms of elements of its free envelope algebra. The depth of a finite circuit is defined as the maximal depth over its vertices.

Partial funding for this work has been provided by: Shinshu Endowment Fund for Information Science, NSERC Grant OGP9207, JSTF award 651-93-S009.

MML Identifier: CIRCUIT1

The terminology and notation used in this paper have been introduced in the following articles [25] [15] [32] [5] [4] [29] [2] [28] [33] [14] [11] [34] [18] [30] [1] [23] [6] [31] [16] [7] [3] [8] [9] [10] [17] [12] [26] [27] [13] [19] [24] [20] [21]

Contents (PDF format)

Circuit State
Vertex Size
Vertex and Circuit Depth

Bibliography

[1] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.

[2] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[3] Grzegorz Bancerek. Introduction to trees. Journal of Formalized Mathematics, 1, 1989.

[4] Grzegorz Bancerek. The ordinal numbers. Journal of Formalized Mathematics, 1, 1989.

[5] Grzegorz Bancerek. Sequences of ordinal numbers. Journal of Formalized Mathematics, 1, 1989.

[6] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.

[7] Grzegorz Bancerek. Cartesian product of functions. Journal of Formalized Mathematics, 3, 1991.

[8] Grzegorz Bancerek. K\"onig's Lemma. Journal of Formalized Mathematics, 3, 1991.

[9] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Journal of Formalized Mathematics, 4, 1992.

[10] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.

[11] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[12] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Journal of Formalized Mathematics, 5, 1993.

[13] Ewa Burakowska. Subalgebras of many sorted algebra. Lattice of subalgebras. Journal of Formalized Mathematics, 6, 1994.

[14] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[15] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.

[16] Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.

[17] Patricia L. Carlson and Grzegorz Bancerek. Context-free grammar --- part I. Journal of Formalized Mathematics, 4, 1992.

[18] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.

[19] Beata Madras. Products of many sorted algebras. Journal of Formalized Mathematics, 6, 1994.

[20] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, I. Journal of Formalized Mathematics, 6, 1994.

[21] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, II. Journal of Formalized Mathematics, 6, 1994.

[22] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Introduction to circuits, II. Journal of Formalized Mathematics, 7, 1995.

[23] Andrzej Nedzusiak. $\sigma$-fields and probability. Journal of Formalized Mathematics, 1, 1989.

[24] Beata Perkowska. Free many sorted universal algebra. Journal of Formalized Mathematics, 6, 1994.

[25] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[26] Andrzej Trybulec. Many-sorted sets. Journal of Formalized Mathematics, 5, 1993.

[27] Andrzej Trybulec. Many sorted algebras. Journal of Formalized Mathematics, 6, 1994.

[28] Andrzej Trybulec. On the sets inhabited by numbers. Journal of Formalized Mathematics, 15, 2003.

[29] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[30] Wojciech A. Trybulec. Groups. Journal of Formalized Mathematics, 2, 1990.

[31] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[32] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.

[33] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[34] Edmund Woronowicz. Relations defined on sets. Journal of Formalized Mathematics, 1, 1989.

Received December 15, 1994

[ Download a postscript version, MML identifier index, Mizar home page]