Venn Diagram, Universal Sets, Subsets, and Power Sets

Posted on by

In the previous article, you learned about the basic type of sets and its notations. In this article, I am going to discuss about Venn diagram, and some other types of sets. These sets are different from what I have discussed in my previous post, which was about equal sets, equivalent set and empty sets etc.

Venn Diagrams

Venn diagram is a graphical representation of sets. All sets come from a universe, called the universal set and represented by the letter $U$ . This universal set contains all the elements with common attributes
that we want to study.

population of a country,
students in a university,

can belong to a universal set, and then we can create sets from the universal set. If students from university belong to our Universal set, then we can have a set of students studying computer science or mathematics. In Venn diagram,

Figure 1 - Venn diagram with single set A and an element a — Figure 1 – Venn diagram with single set A and an element a

the universal set is a rectangle and sets are circles, that may or may not overlap each other. We will come back to that later.

For example, at the beginning, the elements are part of universal set $U$ , and when you make a set then they belong to the set if they have the property to be member of the set.

Example #1

Suppose $N$ is the set of natural numbers, and it’s our universe. To show the natural number set using Venn diagram, we will make a rectangle.

Figure 2 - Natural number set as the Universal set. — Figure 2 – Natural number set as the Universal set.

Let $A$ be a set of all even numbers less than 11.

\begin{aligned}&A = \{ 2, 4, 6, 8, 10 \}\end{aligned}

We did not add zero because Natural numbers start from 1.

N = \{1,2,3, \cdots \}

Now draw a circle inside the rectangle and show all even numbers within the circle. This is the Venn diagram representation of a set with elements. All numbers that are not shown in circle are in the Uniserve $U$ .

Figure 2 - Set A with even elements less than 11 within Natural number set N. — Figure 2 – Set A with even elements less than 11 within Natural number set N.

Example #2

Let’s take another example, Let $X$ and $Y$ be two sets with elements.

\begin{aligned} &X = \{ 2, 5, 6\}\\\\ &Y = \{4, 5, 9\} \end{aligned}

If we construct these two sets using Venn diagram, the circles that represent these two sets are overlapping, it is because they have a common element 5. The elements are shown as dots in Venn diagram.

The Venn diagrams are useful in visualizing the set operations like union, intersection, set difference, etc. We will explore the set operations in future lessons.

Subsets of a Set

Let us talk about subsets. Let there be two sets $A$ and $B$ .

Definition: The set $A$ is subset of set $B$ if and only if every single element of set $A$ is also an element of set $B$ .

We can also write this in equation form.

\begin{aligned} &A \subseteq B = \forall x\{a \in A \implies x \in B\}\end{aligned}

For sets that are not subsets is denoted as

\begin{aligned} &A \nsubseteq B = \forall x\{x \in A \implies x \notin B\} \end{aligned}

Venn Diagram Representation of Subsets

Here is a Venn diagram representation of subset. Since, $A$ is subset of $B$ , it is inside of the bigger circle representing set $B$ .

Figure 3 - Venn diagram of a subset where A is subset of B. — Figure 3 – Venn diagram of a subset where A is subset of B.

When we talk of subsets, there is a theorem:

If A is a set, it is guaranteed that it has at least two subsets:

1. Empty set - empty set is subset of all sets.
2. The set itself - the set automatically becomes subset of itself because it is all the elements.

Proving Equal Sets Using Subsets

This brings an interesting problem. If you remember that equal sets are two sets with same elements. If X and Y are two equal sets with same elements. Then we can prove that they are equal if we can show that they are subsets of each other.

So Let A be set of all odd numbers less than 10. and B is set with members { 1, 3, 5, 7}.

First, empty set is member of both sets. Second, all elements in set A are also in set B, and all elements of set B are in set A. Therefore, they are subsets of each other and equal.

Proper Subsets

Now we talk about proper subsets. A is proper subset of B such that all elements of A are in B , but some elements from B are not in A. It can written in logical form as .

“Forall x{ x in A implies that X in B}
and forsome x {x in B and x not in A}”

The proper subset is denoted as A proper subset of B.

Venn Diagram Of Proper Subsets

The Venn diagram of proper subset will look like this, for some set A and B. Now the question comes to our mind. How many subsets can we make from a given set ?

Power Set of a Set

This kind of set which contains only subsets of a set is called its power set. If set A is an ordinary set with 3 elements, then power set of A is denoted as P(A) and the number of subsets in a power set is 2^n. In our case,
set A has 3 elements, therefore, it has 2^3 = 8 subsets.

