Visualizing Propositions

Suppose that $P$ and $Q$ are two sets of objects. Relative to these two sets, any object can be classified in exactly one of the following 4 ways:

1. The object is neither in $P$ nor in $Q$.
2. The object is in $P$ but not in $Q$.
3. The object is in both $P$ and $Q$.
4. The object is in $Q$ but not in $P$.

A Venn diagram is a picture that represents all the possible relationships between sets of objects. For example, the picture below is a Venn diagram for $P$ and $Q$. The square represents all the possible objects, the circle labeled with $P$ are the objects in the set $P$, and the circle labeled with $Q$ are the objects in the set $Q$. The numbers refer to the above categories that describes the objects in the region.

There is an important connection between Venn diagrams and propositional logic. The key idea is that formulas of propositional logic describe regions of the Venn diagram: For all formulas $X$ and $Y$, the formula $\neg X$ refers to the region outside the the region described by $X$, the formula $X\wedge Y$ refers to the region described by both $X$ and $Y$, and the formula $X\vee Y$ refers to the regions described by either $X$ or $Y$. For example, in the image below, each of the 4 Venn diagrams is labeled with a formula describing the shaded region. Furthermore, each region can be associated with a row in a truth table for $P$ and $Q$.

Building on this idea, we can visualize other formulas of propositional logic constructed using the atomic propositions $P$ and $Q$ by shading different regions of the Venn diagram. Since there are 4 different regions of a Venn diagram for $P$ and $Q$, there are 16 different ways to shade the Venn diagram. The key observation is that any formula of propositional logic that only contains the atomic propositions $P$ or $Q$, describes one of the 16 possible shadings of the Venn diagram for $P$ and $Q$. The image below contains all 16 different shadings, each labeled with a formula that describes the shading.

The Venn diagram at the bottom of the image has no regions shaded, the 4 Venn diagrams in the 1st row have exactly 1 region shaded, the 6 Venn diagrams in the 2nd row have exactly 2 regions shaded, the 4 Venn diagrams in the 3rd row have exactly 3 regions shaded, and the Venn diagram at the top of the image have all 4 regions shaded. There is a line drawn from a Venn diagram to a Venn diagram immediately above it when all regions shaded in the Venn diagram below are also shaded in the Venn diagram above.

The above image is a very useful way to visualize important relationships between different formulas of propositional logic. There are three key observations:

1. Any formula of propositional logic that only contains the atomic propositions $P$ or $Q$ is tautologically equivalent to one of the formulas labelling a shading of the Venn diagram in the following image.
2. For all formulas $X$ and $Y$, if $X$ and $Y$ only contain the atomic propositions $P$ and $Q$, then $X\models Y$ whenever there is a path from a Venn diagram whose shading is described by $X$ to Venn diagram whose shading is described by $Y$.
3. For all formulas $X$, $Y$ and $Z$, if $X$, $Y$ and $Z$ only contain the atomic propositions $P$ and $Q$, then $X$ is tautologically equivalent to $Y\vee Z$ whenever there is a line drawn from both the Venn diagram whose shading is described by $Y$ and $Z$ to Venn diagram whose shading is described by $X$.

For example, the following facts:

• $P\wedge\neg P\models P$,
• $P\wedge\neg P\models P\wedge\neg Q$,
• $P\wedge\neg P\models P\wedge Q$,
• $P\wedge Q\models P$,
• $P\wedge\neg Q\models P$, and
• $P\approx (P\wedge Q)\vee (P\wedge \neg Q)$

are illustrated by the highlighted lines in the following image:

Tutorial

Lecture

Slides

Euler Diagrams

It is important to note that in a Venn diagram, not all of the regions must contain objects. For example, suppose that we are considering sets consisting of the ten digits: $0, 1, 2, 3, 4, 5, 6, 7, 8,$ or $9$. Suppose that $P$ is the first three digits. We express this by writing $\{0,1,2\}$. The braces "$\}$" and "$\{$" are used to denote a set of objects (in this case, a set of digits). Suppose that $Q$ is $\{0,1,2,3,4,5\}$. In the following Venn diagram for the sets $P$ and $Q$, I list the set of elements in each region.

Note that the symbol "$\varnothing$" is used to describe the region consisting of objects that are in $P$ but not in $Q$. This symbol means the empty set: That is, the set with no elements. Of course, there are no numbers in $P$ that are not in $Q$ since every number in $P$ is also in $Q$. In this case, it is more convenient to draw the $P$ circle completely inside the $Q$ circle to indicate that everything in $P$ is also in $Q$. When not all possible regions are depicted the diagrams are called Euler diagrams.

We can also use Euler diagrams to illustrate logical relationships between formulas of propositional logic. The idea is to treat a formula $X$ as the set of truth value functions that make the formula true. Then, $X\models Y$ means that every truth value function that is in the set of truth value functions making $X$ true is also in the set of truth value functions making $Y$ true.

Example

Draw an Euler diagram of two formulas $X$ and $Y$ when $X\models Y$:

Example

Draw an Euler diagram of two formulas $X$ and $Y$ that are mutually exclusive (i.e., there is no truth value assignment that make both formulas true):

Note that there may be a truth value function that makes neither $X$ nor $Y$ true.

Practice Questions

1. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $(A\vee B) \wedge C$.

2. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $(A\wedge C) \vee (B\wedge C)$.

3. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $(A\wedge B) \vee (A\wedge \neg B)$.

4. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $A\wedge (A\rightarrow C)$.

5. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $B\wedge (A\leftrightarrow C)$.

6. Suppose that there are three propositions $A$, $B$ and $C$. Draw a Venn diagram from these three prpositions and shade the region corresponding to $\neg (A\rightarrow (B\vee C))$.

7. Consider the following Venn diagram. What is a formula corresponding to the shaded region?

8. Consider the following Venn diagram. What is a formula corresponding to the shaded region?

9. Consider the following Venn diagram. What is a formula corresponding to the shaded region?

10. Draw a Euler diagram of two formulas $X$ and $Y$ where $X\not\models Y$ and $Y\not\models X$.

11. Draw a Euler diagram of three formulas $X$, $Y$, and $Z$ such that $X,Y\not\models Z$.

12. Draw a Euler diagram of three formulas $X$, $Y$, and $Z$ such that $X,Y\models Z$: