---
title: Implication graph
slug: implication-graph
qid: 
snapshot: enwiki-001344282808
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1344282808
tags: [20279618, 20384058, 23603337, 26220375, 29176164, 29176295]
---

# Implication graph

> [!note] Provenance
> Snapshot `enwiki-001344282808` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1344282808> · Licensed CC BY-SA 4.0

In mathematical logic and graph theory, an implication graph is a skew-symmetric, directed graph composed of vertex set and directed edge set . Each vertex in represents the truth status of a Boolean literal, and each directed edge from vertex to vertex represents the material implication "If the literal is true then the literal is also true". Implication graphs were originally used for analyzing complex Boolean expressions.

In mathematical logic and graph theory, an implication graph is a skew-symmetric, directed graph composed of vertex set and directed edge set . Each vertex in represents the truth status of a Boolean literal, and each directed edge from vertex to vertex represents the material implication "If the literal is true then the literal is also true". Implication graphs were originally used for analyzing complex Boolean expressions. ==Applications== 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. For example, the statement (x_0\lor x_1) can be rewritten as (\neg x_0 \rightarrow x_1) , but (\neg x_1 \rightarrow x_0) also works. An instance is satisfiable if and only if no literal and its negation belong to the same strongly connected component of its implication graph; this characterization can be used to solve instances in linear time. In CDCL SAT-solvers, unit propagation can be naturally associated with an implication graph that captures all possible ways of deriving all implied literals from decision literals, which is then used for clause learning. ==References==