The power set of set A look like this and it has two guaranteed subsets, empty set and itself as members.

Disjoint Sets

Two sets that are not related at all, it means they don’t have any common elements are called the disjoint sets.
It is opposite of subsets. If we drew the venn diagram of disjoint set, then it will look like two separete circles away from each other. It is because their elements are different.

Super Sets

Finally, let us talk about supersets. If set A has all the elements of set B then set A is super set of set B.” It is denoted as A super set of B.

Proper super set is when A is super set of B, but A is not equal to B, there are some elements that are only available in set A.

Let A be a finite set with elements { 1, 3, 8, 7, 4} and B be set with elements { 3, 7}. Then A is super set of B
because it has all the elements of set B. It is also a proper super set because set A is not equal to set B.

If we draw Venn diagram for set A and set B, it look similar to the Venn diagram of subsets where B is subset of A.

Properties of Super Sets

Here are some properties of super sets.

Every set is a super set of empty set because empty set has no elements in it. Also empty set is member of every set.
If B is subset of A, it means that A is the super set of set B. Therefore, we can say that super sets are opposite of subsets. This is the reason, their Venn diagram look similar, however, set description is different.

Summary

Let us review things you learnt in this article.

First you learnt the basics of Venn diagram and know how to represent sets and universal sets.
Next you have understood the universal set as bigger set from which you get other sets.
You learnt about subset that contains elements from other set.
You know about proper subsets which are similar to subsets but contains less elements that its super sets.
Power set is a set of subsets
disjoint sets are two unrelated sets.
and finally, super sets that has all the element from its subsets.

Types of Basic Sets

Posted on by

In the previous article, you learnt about set notations – the roster notation and the set builder notation. In this article, I will discuss about the types of sets available. This is part 1 where we see basic types of sets and in part 2, I will discuss some derived types.

Set Types

The sets are collections of objects with some properties, but not all sets are same. Mathematicians have identified that certain sets have special properties and named them accordingly.

We have different type of sets, listed here.

equal set
equivalent set
empty set
singleton set

let us understand each of these set type. Also, I am giving examples of each set type so that it is easy to understand. For more examples, you can refer to some math books.

Equal Sets

We can define the equal set informally as

” Two sets are equal if and only if they have the same elements.”

If $A$ and $B$ are two equal sets, elements are set $A$ are in $B$ and elements of set $B$ is in set $A$ . It means $A$ and $B$ are equal sets, if and only if

\begin{aligned} \forall x ( x \in A \iff x \in B) \end{aligned}

$\forall$ (For all) is a universal quantifier, which is considering all elements from a set or universe. The symbol ( $\iff$ ) is biconditional, meaning $x \in A$ is only true if $x$ is also in $B$ or $x \in B$ is only true when $x$ is in $A$ .

To represent an equal set, we write

A = B

For example, Let $A$ be set $\{3, 6, 2\}$ .

A = \{3, 6, 2\}

and $B$ be set $\{6, 2, 3\}$ .

B = \{6, 2, 3\}

Both $A$ and $B$ are equal ( $A = B$ ), since, they have the same elements. Here order of elements does not matter.

Equivalent sets

The equivalent set is defined as:

“Two or more set are equivalent if their cardinality is same”.

Here cardinality is simply meaning number of elements and shown as a function of set.

Therefore,

If $A$ and $B$ are two sets then they are equivalent if and only if

n(A) = n(B)

For example, let $A , B, C ,$ and $D$ are $4$ sets.

\begin{aligned} &A = \{ 3, 1, 7\}\\ &B = \{p, q , r\}\\ &C = {4, 3, 2, 8, 9}\\ &D = {1, x, 3, y, 8} \end{aligned}

The elements of set $A$ are $3, 1 , 7$ which are numbers. and elements of set $B$ are $p, q,$ and $r$ which is alphabets. The elements of set $C$ are numbers and elements of set $D$ are both numbers and alphabets.

First, we determine the cardinality of sets – $A, B, C$ and $D$ using the cardinality function.

\begin{aligned} &n(A) = 3 \\ &n(B) = 3 \\ &n(C) = 5 \\ &n(D) = 5 \\ \end{aligned}

The cardinality of set $A$ and set $B$ is $3$ , so they are equivalent sets. The cardinality of set $C$ and Set $D$ is $5$ , so they are another equivalent set.
Note that the elements don’t have to be same. Set with different types of elements can be equivalent.

