Namespaces
Variants
Actions

Difference between revisions of "Venn diagram"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (dots)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
A graphic representation of formulas of mathematical logic, mainly formulas of the [[Propositional calculus|propositional calculus]]. A Venn diagram of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965501.png" /> variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965502.png" /> of classical propositional logic is a selection of closed contours <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965503.png" /> (with homeomorphic circumferences) which subdivides the plane into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965504.png" /> domains, some of which (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965505.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965506.png" />) are marked. Each marked domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965507.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965508.png" />, is put into correspondence with the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v0965509.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655011.png" />, is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655012.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655013.png" /> lies within the contour <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655015.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655016.png" /> otherwise. The formula corresponding to the diagram as a whole is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655017.png" />. Thus, the Venn diagram in the figure corresponds to the formula
+
{{TEX|done}}
 +
A graphic representation of formulas of mathematical logic, mainly formulas of the [[Propositional calculus|propositional calculus]]. A Venn diagram of $n$ variables $a_1,\dotsc,a_n$ of classical propositional logic is a selection of closed contours $C_1,\dotsc,C_n$ (with homeomorphic circumferences) which subdivides the plane into $2^n$ domains, some of which (e.g. $v_1,\dotsc,v_k$, $0\leq k\leq2^n$) are marked. Each marked domain $v_i$, $0<i\leq k$, is put into correspondence with the formula $B_i=b_1\mathbin{\&}\dotsb\mathbin{\&}b_n$ where $b_j$, $0<j\leq n$, is $a_j$ if $v_i$ lies within the contour $C_j$ and $b_j$ is $\neg a_j$ otherwise. The formula corresponding to the diagram as a whole is $B_1\lor\dotsb\lor B_n$. Thus, the Venn diagram in the figure corresponds to the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655018.png" /></td> </tr></table>
+
$$(\neg a_1\mathbin{\&}\neg a_2\mathbin{\&}\neg a_3)\lor(a_1\mathbin{\&}\neg a_2\mathbin{\&}a_3)\lor(\neg a_1\mathbin{\&}a_2\mathbin{\&}\neg a_3).$$
  
If there are no marked domains (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655019.png" />), the diagram corresponds to an identically-false formula, e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096550/v09655020.png" />. In propositional logic, Venn diagrams are used to solve decision problems, the problem of deducing all possible pairwise non-equivalent logical consequences from given premises, etc. Propositional logic may be constructed as operations over Venn diagrams brought into correspondence with logical operations.
+
If there are no marked domains ($k=0$), the diagram corresponds to an identically-false formula, e.g. $a_1\mathbin{\&}\neg a_1$. In propositional logic, Venn diagrams are used to solve decision problems, the problem of deducing all possible pairwise non-equivalent logical consequences from given premises, etc. Propositional logic may be constructed as operations over Venn diagrams brought into correspondence with logical operations.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/v096550a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/v096550a.gif" />

Latest revision as of 12:22, 14 February 2020

A graphic representation of formulas of mathematical logic, mainly formulas of the propositional calculus. A Venn diagram of $n$ variables $a_1,\dotsc,a_n$ of classical propositional logic is a selection of closed contours $C_1,\dotsc,C_n$ (with homeomorphic circumferences) which subdivides the plane into $2^n$ domains, some of which (e.g. $v_1,\dotsc,v_k$, $0\leq k\leq2^n$) are marked. Each marked domain $v_i$, $0<i\leq k$, is put into correspondence with the formula $B_i=b_1\mathbin{\&}\dotsb\mathbin{\&}b_n$ where $b_j$, $0<j\leq n$, is $a_j$ if $v_i$ lies within the contour $C_j$ and $b_j$ is $\neg a_j$ otherwise. The formula corresponding to the diagram as a whole is $B_1\lor\dotsb\lor B_n$. Thus, the Venn diagram in the figure corresponds to the formula

$$(\neg a_1\mathbin{\&}\neg a_2\mathbin{\&}\neg a_3)\lor(a_1\mathbin{\&}\neg a_2\mathbin{\&}a_3)\lor(\neg a_1\mathbin{\&}a_2\mathbin{\&}\neg a_3).$$

If there are no marked domains ($k=0$), the diagram corresponds to an identically-false formula, e.g. $a_1\mathbin{\&}\neg a_1$. In propositional logic, Venn diagrams are used to solve decision problems, the problem of deducing all possible pairwise non-equivalent logical consequences from given premises, etc. Propositional logic may be constructed as operations over Venn diagrams brought into correspondence with logical operations.

Figure: v096550a

The apparatus of diagrams was proposed by J. Venn [1] to solve problems in the logic of classes. The method was then extended to the classical many-place predicate calculus. Venn diagrams are used in applications of mathematical logic and theory of automata, in particular in solving the problems of neural nets.

References

[1] J. Venn, "Symbolic logic" , London (1894)
[2] A.S. Kuzichev, "Venn diagrams" , Moscow (1968) (In Russian)


Comments

The idea of Venn diagrams goes back to L. Euler and they are sometimes also called Euler diagrams.

References

[a1] P. Suppes, "Introduction to logic" , v. Nostrand (1957) pp. §9.8
[a2] G. Birkhoff, S. MacLane, "A survey of modern algebra" , Macmillan (1953) pp. 336ff
[a3] B. Rosser, "Logic for mathematicians" , McGraw-Hill (1953) pp. 227–228; 237ff
How to Cite This Entry:
Venn diagram. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Venn_diagram&oldid=12932
This article was adapted from an original article by A.S. Kuzichev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article