We will be dealing with “sequential circuits” in the sense of E. F. Moore and G. H. Mealy. Each such circuit is assumed to have a finite number of input wires and a finite number of output wires. Each element of such a circuit will be assumed to be an and-circuit, an or-circuit, a not-circuit, or a delay circuit, for some specified temporal delay. Each element has one output wire which, however, may branch in order to serve several purposes (...) simultaneously. The and-circuits and or-circuits have two input wires each, while the not-circuits and the delay circuits have one input wire each. (shrink)

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first is insufficient to determine the value of the expression. Com...

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first argument does not suffice to determine the value of the expression. Free short-circuit logic is the equational logic in which compound statements are evaluated from left to right, while atomic evaluations are not memorised throughout the evaluation, i.e. evaluations of distinct occurrences of an atom in a compound statement may yield different truth values. We provide a simple semantics for (...) free short-circuit logic and an independent axiomatisation. Finally, we discuss evaluation strategies, some other SCLs, and side effects. (shrink)

In this paper I introduce a sequent system for the propositional modal logic S5. Derivations of valid sequents in the system are shown to correspond to proofs in a novel natural deduction system of circuit proofs (reminiscient of proofnets in linear logic, or multiple-conclusion calculi for classical logic). -/- The sequent derivations and proofnets are both simple extensions of sequents and proofnets for classical propositional logic, in which the new machinery—to take account of the modal vocabulary—is (...) directly motivated in terms of the simple, universal Kripke semantics for S5. The sequent system is cut-free and the circuit proofs are normalising. (shrink)

This book explains, in lay terms, the surprisingly simple system of mathematical logic used in digital computer circuitry. Anecdotal in its style and often funny, it follows the development of this logic system from its origins in Victorian England to its rediscovery in this century as the foundation of all modern computing machinery. ONES AND ZEROS will be enjoyed by anyone who has a general interest in science and technology.

A simplified model using kinetic logic is proposed to approach the problem after Hepatitis B viral (HBV) infection. It accounts for several stable regimes or attractors corresponding to the essential dynamic behaviour of the replication of the Hepatitis B virus. Infection with the virus can result in viral clearance, fulminant hepatic failure and death, or chronic transmissible infection, that is multistationarity corresponding to the existence of the positive feedback circuit in our modelling. Another implication of this model is the (...) existence of oscillations or homeostatic mechanisms, sometimes observed in the viral cycle, consistent with the existence of the negative feedback circuit. Thus, this report shows how a simple model of kinetic logic may be used to account for the variety of manifestations of HBV infection. This model implies the presence of the Hepatitis B e antigen, whose conservation suggests that it plays an important role in the life cycle of hepadnaviruses. Its function in the viral cycle is still unknown, but our model suggests that this antigen could explain the passage from one state of the viral infection (acute or latent) to another, as well as the oscillatory behavior which may account for the intermittent symptoms of hepatitis observed in some patients. Furthermore, this model shows a virgin state. This state is also reached after recovery. The model proposed demonstrates that starting from a viral acute infection, the host's immune response, depending on the immunological status of the patient, can lead to viral clearance, or to periodic spontaneous reactivation. (shrink)

Journal of Mathematical Logic, Ahead of Print. We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory [math] is consistent with the conjecture that [math], i.e. some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results (...) with [math] replaced by the class of problems decidable in non-deterministic barely superpolynomial time such as [math]. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds. (shrink)

This paper reviews three social scientific accounts of the civic sector's role in society: the government failure, contract failure, and voluntary failure theories. All three explain the role of nonprofit organizations as compensating for the market's failure to provide certain collective goods. This approach involves a radical misinterpretation of the underlying principles of civic sector organizations. An account is needed that explains their economy in terms of their normative concerns, rather than explaining normative concerns in terms of their economy. I (...) lay a foundation for such an account by examining the self-understanding among civic sector organizations that they should be "mission-driven," and the implications of this self-understanding for the sector as a "social economy." Whereas "mission-drivenness" calls attention to service-provision, resource-sharing, and open communication as the normative core of civic sector organizations, the notion of a "social economy" suggests a recirculation of money into channels where standard economic logic no longer holds. The key to the civic sector's role lies not in responses to market failure, but in the short-circuiting of a money-driven capitalist economy. (shrink)