Comparison between equal and Equivalent set

Let us compare between equal sets and equivalent sets.

Two or sets have same elements, so they can be equal and equivalent at the same time.
For equivalent sets, the elements does not matter, only cardinality is important, whereas equal sets consider elements also.
order of elements in both equal and equivalent sets does not matter.
empty sets are always equivalent to each other.

When two sets have same element, they are equal set which we know already, but they have the same cardinality also. For instance,

\begin{aligned} &A = \{2, 5 , 7\}\\ &B = \{5, 2, 7\} \end{aligned}

The set $A$ and $B$ are same, hence, equal sets. If we check the cardinality of both sets, then

n(A) = 3\\n(B) = 3

It means that the number of elements is also same for both functions.

Another thing to notice in set $A$ and set $B$ is that order of elements is different. The order of elements is does not matter in equal sets. Also, it does matter how the elements are arranged when we are only concerned with number of elements of the set. Therefore, equivalent sets are also not affected by the order of elements in a set.

Empty sets

The empty sets are sets with no elements. They are denoted with $\{ \}$ or $\varnothing$ . Sometimes a set is described in terms of properties. For example,

Set of months in a year.

If the set property is such that there is no element exists is also empty.

For example,

A set of numbers with $x+1 < x$ , it is not possible, so such a set contains no element, and it is an empty set. It is also called the null set.

The empty set is this symbol $\varnothing$ and this $\{ \varnothing \}$ is a set that contains empty set.

Singleton Set

A singleton set is a set with only one element.

For example,

Set of even prime, $P$ is only one element $2$ .

Figure 1 - Set of even prime is a property with only one element which is 2. — Figure 1 – Set of even prime is a property with only one element which is 2.

Other examples of singleton sets are :

\begin{aligned} &Set \hspace{3px} A = \{ 0 \}\\ &or \\ &Set \hspace{3px} B = \{ x \in \mathbb{Z} \mid x + 4 = 0 \} \end{aligned}

Where $x$ can be only one number which is $-4$ in set $B$ .

Finite Sets

All of the previous set types have one thing in common, which is, the number of elements is limited or countable. A set with limited element is called a finite set. There is no special symbol to denote a finite set.

But, when you use roster notation, then you can list all the elements of the set. In other words, roster method is most suitable way to show a finite set.

For example, the set of all number less than $30$ perfectly divisible by number $5$ are:

\begin{aligned} S = \{ 5, 10, 15, 20, 25 \} \end{aligned}

Note, how set builder notion is very descriptive and long while describing a set of finite elements. That’s why a roster method is best choice for represent finite sets.

What happens when the set has infinite number of elements ?

Infinite Sets

A set with infinite number of elements is known as infinite set. It this set elements are many, to roster method is not a suitable method to represent the set.

Consider an example,

N = \{Set \hspace{3px} of \hspace {3px} natural \hspace{ 3px} numbers \}

The natural numbers are infinite and uncountable set. If that is the case, then describing the natural number set using set builder notation is suitable option.

It does not mean that infinite sets cannot be showed as using roster notation. But you must use the $(\cdots)$ symbol to show that there are infinite number of elements in the set.

Therefore, the set of natural numbers can be represented as:

N = \{ 1, 2, 3, 4, \cdots \}

The set of integers grows continuously on both direction, which is negative and positive. Therefore, it is shown as:

Z = \{ \cdots, -3, -2, -1 , 0, 1, 2, 3 , \cdots \}

There are several examples of infinite sets in mathematics. You will learn those in future articles.

Summary

You learnt that the sets are broadly finite or infinite sets. Depending on element in the sets. So a two sets can be equal or equivalent depending on number and type of elements in them. There are empty or singleton sets with no or one element respectively.

Introduction To Sets

Posted on by

In this article, I will introduce you to sets and its notations. There are many definitions for sets. But no one single definition is acceptable. So, I will start with a simple informal definition of a set.

“A set is group of objects with some properties and sometimes the object from same group does not share same properties”.

Figure 1 - Set A is a set of students from a school. — Figure 1 – Set A is a set of students from a school.

Suppose $A$ is a set of students from a school. Students in school are a in a set, but all students do not study same course. Some study math and other study programming and so on. In other words, they have different properties.

Figure 2 - Set of fruits with different tastes and colors — Figure 2 – Set of fruits with different tastes and colors

