Skip to content

And-inverter graph

A directed acyclic representation of Boolean logic using two-input AND nodes and optional edge inversions.

Version
v2 · 2026-09-19 · History
Domain-specific #
3289
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomain
Logic Synthesis → Computer Science & Software Engineering
Aliases
AIG

Core Idea

Variables and constants form terminals, conjunction forms internal nodes and complemented edges encode negation, providing a structurally simple basis for scalable rewriting, hashing and verification. Arbitrary gates are decomposed into AND and NOT, common subexpressions share graph nodes and local equivalence-preserving rewrites optimize structure while outputs reference selected nodes or complements. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Both-Yes and Flip Blocks

Computers decide things with tiny switches. An and-inverter graph builds every decision out of just two kinds of pieces: a 'both' piece that says yes only when both of its inputs say yes, and a 'flip' that turns yes into no and no into yes. If two parts would do the exact same job, they share one piece instead of building it twice.

AND-and-NOT Circuit Map

Computer chips answer yes/no (true/false) questions using logic. An and-inverter graph is a way to draw any such logic using only two pieces: AND boxes, which have two inputs and say 'true' only if both inputs are true, and a 'NOT' mark on a connecting line, which flips true to false. Any logic gate can be rebuilt from these. If the same piece of logic is needed twice, the drawing shares one box instead of making two. Because everything is made of the same simple parts, computers can quickly shrink, check, and compare these drawings.

AND-plus-NOT Logic Graph

An And-inverter graph (AIG) represents a Boolean function as a directed acyclic graph. The inputs are variables and constants; every internal node is a two-input AND; and negation is not a separate node but a mark on an edge, called a complemented edge. Outputs point to chosen nodes, possibly complemented. Any logic gate can be rewritten in terms of AND and NOT, so any circuit can be expressed this way. Identical subexpressions are merged into one shared node (structural hashing), and small local rewrites that keep the function the same are used to make the graph smaller or shallower. This uniform, simple structure is why AIGs are popular for logic optimization and for checking whether two circuits are equivalent.

 

An and-inverter graph is a DAG representation of Boolean functions over a set of input variables: terminals are primary inputs and constants, every internal node computes the conjunction of exactly two fanins, and negation is encoded by complement attributes on edges. Arbitrary gates are decomposed into this AND/NOT basis. Structural hashing ensures that a node with a given pair of (possibly complemented) fanins exists only once, so common subexpressions are shared. Local, function-preserving rewrites restructure subgraphs to reduce node count (size) or logic levels (depth), and outputs reference selected nodes or their complements. Nodes have a topological order, and this uniform structure makes scalable rewriting and equivalence verification practical. The concept is specific: it requires the two-input AND semantics, the complemented-edge convention, and the explicit input/output and metric definitions, not just any logic network.

Scope of Application

And-inverter graph belongs to logic synthesis and is useful where the analyst can specify the typed logic synthesis carrier, including its objects, relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics are explicit. The scope is broad within that domain but bounded by the need for the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics are explicit.

Clarity

The abstraction clarifies a crowded vocabulary by making the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to And-inverter graph. And-inverter graph compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning

  1. Identify the carrier. State what the elements, states, objects, or observations are: the typed logic synthesis carrier, including its objects, relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
  2. Lock the constitutive rule. Express the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics are explicit independently of one notation or implementation.

Knowledge Transfer

Knowledge transfers strongly among subfields of logic synthesis because they reuse the typed logic synthesis carrier, including its objects, relations, parameters, conventions, evidence, boundary cases, and comparison targets, Arbitrary gates are decomposed into AND and NOT, common subexpressions share graph nodes and local equivalence-preserving rewrites optimize structure while outputs reference selected nodes or complements., and type the carrier, state every parameter and convention in the definition, test that the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions

Local relationship map for And-inverter graphParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.And-inverter graphDOMAINPrime abstraction: Composition — is a kind ofCompositionPRIME

Current abstraction And-inverter graph Domain-specific

Parents (1) — outgoing typed relations

  • And-inverter graph is a kind of Composition Prime

    It remains its own entry because its identity is fixed by the Boolean function and input variables, DAG nodes and topological order, two-input AND semantics, complemented-edge convention, constants and outputs, structural hashing, equivalence and size or depth metrics.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

And-inverter graph sits in a crowded region of the domain-specific corpus (8th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Formal Logic & Computation Systems (24 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25