Implication graph

Implication graph

In mathematical logic, an implication graph is a skew-symmetric directed graph "G"("V", "E") composed of vertex set "V" and directed edge set "E". Each vertex in "V" represents the truth status of a Boolean literal, and each directed edge "e"("u", "v") connecting vertex "u" and vertex "v" represents the implication "If the literal "u" is true then the literal "v" is also true". IGs were originally used for analyzing complex Boolean expressions.

A 2-satisfiability instance in conjunctive normal form can be transformed into an implication graph by replacing each of its disjunctions by a pair of implications. The instance is satisfiable if and only if no literal and its negation belong to the same strongly connected component of the implication graph; this characterization can be used to solve 2-satisfiability instances in linear time. [cite journal|author = Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E.|title = A linear-time algorithm for testing the truth of certain quantified boolean formulas|journal = Information Processing Letters | volume = 8 | issue = 3 | pages = 121–123|year = 1979|doi = 10.1016/0020-0190(79)90002-4]

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Skew-symmetric graph — In graph theory, a branch of mathematics, a skew symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges. The isomorphism is required to be an involution without any fixed… …   Wikipedia

  • Logical implication — In logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model (or interpretation or valuation) of T is also a model of B . In symbols,# T models B, # T Rightarrow B # T …   Wikipedia

  • Transpose graph — In the mathematical and algorithmic study of graph theory, the converse[1], transpose[2] or reverse[3] of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the… …   Wikipedia

  • Strongly connected component — Graph with strongly connected components marked A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a …   Wikipedia

  • 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia

  • Okun's law — Graph of US quarterly data (not annualized) from 1947 through 2002 estimates a form of the difference version of Okun s law: %Change GNP = .856 1.827*(Change Unemployment Rate). R^2 of .504. Differences from other results are partly due to… …   Wikipedia

  • Propositional calculus — In mathematical logic, a propositional calculus or logic (also called sentential calculus or sentential logic) is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules… …   Wikipedia

  • List of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • physical science, principles of — Introduction       the procedures and concepts employed by those who study the inorganic world.        physical science, like all the natural sciences, is concerned with describing and relating to one another those experiences of the surrounding… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”