Let $B$ be a set of fruits: it has ${apple, oranges, banana}$ and all fruits have different taste and color.

What is the definition of set?

The formal definition of a set is:

A set is an unordered collection of objects called its members or elements. A set contains elements or members.

Here unordered is important and we will come back to it later. If an element belongs to a set, then we write $a \in A$ which means element ‘a’ is in set A.

Figure 3 - Element a is in set A is shown with the "in" operator. — Figure 3 – Element a is in set A is shown with the “in” operator.

If an element does not belong to a set, we write $a \notin A$ which means that element ‘a’ is not in set A.

Figure 4 - Symbol to indicate that element a is not in set A. — Figure 4 – Symbol to indicate that element a is not in set A.

Set Notations

There are two ways to describe a set.

Roster notation
Set builder notation.

Roster notation

In roster method, you simply list all the elements of a set within braces. If $A$ is a set of soft drinks, then list all the elements inside curly braces, separated with a comma. You have already seen an example above.

The roster method works when you have limited elements in a set. In other words you can count the number of elements in a set.

Set Builder Notation

When the size of set is too large, and you are not able to list the element, use the set builder notation. You are simple creating a rule for the elements of a set.

For example:

Suppose $N$ is set of all numbers less than $100$ , then you write this in set builder notation within curly braces like this.

A = {x \in N \mid x < 100}

Figure 6 - Set builder notation — Figure 6 – Set builder notation

Note that we wrote $N$ as a set, not $A$ because $N$ is set of natural numbers from which we got elements of $A$ . Sometimes elements of a set come from a bigger group called its Universe.

Logical Equivalence – Identity Law

Posted on by

Earlier you learned about the logical equivalence and how two or more compound prepositions makes a tautology and prove their equivalence.

There are many well-known $logical \hspace{5px} equivalences$ , so first one is identity law. We call it law because the same logic is applied in $Boolean \hspace{5px} algebra$ which is another branch of mathematics, that studies and understand logic in terms of algebra. But that is out of scope for this article.

Duality

As I mentioned earlier in a previous article, that duality applies to logical equivalences. A logical equivalence is made of compound statements which has a dual. So, every equivalence has a dual obtain by changing the connectives and $true$ to $false$ or $false$ to true if any.

\begin{aligned} &P \wedge Q \vee T \\\\ &Dual \hspace{5px} is \\\\ &P \vee Q \wedge F \end{aligned}

Understanding The Identity Law

Suppose $P$ is a statement “I ate breakfast” with some other true statement which we don’t know. The truth value of other statement is always $true$ , so we don’t need a variable for that, instead we call it $T$ which stands for $true$ .

\begin{aligned} &P \wedge T \equiv P\\ &P \vee F \equiv P \end{aligned}

In the first equivalence of identity law, when $P$ is $true$ , then both $P$ and the $other \hspace{5px} true \hspace{5px} statement$ gives $true$ which is same as $P$ becuase truth value of $P$ is $true$ .

If $P$ is $false$ , the compound statement $P \wedge T$ becomes $false$ which is same as $P$ . The equivalence is valid and a tautology.

The second equivalence states that $P \vee F$ is equivalent to $P$ . The $F$ stands for $false$ meaning we are referring to some statement which is always going to be false, and which is why we don’t use a variable.

If $P$ value is $true$ , output of compound statement $P \vee false$ is $true$ as per the working of disjunction, and equivalence holds.

If $P$ is $false$ , then compound statement $P$ or $false$ is $false$ and equivalent to $P$ .
The equivalence is true again.

Translating Identity Law To English

If we translate the identity law into English.

Watch on YouTube – Identity Law

P and True equivalent to P becomes
"I ate breakfast and Human being need food to survive"
is equivalent to saying "I ate breakfast".

P and True equivalent to P becomes
"I ate breakfast and Human being need food to survive"
is equivalent to saying "I ate breakfast".

The second statment does not need to be mentioned explicitly. It is always going to be true. Therefore, the equivalence is true regardless of second statement.

If I did not eat breakfast, the second statement does not make a difference. The equivalence is $true$ .

 (P or False) is equivalent to P can translate to "I at breakfast or I can survive without food and water" which is same as "I ate breakfast"

Similarly, and the false statement “I can survive without food and water” is irrelevant.

