Functional completeness

Summary

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT. A gate or set of gates which is functionally complete can also be called a universal gate / gates. A functionally complete set of gates may utilise or generate 'garbage bits' as part of its computation which are either not part of the input or not part of the output to the system. In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate. From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as

Official source

https://en.wikipedia.org/wiki/Functional_completeness

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (5)

Related publications

Related people

Related units

Related concepts (21)

Related concepts

Related courses (1)

Related courses

Related lectures (1)

Related lectures

Frequentist estimation of an epidemic's spreading potential when observations are scarce

Andrea Kraus, Victor Panaretos

We consider the problem of inferring the potential of an epidemic for escalating into a pandemic on the basis of limited observations in its initial stages. Classical results of Becker & Hasofer (J. R. Statist. Soc. B, 59, 415-29) illustrate that frequentist estimation of the complete set of parameters of an epidemic modelled as a birth and death process remains feasible even when one is able to observe only the deaths and the total number of births. These assumptions on the observation mechanism, however, are too strong to be met in practice. We consider a more realistic scenario where only temporally aggregated random proportions of the deaths are observed over time. We demonstrate that the frequentist estimation of the Malthusian parameter governing the growth of the epidemic is still feasible in this context. We construct explicit straightforwardly calculable estimators motivated heuristically by the martingale dynamics of the process, and show that they admit a rigorous quasilikelihood interpretation. We establish the consistency and asymptotic normality of these estimators, allowing for the construction of approximate confidence intervals that can be used to infer the spreading potential of the epidemic. A simulation study and an application to the initial outbreak data of the 2009 H1N1 influenza pandemic illustrate that the method can be expected to give reasonable results in practice.

Oxford University Press2014

From C/C plus plus Code to High-Performance Dataflow Circuits

Andrea Guerrieri, Paolo Ienne, Lana Josipovic

High-level synthesis (HLS) tools typically generate statically scheduled datapaths. Static scheduling implies that the resulting circuits have a hard time exploiting parallelism in code with potential memory dependences, with control dependences, or where performance is limited by long latency control decisions. In this work, we describe an HLS approach which generates dynamically scheduled, dataflow circuits out of imperative code. We detail a complete set of rules to transform a standard compiler intermediate representation into a high-performance dataflow circuit that is able to dynamically resolve memory dependences and adapt its behavior on the fly to particular control flow decisions and operation latencies. Compared to a traditional HLS tool, the result is a different tradeoff between performance and circuit complexity: statically scheduled circuits display the best performance per cost in regular applications, but general-purpose, irregular, and control-dominated computing tasks require the runtime flexibility of dynamic scheduling. Therefore, enabling dynamic behavior in HLS is key to dealing with the increasing computational demands of new contexts and broader application domains.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Based on the original combination of picosecond acoustics and diamond anvils cell, recent improvements to accurately measure hypersonic sound velocities of liquids and solids under extreme conditions are described. To illustrate the capability of this technique, results are given on the pressure and temperature dependence of acoustic properties for three prototypical cases: polycrystal (iron), single-crystal (silicon) and liquid (mercury) samples. It is shown that such technique also enables the determination of the density as a function of pressure for liquids, of the complete set of elastic constants for single crystals, and of the melting curve for any kind of material. High pressure ultrafast acoustic spectroscopy technique clearly opens opportunities to measure thermodynamical properties under previously unattainable extreme conditions. Beyond physics, this state-of-the-art experiment would thus be useful in many other fields such as nonlinear acoustics, oceanography, petrology, in of view. A brief description of new developments and future directions of works conclude the article. (C) 2014 Elsevier B.V. All rights reserved.

Elsevier Science Bv2014