Dear Qefsere,

a simple example is a graph model of mathematical logic - vertices are statements and directed arrows correspond to logical implications (a->b if a implies b).

I have read this paper "A CHARACTERIZATION OF HYPERCUBES" in which it is proved that. A hypercube is defined as the undirected Hassc diagram of a Boolean lattice.

And also the proposition: A directed graph D i'~ the ,t-lasse diagram of a partial order if and

only if the following holds:

Whenever there is an arrow a from a vertex x to a vertex y, 'a' is the only directed

path from x to y and there exists no directed path from y to x.

There are great answers here so far. The most obvious one is finite automata and state machines. They are all graphs in the end. All of these are logical structures can induce a language (a set of strings, for which will be accepted). Compilers use this material all the time.

Dear Qefsere,

I would like to mention connection between logic and HYPERgraphs. The connection is easy to understand you ыуу every hyperedge as an implication: the outcoming nodes make the premise, the incoming node is the conclusion. You can find much more in this paper: http://link.springer.com/chapter/10.1007/3-540-45757-7_53

Thank you Artem.

Dear Qefsere,

As is well known, set theory and two-valued classical logic are the two faces of the same "coin". Set theory can be develoed using "trees". Similarly classical logic can be developed using trees. For such a development see Colin Howson Logic with Trees: An Introduction to Symbolic Logic. Routledge, 1977. 

There are also non-well founded sets, which use pointed graphs. This set theory can be seen that it is essentially the Category of sets. In general a logic based on general graphs should be a variant of Categorical Logic.

Dear Qefsere and others,

nice to find out this discussion has not ended.

Costas is quite right - there are syntax-based graphs.

There is also a  way to assign a graph to any propositional logic formula. Google "Proofs without syntax" and "cographs".

A graph is nothing else as a binary relation over some (not necessarily finite) set. One makes a lot of model theory for graphs. An interesting example seems to me the infinite random graph, with the property that for all m and n, given any n + m elements , there is a vertex c in V that is adjacent to each of the n and is not adjacent to any of the m elements. All countable infinite random graphs are isomorphic, so this theory is complete. All finite graph is embeddable in this infinite random graph. Random Graphs have defined by Erdos and Reny. See also

http://en.wikipedia.org/wiki/Random_graph

Another connection between logic and graphs is about coloring, see Ramsey's Theorem.

More about the Rado graph, containing all finite (AND COUNTABLE!) Graphs as induced subgraphs, can be read here:

http://en.wikipedia.org/wiki/Rado_graph

The following paper introduces the development of a theorem prover (and its accompanying mathematical logic) for graph theory:

History of mathematical logic in Serbia:

http://www.site.uottawa.ca/~ivan/Logic%in%Serbia.pdf

Dear Jim, I think your link does not work!

Yeah, Dear Jim, the link doesnot work

Thank you  @Joachim..

http://www.site.uottawa.ca/~ivan/Logic%20in%20Serbia.pdf

Dear Joachim,

Many thanks for fixing the link!   A great help.

And Dear Prasanth and Costas, mwny thanks for pointing out the difficulty with the link in my previous post.

I am one of the coauthors of the paper: History of the Mathematical Logic in Serbia. You can go to my page on RG, find the paper and download it from there.

But that does not answer Qefsere's question.

Trees are special graphs and they are often used in mathematical logic. Terms and formulas are trees, there are proof systems with tableaux wich are also trees. Graphs are used heavily in Proof theory (go to the RG page of my colleague Zoran Petric for examples) etc. Conversly, you have theories of various classes of graphs as respective theories of particular types of (binary) relations.

Dear @Aleksandar,

Many thanks for joining the discussion.   Also, many thanks for mentioning the paper you coauthored: History of Mathematical Logic in Serbia:

https://www.researchgate.net/publication/260192584_History_of_Mathematical_Logic_in_Serbia?ev=prf_pub

The seminar on mathematical logic that grew out of the seminar on algebra and logic was truly fruitful, leading to more than 40 doctoral theses. 

In the section of General Proof Theory, you mention that Došen proposed the notion of the union of proofs and the notion of zero proofs.    If possible, please tell a bit about the union of proofs and zero proofs.

Chapter History of Mathematical Logic in Serbia

Its really great that a seminar on Mathematical Logic produced more than 40 doctoral theses.  usually these seminars gives us little, But this is so huge.  My appreciations

Thanks for nice words. That seminar was the 'kindergarden' for all of us starting in mathematical logic in Serbia. It was so important that people from Novi Sad (80km away) regularly attended. Still living and doing great job.

Unfortunately, I am not familiar with union of proofs. You can contact Zoran Petrić, he and Došen work together in Categorical Proof Theory.

There is a strong connection between graph theory and mathematical logic. Several graph theoretical concepts can be definable in terms of first order logic and second order logic. One can use also the first order axioms on Interval functions on to define and characterize several graph families.  

I have attached an unpublished paper that discusses one small point in the history of applications of graph theory in logic. You may find some of the references of interest. 

Thank you Professor Weaver.

Dear Madam,

Please check whether the following documents answers your questions.

http://www.automata.rwth-aachen.de/~grohe/pub/grokawree13.pdf

http://www.sciencedirect.com/science/article/pii/S0304397596807079

http://link.springer.com/chapter/10.1007%2F3-540-50728-0_53