The second statement does not matter here because if I ate breakfast the compound statement $P \vee false$ is $true$ . It is same as saying “I ate breakfast”. The equivalence holds. Suppose “I did not eat breakfast”, even then the equivalence holds, and it is a tautology.

Truth Table For Identity Law

It would be easier to visualize Identity law with truth table. So first we make a truth table with 2 rows because the compound preposition has only one variable which is $P$ and other entity is either true or false.

$P$	$True$	$False$	$P \wedge T$	$P \vee F$
T	T	F	T	T
F	T	F	F	F

The column $P \wedge T$ and $P \vee F$ entries match with column $P$ which means the logical equivalence of identity law is valid and hence proved.

List of Logical Equivalences and Truth Tables

Posted on by

In this article, you will know the list of known logical equivalences and their corresponding truth table as a proof of them being a tautology. To understand more in-depth analysis of each of the identities, you can watch my YouTube channel.

Note that these logical identities are also found in Boolean algebra and each of the logical identity has its dual obtained by inverting the connectives and True or False if any.

Logical Equivalences with And, Or, Not

These are logical equivalence that use following connectives – conjunction, disjunction and negation.

Identity Laws

\begin{aligned} p \wedge T \equiv p\end{aligned}

$p$	T	$p \wedge T$
T	T	T
F	T	F

\begin{aligned}p \vee F \equiv p\end{aligned}

$p$	F	$p \vee F$
T	F	T
F	F	F

Domination Laws

\begin{aligned}p \vee T \equiv T\end{aligned}

$p$	T	$p \vee T$
T	T	T
F	T	T

\begin{aligned}p \wedge F \equiv F\end{aligned}

$p$	F	$p \wedge F$
T	F	F
F	F	F

Idempotent Laws

\begin{aligned}p \wedge p \equiv p\end{aligned}

$p$	$p \wedge p$
T	T
F	F

\begin{aligned} p \vee p \equiv p\end{aligned}

$p$	$p \vee p$
T	T
F	F

Double Negation Law

\begin{aligned}\neg (\neg p) \equiv p\end{aligned}

$p$	$\neg p$	$\neg(\neg p)$
T	F	T
F	T	F

Commutative Laws

\begin{aligned}p \wedge q \equiv q \wedge p\end{aligned}

$p$	$q$	$p \wedge q$	$q \wedge p$
T	T	T	T
T	F	F	F
F	T	F	F
F	F	F	F

\begin{aligned}p \vee q \equiv q \vee p\end{aligned}

$p$	$q$	$p \vee q$	$q \vee p$
T	T	T	T
T	F	T	T
F	T	T	T
F	F	F	F

Associative Laws

\begin{aligned}p \wedge (q \wedge r) \equiv (p \wedge q) \wedge r\end{aligned}

$p$	$q$	$r$	$q \wedge r$	$p \wedge (q \wedge r)$	$p \wedge q$	$(p \wedge q) \wedge r$
T	T	T	T	T	T	T
T	T	F	F	F	T	F
T	F	T	F	F	F	F
T	F	F	F	F	F	F
F	T	T	T	F	F	F
F	T	F	F	F	F	F
F	F	T	F	F	F	F
F	F	F	F	F	F	F

\begin{aligned}p \vee (q \vee r) \equiv (p \vee q) \vee r\end{aligned}

$p$	$q$	$r$	$q \vee r$	$p \vee (q \vee r)$	$p \vee q$	$(p \vee q) \vee r$
T	T	T	T	T	T	T
T	T	F	T	T	T	T
T	F	T	T	T	T	T
T	F	F	F	T	T	T
F	T	T	T	T	T	T
F	T	F	T	T	T	T
F	F	T	T	T	F	T
F	F	F	F	F	F	F

Distributive Laws

\begin{aligned} p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\end{aligned}

$p$	$q$	$r$	$q \vee r$	$p \wedge (q \vee r)$	$p \wedge q$	$p \wedge r$	$(p \wedge q) \vee (p \wedge r)$
T	T	T	T	T	T	T	T
T	T	F	T	T	T	F	T
T	F	T	T	T	F	T	T
T	F	F	F	F	F	F	F
F	T	T	T	F	F	F	F
F	T	F	T	F	F	F	F
F	F	T	F	F	F	F	F
F	F	F	F	F	F	F	F

\begin{aligned} p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\end{aligned}