Checking the equivalence of two Boolean functions, or combinational circuits modeled as Boolean functions, is often desired when reliable and correct hardware components are required. The most common approaches to equivalence checking are based on simulation and model checking, which are constrained due to the popular memory and state explosion problems. Furthermore, such tools are often not user-friendly, thereby making it tedious to check the equivalence of large formulas or circuits. An alternative is to use mathematical tools, called (...) interactive theorem provers, to prove the equivalence of two circuits; however, this requires human effort and expertise to write multiple output functions and carry out interactive proof of their equivalence. In this paper, we define two simple, one formal and the other informal, gate-level hardware description languages, design and develop a formal automatic combinational circuit equivalence checker tool, and test and evaluate our tool. The tool CoCEC is based on human-assisted theorem prover Coq, yet it checks the equivalence of circuit descriptions purely automatically through a human-friendly user interface. It either returns a machine-readable proof of circuits’ equivalence or a counterexample of their inequality. The interface enables users to enter or load two circuit descriptions written in an easy and natural style. It automatically proves, in few seconds, the equivalence of circuits with as many as 45 variables. CoCEC has a mathematical foundation, and it is reliable, quick, and easy to use. The tool is intended to be used by digital logic circuit designers, logicians, students, and faculty during the digital logic design course. (shrink)

Rice Combinational and Sequential Logic This text provides a guide to combinational and sequential logic, introducing students to the basic concepts then progressing to HND/first year undergraduate level. It has a highly practical emphasis, enabling the reader to simulate, build and test the circuits discussed in the text. Electronics Workbench files are provided for simulation, while easy-to-use XPLA software and specially designed hardware encourage the reader to build and test the circuits using programmable logic. The (...) text itself contains many self-assessment questions, complete with detailed answers, allowing students to test themselves as they learn. No previous experience of the topic is required and an abundance of practical examples helps students to apply the basic principles. The accompanying CD-ROM provides the XPLA development system software and Electronics Workbench files, as well as the Xilinx Webpack development system and 'walkthrough'. Hardware for Programmable Logic experiments can either be purchased or built following instructions from the text. Altogether, the text, software and hardware provide an interactive and stimulating teaching and learning resource. F. (shrink)

The living mycelium networks are capable of efficient sensorial fusion over very large areas and distributed decision making. The information processing in the mycelium networks is implemented via propagation of electrical and chemical signals en pair with morphological changes in the mycelium structure. These information processing mechanisms are manifested in experimental laboratory findings that show that the mycelium networks exhibit rich dynamics of neuron-like spiking behaviour and a wide range of non-linear electrical properties. On an example of a single real (...) colony of _Aspergillus niger_, we demonstrate that the non-linear transformation of electrical signals and trains of extracellular voltage spikes can be used to implement logical gates and circuits. The approaches adopted include numerical modelling of excitation propagation on the mycelium network, representation of the mycelium network as a resistive and capacitive network and an experimental laboratory study on mining logical circuits in mycelium bound composites. (shrink)

We propose that, for the purpose of studying theoretical properties of the knowledge of an agent with Artificial General Intelligence (that is, the knowledge of an AGI), a pragmatic way to define such an agent’s knowledge (restricted to the language of Epistemic Arithmetic, or EA) is as follows. We declare an AGI to know an EA-statement φ if and only if that AGI would include φ in the resulting enumeration if that AGI were commanded: “Enumerate all the EA-sentences which you (...) know.” This definition is non-circular because an AGI, being capable of practical English communication, is capable of understanding the everyday English word “know” independently of how any philosopher formally defines knowledge; we elaborate further on the non-circularity of this circular-looking definition. This elegantly solves the problem that different AGIs may have different internal knowledge definitions and yet we want to study knowledge of AGIs in general, without having to study different AGIs separately just because they have separate internal knowledge definitions. Finally, we suggest how this definition of AGI knowledge can be used as a bridge which could allow the AGI research community to import certain abstract results about mechanical knowing agents from mathematical logic. (shrink)

The value of logic techniques in circuit design has been well-known for many years, but a thorough grounding in mathematical logic is needed for all stages of software development, especially program specification, verification and program transformation. In all these stages, logic underpins the theory, bearing out the dictum that Logic is the calculus of computer science. This book presents the subject of mathematical logic in order to provide a grounding for students in computer science.

