On the repetition-free realization of truth functions by two-terminal graphs I.

Ádám, András (1964) On the repetition-free realization of truth functions by two-terminal graphs I. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (1-2). pp. 11-20.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp11_-_20.pdf - Published Version Download (6MB) | Preview

Abstract

The investigations described in the present paper join to a theorem of B. Trachtenbrot ([8], Theorem 1). This theorem serves the purpose of determining a 2-graph if the truth function realized by it is known, and it solves the problem completely from theoretical point of view. However, in applying this theorem, there arises a so high number of tests which means a grave disadvantage in practical application. Our investigations are devoted to improving TRACHTENBROT'S idea into a more determined method which seems to be able for being performed by an electronic computer or by a machine built for this special aim. § 1 gives a survey on the situation of researches in the investigated field. §§ 2—4 contain the description of the proposed algorithm. The problems (arisen in boundaries of graph theory and logic) are investigated by terms of combinatorial set theory. At the end of § 4 the questions of machine realization are touched (without the endeavour to perfectness). The paper terminates with four appendices. App. 1 presents a proposition which has an auxiliary rôle in the algorithm. App. 2 considers a part of the main problem which requires to be treated separately. The two final appendices touch the immediate further questions of the theory, namely they give such mathematical formulations of the problems which will prove, it can be hoped, to be profitable in the future research.

Actions (login required)

Edit Item