$p$	$q$	$r$	$q \wedge r$	$p \vee (q \wedge r)$	$p \vee q$	$p \vee r$	$(p \vee q) \wedge (p \vee r)$
T	T	T	T	T	T	T	T
T	T	F	F	T	T	T	T
T	F	T	F	T	T	T	T
T	F	F	F	T	T	T	T
F	T	T	T	T	T	T	T
F	T	F	F	F	T	F	F
F	F	T	F	F	F	T	F
F	F	F	F	F	F	F	F

Absorption Laws

\begin{aligned} p \wedge (p \vee q) \equiv p\end{aligned}

$p$	$q$	$p \vee q$	$p \wedge (p \vee q)$
T	T	T	T
T	F	T	T
F	T	T	F
F	F	F	F

\begin{aligned} p \vee (p \wedge q) \equiv p\end{aligned}

$p$	$q$	$p \wedge q$	$p \vee (p \wedge q)$
T	T	T	T
T	F	F	T
F	T	F	F
F	F	F	F

Negation Laws

\begin{aligned}p \wedge \neg p \equiv F\end{aligned}

$p$	$\neg p$	$p \wedge \neg p$	F
T	F	F	F
F	T	F	F

\begin{aligned}p \vee \neg p \equiv T\end{aligned}

$p$	$\neg p$	$p \vee \neg p$	T
T	F	T	T
F	T	T	T

De Morgan’s Laws

\begin{aligned}\neg(p \wedge q) \equiv \neg p \vee \neg q\end{aligned}

$p$	$q$	$\neg p$	$\neg q$	$(p \wedge q)$	$\neg (p \wedge q)$	$\neg p \vee \neg q$
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

\begin{aligned}\neg(p \vee q) \equiv \neg p \wedge \neg q\end{aligned}

$p$	$q$	$\neg p$	$\neg q$	$(p \vee q)$	$\neg (p \vee q)$	$\neg p \wedge \neg q$
T	T	F	F	T	F	F
T	F	F	T	T	F	F
F	T	T	F	T	F	F
F	F	T	T	F	T	T

Prepositional Logic – Duality

Posted on by

We know that the simple statements are represented as p, q and so on. Suppose we are given a compound preposition.

$p \land q$

There is another property of compound prepositions called the duality; Therefore, the dual of above statement is

$p \lor q$

The dual can be achieved by interchanging $\land$ by $\lor$ or interchanging $\lor$ by $\land$ . This means $\land$ and $\lor$ is dual of each other.

Dual For Another Type Of Statement

We will see an example of another type of prepositional statement in which we use True or False directly instead of a variable.

For example,



is a preposition with T or True as one of the variable.

The dual of such a statement can be obtained by interchanging $\lor$ by $\land$ and interchanging True with False or False with True.

Each of the statement can be derived from the other.

Understanding Duality Using Truth Tables

These are the truth tables for the statements – $p \land q$ and $p \lor q$ .

If we change the operator for $p \land q$ with $p \lor q$ , or vice-versa, we get dual of each other. The truth table validates this claim. We can check this for other prepositional statements also.

Finite Probability

Posted on by

Finite Probability is a very important concept in discrete mathematics. Before we begin let’s understand some basic terminology, that is important in understanding probability theory.

Basic Terminologies

Experiment

An experiment is some task you do and get an outcome, possibly from a set of different outcomes. Example, throwing a dice would result in a number between one to six.

THROW A DICE AND YOU GET A NUMBER

Sample Space

Sample space is all possible outcome an experiment. For example, throw a dice and you get the following outcomes.

Sample Space = { 1, 2, 3, 4, 5, 6 }

You cannot get more than the value of sample space.

Event

An event is a subset of sample space. It means desired outcomes from a set of sample space.

It is denoted in set notations as E ⊆ S. For example if you throw a dice, and a six to appear then it’s an event.

Probability is associated with the event and probability of an event is between 0 and 1. If a probability of an event is 1, then it is a certain event.

Probability of an event is denoted as P(E) and 0 < = P(E) <= 1.

Favorable Outcome

When an event occur then it is a favorable outcome when it happens.

Unfavorable Outcome

When the event does not happen then it is an unfavorable outcome as it did not happen. Sometimes, we also need to find unfavorable outcomes of an event.

Equally likely

An event is equally likely if the probability of each outcome in sample space is equally likely.

For example, when we toss a coin we get either Head or Tail out of two outcomes of the sample space. So there is a 50-50 chance of getting a Head or Tail and both are equally likely events.

HEAD OR TAIL ARE EQUALLY LIKELY EVENTS

