BooleanGraph
BooleanGraph[bfunc,g1,…,gn]
gives the Boolean graph defined by the Boolean function bfunc on the graphs g1, …, gn.
Details and Options
- The Boolean graph has a vertex list given by the union of vertex lists.
- An edge uv is in the resulting graph if bfunc[EdgeQ[g1,uv],…,EdgeQ[gn,uv]] is True.
- An edge uv is in the resulting graph if bfunc[EdgeQ[gi,uv],…,EdgeQ[gn,uv]] is True.
- GraphUnion[g1,g2] is equivalent to BooleanGraph[Or,g1,g2].
- GraphIntersection[g1,g2] is equivalent to BooleanGraph[And,g1,g2].
- GraphDifference[g1,g2] is equivalent to BooleanGraph[#1∧¬#2&,g1,g2].
- BooleanGraph works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
Examples
open all close allBasic Examples (1)
Scope (5)
BooleanGraph works with undirected graphs:
BooleanGraph[And, [image], [image]]BooleanGraph[Or, [image], [image]]BooleanGraph works with as many graphs as the Boolean function:
BooleanGraph[Or, [image], [image], [image]]BooleanGraph[And, [image], [image]]BooleanGraph[Or, [image], [image]]Applications (4)
Define the symmetric graph difference Xor:
{g1 = RandomGraph[{20, 30}], g2 = RandomGraph[{20, 30}]}Convert the Boolean expression Xor to disjunctive normal form:
BooleanConvert[Xor[x, y]]Implement it by related functions:
GraphUnion[GraphIntersection[g1, GraphComplement[g2]], GraphIntersection[g2, GraphComplement[g1]]]Compare to the result by using Xor directly:
IsomorphicGraphQ[%, SimpleGraph[BooleanGraph[Xor, g1, g2]]]Define the graph Nand:
{g1 = RandomGraph[{20, 30}], g2 = RandomGraph[{20, 30}]}Convert the Boolean expression Nand to disjunctive normal form:
BooleanConvert[Nand[x, y]]Implement it by related functions:
GraphUnion[GraphComplement[g2], GraphComplement[g1]]Compare to the result by using Nand directly:
IsomorphicGraphQ[%, SimpleGraph[BooleanGraph[Nand, g1, g2]]]Define the graph Nor:
{g1 = RandomGraph[{20, 30}], g2 = RandomGraph[{20, 30}]}Convert the Boolean expression Nor to disjunctive normal form:
BooleanConvert[Nor[x, y]]Implement it by related functions:
GraphIntersection[GraphComplement[g1], GraphComplement[g2]]Compare to the result by using Nor directly:
IsomorphicGraphQ[%, SimpleGraph[BooleanGraph[Nor, g1, g2]]]Compute the Boolean graph for all Boolean functions of two variables:
g1 = [image];g2 = [image];vc = AbsoluteOptions[g1, VertexCoordinates];Use BooleanFunction to enumerate all Boolean functions of two variables:
Table[TraditionalForm@BooleanFunction[i, {x, y}], {i, 0, 2 ^ 2 ^ 2 - 1}]Compute the Boolean graph using these functions:
Table[Tooltip[BooleanGraph[BooleanFunction[i, 2], g1, g2, vc, PlotLabel -> i], TraditionalForm@BooleanFunction[i, {x, y}]], {i, 0, 15}]Properties & Relations (3)
GraphUnion corresponds to Or:
{g1, g2} = {[image], [image]};IsomorphicGraphQ[BooleanGraph[Or, g1, g2], GraphUnion[g1, g2]]GraphIntersection corresponds to And:
{g1, g2} = {[image], [image]};IsomorphicGraphQ[BooleanGraph[And, g1, g2], GraphIntersection[g1, g2]]BooleanGraph does not necessarily produce simple graphs:
BooleanGraph[Not, [image]]Use SimpleGraph if only a simple graph is needed:
SimpleGraph[%]Text
Wolfram Research (2010), BooleanGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/BooleanGraph.html (updated 2014).
CMS
Wolfram Language. 2010. "BooleanGraph." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/BooleanGraph.html.
APA
Wolfram Language. (2010). BooleanGraph. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/BooleanGraph.html