7. Decomposition trees

Decomposition Trees

We can represent complicated expressions, like formulas of propositional logic and arithmetical expressions using rooted trees.

For example we can represent the formula $(\neg (p\wedge q)⟺(\neg p\vee \neg q))$ as:

graph G {
	graph [nodesep="0.6"]
	node[shape=plain]
 
	r[label="↔"]
	1[label="¬"]
	2[label="∧"]
	3[label="p"]
	4[label="q"]
	5[label="∨"]
	6[label="¬"]
	7[label="¬"]
	8[label="q"]
	9[label="p"]	
	
	r--1,5
	1--2
	2--3,4
 
	5--6,7
	6--9
	7--8
}

Notice subgraphs here represent parts of the equation:

graph G {
	graph [nodesep="1"]
	node[shape=plain]
 
	r[label="↔"]
	1[label="¬"]
	2[label="∧"]
	3[label="p"]
	4[label="q"]
	5[label="∨"]
	6[label="¬"]
	7[label="¬"]
	8[label="q"]
	9[label="p"]	
	
	r--1,5
	
	subgraph cluster0 {
		label="¬(p∧q)"
		1--2
		
		subgraph cluster2 {
			label="p∧q"
			2--3,4
		}
	}
	
	subgraph cluster1 {
		label="¬p∨¬q"
		5--6,7
		
		subgraph cluster3 {
			label="¬p"
			6--9
		}
		
		subgraph cluster4 {
			label="¬q"
			7--8
		}
	}
}