Formal Definition of Probability

If S is a finite non-empty sample space of equally likely outcomes and E is an event, that is, a subset of S, then the probability of E is

P(E) = |E| / |S|

Example Problem

Question :

A box contains 3 Red balls and 5 Green balls. What is the probability that a ball picked randomly from the box is Red?

Solution :

Total Number of Balls in Box = 3 + 5 = 8

Sample Space = 8

There are 3 ways to pick Red balls, Therefore, Event E = 3

P(E) = 3/8

The probability of picking a Red ball from the box is 3/8.

Logical Equivalence

Posted on by

We have seen prepositions, connectives and compound prepositions; all possible combinations of truth values of the individual prepositions in a compound preposition is depicted in a truth-table. However, it is possible that another preposition or compound preposition has the same truth values in the truth table. This is called logical equivalence of two prepositions.

The importance of logical equivalence is in simplifying complex logical expressions. This type of simplification is used in designing digital circuits . Learn digital logic that is the basis for computer system designs.

Watch on Youtube

Verifying Logical Equivalence using Truth-Table

As we mentioned earlier, the simplest way to verify logical equivalence of two preposition or compound preposition is to create a truth table and compare the output of each logical expression.

The number of variables used in the truth-table for each expression may be different, but we shall only take variables that are common to both the expressions.

Example #1

Suppose you are asked to verify the logical equivalence of following expressions.

p \implies q \equiv \neg p \vee q

The number of unique variables is $p, q$ . Therefore, our truth-table will contain $2^{2} = 4$ rows. The truth-table will contain truth values for all the expressions as given below.

$p$	$q$	$\neg p$	$p \implies q$	$\neg p \vee q$
$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$T$	$T$

Truth-table to verify logical equivalence : $p \implies q \equiv \neg p \vee q$

The above table clearly shows that the logically both expressions give the same truth value for all input combinations, that is, $p \implies q \equiv \neg p \vee q$ is equivalent. Let us see some more examples of logical equivalences.

Example #2

In the second example, we will try to prove the logical equivalence of biconditional connective using truth table.

p \iff q \equiv p \implies q \wedge q \implies p

There are exactly two unique variables in above expressions. Therefore, the truth-table will contain 4 rows.

$p$	$q$	$p \iff q$	$p \implies q$	$q \implies p$	$p \implies q \wedge q \implies p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$F$
$F$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$F$	$T$	$T$	$T$

Truth table for logical equivalence p<->q <=> p -> q and q -> p

The truth value for each row is same for both the expressions; therefore, both expressions are equivalent. There are several other logical expressions that we are going to explore in future lessons.

Prepositional Logic-Implication and Biconditional

Posted on by

In the previous video, you learned about different types of basic logical connectives that helps in creating compound prepositions. These connectives are join two or more atomic statements to form compound preposition which also have a truth value of its own.

We have discuss negation, conjunction, and disjunction connectives so far, the remaining two connectives are discussed in this article.

You can also watch our YouTube video on implication and biconditional.

Implication ( $\implies$ )

The implication connective takes one or more variables that represent atomic statements and make a compound statement. The implication is denoted with the $\implies$ symbol which means “implies” or “if…then..”.

In programming world, if-then is popularly known as conditional statement.

For example, Let  and  be two atomic statements. 

: "Today is Sunday"
: "I don't go to school"

Then  is "if p, then q" or "p implies q", 

: "If today is Sunday, then I don't go to school"

The statement $p$ is called antecedent or premise and the statement $q$ is called consequent or conclusion.

Other English Phrases That Represent If…Then..

There are several other ways to write implication in English, some of them are

q, if p
q, provided that p
q unless p
q follows from p
p sufficient condition or q
q necessary condition for p
because p, q
p therefore q

Translating English sentences to logic statements with variables may be tricky because there could be several meaning to same statement and we are not asserting a particular truth value to statement $p$ or $q$ .

It means that we are not saying that $p$ is true so that we have $q$ ; therefore, we want material implication which is weak and tentative in nature.

This could be understood with the help of truth table of implication.

Suppose $p$ is “You study hard” and $q$ stands for “You will pass the exam”. The $p\implies q$ is “If you study hard, then you will pass the exam”.

Let say $p$ is true, and $q$ is true as well, then $p \implies q$ is true. Similarly, $p$ is true and $q$ is false.