We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory [Formula: see text] is consistent with the conjecture that [Formula: see text], i.e. some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results with [Formula: see text] (...) replaced by the class of problems decidable in non-deterministic barely superpolynomial time such as [Formula: see text]. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds. (shrink)

In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: It is very natural to define in this logic two negations, (...) weak negation as failure to verify a sentence, and strong negation as the existence of a falsifying strategy: One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc. (shrink)

Most studies of motifs of biological regulatory networks focus on the analysis of asymptotical behaviours, but transient properties are rarely addressed. In the line of our previous study devoted to isolated circuits 19:172–178, 2003), we consider chorded circuits, that are motifs made of an elementary positive or negative circuit with a chord, possibly a self-loop. We provide detailed descriptions of the boolean dynamics of chorded circuits versus isolated circuits, under the synchronous and asynchronous updating schemes within (...) the logical formalism. To this end, we address the description of the trajectories in the dynamics of isolated circuits with coding techniques and adapt them for chorded circuits. The use of the logical modeling gives access to mathematical tools allowing complete analytical analysis of basic yet important motifs. In particular, we show that whatever the chosen updating rule, the dynamics depends on a small number of parameters. (shrink)

The mechanisms by which bacteria adapt to changes in their environment involve transcriptional regulation in which a transcriptional regulator responds to signal(s) from the environment and regulates (positively or negatively) the expression of several genes or operons. Some of these regulators exert a positive feedback on their own expression. This is a necessary (although not sufficient) condition for the occurrence of multistationarity. One biological consequence of multistationarity may be epigenetic modifications, a hypothesis unusual to microbiologists, in spite of some well-known (...) epigenetic modifications in bacteria. We propose here that the occurrence of mucoidy in the opportunistic pathogen Pseudomonas aeruginosa, which is currently attributed to mutations only, may also be an epigenetic modification. A theoretical approach using a generalised logical analysis lends credit to this hypothesis and suggests experiments to ascertain it. (shrink)

The human brain is the first computer to which all others are compared. Yet we know painfully little about how a brain accomplishes its peculiar computations. In particular, consciousness is at once familiar and mysterious, and needs to be understood both for science and for medicine. Boldly, but gently this book introduces a reader to the neural circuitry that achieves consciousness. This amazing interconnection enables consciousness to flow like a stream, intimately relevant to the outside world; and for this to (...) happen, fundamental cues emerge from mental images to bring forth associated recalls. Alas cues can be inconsistent, causing memory failure; fortunately a subliminal cue editor encourages remembering forgotten items. Furthermore, cues generally address several memories, forcing the brain to make a selection. This necessitates another special circuit whose purpose is subliminal editing. The simplified explanations provided in this book make it clear that neurons do far more than ordinary devices, since a single neuron is capable of remarkably dense combinational and sequential logic. Beginning with their interesting and unexpected logical behavior, the reader will genuinely enjoy Dr. Burger's synthesis of a system for biological consciousness, a system that may someday result in credible artificial consciousness. (shrink)

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62 457–486] allows to derive from some short semantic derivations of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol computing the Karchmer–Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] (...) from [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity. In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle, that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63 1582–1596] ) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. (shrink)

A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory \ of all polynomial time functions. Generalizing a theorem of Hirschfeld :111–126, 1975), we show that every countable model of \ is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical sense of Keisler Ultrafilters across (...) mathematics, contemporary mathematics vol 530, pp 163–179. AMS, New York, 1963). Using a polynomial time ultrapower over a nonstandard Herbrand saturated model of \ we show that \ is consistent with a formal statement of a polynomial size circuit lower bound for a polynomial time computable function. This improves upon a recent result of Krajíček and Oliveira, 2017). (shrink)

Fine and Saad-Filho are wrong to insist that an abstract category of production should be the starting point of Marxist value-theory in logical, temporal and causal terms. Marx, in Capital, begins with a repertoire of simpler categories and slowly constructs the complex category of capitalist production. It is vital that exploitation should be seen as one phase of a process of capital-in-motion, and due weight given to money, competition and realisation.