For the row 3 and row 4, we could not use $p \implies q$ as false because the table will look like truth table for $p \land q$ .

Suppose $p$ is false and means “You did not study”. The statement $q$ is false means “You did not pass the exam”; therefore, $p \implies q$ is true. We cannot have that truth table because it will match with the truth table of biconditional connective about which we will discuss later in the article.

The only case when connective is false is when $p$ is true, and $q$ is false. All other entries must be true in the truth table of material implication.

Read about “Paradoxes of Material Implication”.

Simplification of implication

Another way to write implication is to simplify it. The if-then $p \implies q$ is also written as $\neg p \lor q$ . This logical equivalence can be verified using following truth table.

Biconditional Operator ( $p \iff q$ )

The biconditional connective also takes one of more atomic statements and create a compound statement that has a truth value of its own. The biconditional is an “if and only if” or “iff” statement. The biconditional operator is denoted by $\iff$ .

For example if  and  are two logical atomic statements.

: "I am hungry" 

: "I worked very hard this morning" 

Then 

 : "I am hungry if and only if I worked very hard this morning"

Here is the truth table for biconditional connective.

From the truth table it is evident that when both the variables have same truth values – true or false. The compound preposition with a biconditional connective is true.

For example, let $p$ be the preposition “It is raining today” and $q$ be the statement “Peter will stay in house”. If both the statement is true, then whole statement is true, else both the statements are false then the statement is false.

The biconditional is implication that true from $p \implies q$ and $q \implies p$ . For example, consider the following statement.

 : "A polygon is a triangle" 

 : "A triangle has 3 sides" 

Using the biconditional we can make following statement.

"A polygon is a triangle if and only if it has 3 sides"

Condition for above statement are

If polygon is triangle then it has 3 sides ( $p \implies q$ )
If polygon has 3 sides, then it is a triangle ( $q \implies p$ )

Note that the both conditions we get and equivalent preposition for biconditional.

Let us verify the claim using a truth table.

logical equivalence of p<->q = p->q and q->p

From the truth table above, clearly, both expression are logically equal. Whenever you are asked to simplify a compound statements involving biconditionals, replace it with above expression for convenience.

Prepositional Logic – Negation of Statements

Posted on by

From the previous article, you know that a prepositional statement can have truth value and the values are boolean – true or false. A statement having true value can be negated using ‘not‘ operator and then its value becomes false or vice-versa.

Watch on YouTube

Consider the following example where variable p is the statement “I am eating“.

p: "I am eating" 

negation of p or : " It is not the case that I am eating" or simply "I am not eating"

You can write a negative statement but a true statement and negate it too. Let q be the statement “I am not eating”.

q: "I am not eating"

: "I am eating".

Given a compound preposition, a negation must be simplified first before any other logical operator. Its precedence is highest unless you have part of an expression enclosed in parenthesis.

1.  

2.

In the compound statement (1) there are two groups of parenthesis where first group $latex \neg (p \lor q) has a negation. Therefore, we must evaluate the first group and then second group of parenthesis.

The expression (2) has only one parenthesis that must be evaluated first because cannot simplify the not operator with one variable.

Truth Table for Negation

The negation operator is unary operator which give opposite results to a boolean value. The truth table gives all possible output for a given input combination and negation operator.

P	Not P
T	F
F	T

truth table for negation

Venn Diagrams

Example #1

Example #2

Subsets of a Set

Venn Diagram Representation of Subsets

Proving Equal Sets Using Subsets

Proper Subsets

Venn Diagram Of Proper Subsets

Power Set of a Set

Disjoint Sets

Super Sets

Properties of Super Sets

Summary

Set Types

Equal Sets

Equivalent sets

Comparison between equal and Equivalent set

Empty sets

Singleton Set

Finite Sets

Infinite Sets

Summary

What is the definition of set?

Set Notations

Roster notation

Set Builder Notation

Duality

Understanding The Identity Law

Translating Identity Law To English

Truth Table For Identity Law

Logical Equivalences with And, Or, Not

Dual For Another Type Of Statement

Understanding Duality Using Truth Tables

Basic Terminologies

Experiment

Sample Space

Event

Favorable Outcome

Unfavorable Outcome

Equally likely

Formal Definition of Probability

Example Problem

Verifying Logical Equivalence using Truth-Table

Implication ( )

Biconditional Operator ( )

Truth Table for Negation

Implication ( $\implies$ )

Biconditional Operator ( $p \iff q$ )