Prepositional Logic – Negation of Statements

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.

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

\begin{aligned}
&p: "I \hspace{5px}am \hspace{5px} eating" \\\\
&negation \hspace{5px} of \hspace{5px} p \hspace{5px} or \hspace{5px} \neg p: " It \hspace{5px} is \hspace{5px}not \hspace{5px} the\hspace{5px} case \hspace{5px}that \hspace{5px}I \hspace{5px}am \hspace{5px}eating." \\
&or \\
&"I \hspace{5px}am \hspace{5px}not \hspace{5px} eating"
\end{aligned}

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

\begin{aligned}
&q: "I \hspace{5px} am \hspace{5px} not \hspace{5px}eating"\\\\
&\neg q: "I \hspace{5px} am \hspace{5px}eating".
\end{aligned}

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.

\begin{aligned}
&1. \hspace{3px}\neg(p \lor q) \hspace{3px} and \hspace{3px} (q \lor \neg q)\\\\
&2. \hspace{3px}(p \lor p)\land \neg q
\end{aligned}

In the compound statement (1) there are two groups of parenthesis where first group 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.

Prepositional Logic – Simple Statements

Prepositional Logic is kind of logic that studies “Statements” and derives relationship among those statements.

What is a statement or a preposition ?

When we talk, we make many sentences, but all sentences are not . A sentence qualifies as a statement when it has a truth value. There is only two truth value for a statement – or .

For example,

What \hspace{5px}is \hspace{5px}your \hspace{5px}name?

The above sentence is a question, and we cannot give a truth value for this sentence. It is neither true nor false.

If someone reply to the question with an answer such as following

My \hspace{5px}name \hspace{5px} is \hspace{5px} Peter.

The above is an example of statement because it can be true or false.

Simple Preposition and Compound Preposition

Suppose there are two prepositions.

\begin{aligned}
&I \hspace{5px}am \hspace{5px} eating.\\
&I \hspace{5px}am \hspace{5px} sleeping.
\end{aligned}

Such individual statement is called simple prepositions and we do not need to write them every time. Instead, we can assign an alphabet to each of these statements.

\begin{aligned}
&p : I \hspace{5px} am \hspace{5px} eating.\\
&q:  I\hspace{5px}  am\hspace{5px}  sleeping.
\end{aligned}

We can also make complex statements using these simple prepositions. However, we need a logical connective to do that.

There are many logical connectives but the most common connectives are

\begin{aligned}
&and \hspace{5px} ( conjunction )\\
&or  \hspace{5px}  ( disjunction )
\end{aligned}

  and   are compound statements.

It means following

\begin{aligned}
&p \wedge q : I \hspace{5px} am \hspace{5px} eating \hspace{5px}and \hspace{5px}I \hspace{5px}am \hspace{5px}sleeping.\\
&p \vee q : I \hspace{5px}am \hspace{5px}eating \hspace{5px}or \hspace{5px}I \hspace{5px}am \hspace{5px}sleeping.
\end{aligned}

The truth value of the compound preposition depends on the individual simple preposition in the compound preposition.

In the above example, suppose truth value of p is true and q is false, then

\begin{aligned}
p \wedge q = true \wedge false = false
\end{aligned}

Similarly,

\begin{aligned}
p \vee q = true \vee false = true
\end{aligned}

We shall see more of these using a truth table in future lessons.

How to create a Hasse Diagram

Hasse Diagram is created for POSET or Partially Ordered Set. It means that there is a set of elements in which certain element are ordered, sequenced or arranged in some way. It is usually denoted as ≤, this is not “Less than, Equal to”, this symbol shows that elements are ordered.

Now, there is a relation among all the elements in the partial order set and it is some binary relation R, this relation must satisfy following properties

1. Reflexive
2. Anti-Symmetric
3. Transitive

Example Problem

Suppose (z, |) is a partial order set where | is division operator and a | b means “a divides b”.

Reflexive Property

a | a => a divides itself and this is correct with respect to division. A number can divide itself.

Anti-Symmetric Property

a | b = b | a is correct and works only when a = b. If not, then it is not anti-symmetric.

Transitive Property

a | b => a divides b means b = a * m where m is some number. (1)

b | c => b divides c means c = b * n  where n is some number.  (2)

Using (1) and (2) we get

c = (a * m) * n

c = a * (m * n) which is same as (1). This proves the transitivity property.

Hasse Diagram

Now that we know partial order set means and a Hasse Diagram is graphical representation of posets.

Rules for Hasse Diagram

1. If x < y, then in the graph x appears lower to y.
2. We draw line segment between x and y only if x cover y or y cover x, it means some order is maintained between them.

Consider an example

Let A be a set, A = { 1,  3,  5,  12,  15 }, relation between elements are a | b that is., a divides b.

 

Step 1

Due to the reflexive property all elements have direct edge to itself.

 

Hasse Diagram showing all relations

In this diagram, it shows the relations removed all the self-directing loops.

 

All Self-Directing Edges Removed

Step 2

The green lines shows transitivity, so we remove all the transitive lines. Out diagram look like the following.

Hasse Diagram without Transition and Loops

Step 3

Replace all the vertices with dots and directed edges with ordinary lines. This final diagram is called the Hasse Diagram of poset.

Hasse Diagram for A = { 1, 3, 5, 12, 15 } and relation a | b i.e., a divides b

Exercise

Here is an exercise for you to practice. The prerequisite for Hasse Diagram is to know how to represent relations using graphs.

Let A be a poset, A = { 2,  4,  6,  8 } and the relation a | b is ‘a divides b. Draw a Hasse Diagram for the poset showing all the relations.

 

Permutation and Combination Problems

Semi-Group and Monoid

Preposition Logic and Problems – III

In this article , you will find common laws for preposition logic. These are very helpful in solving problems like simplifying a complex prepositional statement into a simple one. They also form the basis for arguments which you will learn in future lessons.

Identity Laws  (1)

$latex p \wedge T \equiv p$

$latex p \vee F \equiv p$

Domination Laws (2)

$latex p \vee T \equiv T$

$latex p \wedge F \equiv F$

Idempotent Laws (3)

$latex p \vee p \equiv p$

$latex p \wedge p \equiv p$

Double Negation Law (4)

$latex \neg(\neg p) \equiv p$

Commutative Laws (5)

$latex p \vee q \equiv q \vee p$

$latex p \wedge q \equiv q \wedge p$

Associative Laws (6)

$latex (p \vee q) \vee r \equiv p \vee (q \vee r)$

$latex (p \vee q) \vee r \equiv p \vee (q \vee r)$

Distributive Laws (7)

$latex p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$

$latex p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$

De Morgan’s Laws (8)

$latex \neg( p \wedge q) \equiv \neg p \vee \neg q$

$latex \neg( p \vee q) \equiv \neg p \wedge \neg q$

Absorption Laws (9)

$latex p \vee (p \wedge q) \equiv p$

$latex p \wedge (p \vee q) \equiv p$

Negation Laws (10)

$latex p \vee \neg p \equiv T$

$latex p \wedge \neg p \equiv F$

Prepositional Logic and Problems – II

Logical Connectives And Truth Table

Logical statements have truth values such as true or false. One or more simple logical statements can be connected to make a compound statement which also has truth value. The connectives are logical operators that connect one or more logical statements or atomic statements.

The outcome depends on the truth value of individual statements that are part of the compound statement; therefore, all combination of truth values for each atomic statements displayed in a tabular form called the truth table including outcome for each input combinations.

In prepositional logic, there are 5 basic logical connectives which is the topic of this article. These are,

Connective	Name	Symbol
Negation	Not operator
Conjunction	And operator
Disjunction	Or operator
Implication	if-then operator
Biconditional	if-and-only-iff or iff

Negation ()

We have already discussed negation in previous video. Negation simply negates the truth value of an atomic statement. If is a statement with value – True, then is False.

The truth table for negation is given below.

The negation is unary operator which means it only takes a single element or a group of elements enclosed in parenthesis.

Conjunction ()

The conjunction is connective that takes two or more atomic statements and make a compound statement. The output of conjunction is similar to boolean and operator. If all the input combination of a compound statement is True, then the output is True; otherwise, it is False. The conjunction or and operator works on the “all or nothing” principle. The truth table for conjunction is given below.

The total number of rows in this table depends on the number of variables; therefore, if there are two variables.

Number \hspace{5px} of \hspace{5px} rows = 2^n = 2^2 =4

Note that the only row with result True is where both inputs are True.

Disjunction ()

The disjunction is similar to boolean OR logic. It takes one or more atomic statement and makes a compound statement. If the said compound statement is True then there is at-least one atomic statement with a truth value – True. The truth table for disjunction also depends on the number of variables.

In the next article, we will discuss about the implication and biconditional connectives. We discuss why they are different from other basic connectives.

Simple Graph Types

In previous lessons, you learned about graph models and some basic graph terminologies.

In this lesson, you will learn about simple graph types, we learned earlier that a simple graph is one in which each edge has two unique vertices.

Simple Graph Types

The following is a list of simple graph types that we are going to explore.

1. Complete Graph
2. Cycles
3. Wheels
4. n-Cube
5. Bipartite Graph
6. Complete Bipartite Graph

Let us discuss each one them.

Complete Graph

A complete graph on n vertices, denoted by $latex K_n$ is a simple graph that contains exactly one edge between each pair of distinct vertices. It any edge from the pair of distinct vertices is not connected then it is called non-complete.

Here are some examples of complete graph.

Cycles

A cycle is denoted as $latex C_n$ where $latex n \geq 3$ consists of n vertices v₁, v₂, …, v_n and edges { v₁, v₂ }, { v₂, v₃ }, …, { v_n, v₁}.

Here are some examples of cycles.

Wheels

A wheel graph is easy to construct. You get a wheel, $latex W_n&s=1$ when you add an additional vertex to a cycle $latex C_n&s=1$, for $latex n \geq 3&s=1$ and place it in center of the cycle. This will connect each of the n vertices of cycle using new edges.

Some examples of wheels.

n-Cubes

A n-dimensional hyper-cube or n-cube is denoted by $latex Q_n&s=1$ is simple graph that has vertices representing the $latex 2^n&s=1$ bit-strings of length n.

In this scheme, two vertices are adjacent iff the bit strings differ only in one bit position. If this is confusing for you, see the following example.

Suppose $latex Q_1&s=1$ is given by following diagram.

The n-Cube, $latex Q1$ graph contains bit string length of 1. To construct $latex Q2$ from $latex Q1$ write another copy of $latex Q1$ and prefix 0 and 1 to each opposite end.

Similarly, to draw $latex Q3$ graph from $latex Q2$, do same as above, make a copy of $latex Q2$ and add 0 and 1 to opposite ends everywhere. Then join them by edges.

Bipartite Graphs

There is a special type of simple graph called bipartite graph. A simple graph $latex G$ is bipartite if its vertex set $latex V$ can be partitioned into two disjoint sets – $latex V1$ and $latex V2$, such that every edge in the graph $latex G$ connects a vertex in $latex V1$ and $latex V2$. It means no edge in $latex G$ connects two distinct vertices in either $latex V1$ or $latex V2$.

When this condition is holds, then you call the pair $latex (V1, V2)$ bi-partition of $latex V$ of graph $latex G$.

Consider following graphs.

In the first graph, the vertex set $latex V$ is divided into

$latex V1 = { S, R }$

$latex V2 = { A, B, C }$

This graph is a bipartite because there is no edge between nodes of same set. Every edge is connecting two vertices – one from each subset of $latex V$.

The second graph, the vertex set is divided into

$latex V1 = { A, B }$

$latex V2 = { C, D }$

This graph is not a bipartite because $latex A$ and $latex B$ has an edge and both $latex A$ and $latex B$ belong to subset $latex V1$.

Complete Bipartite Graph

If you recall, a complete graph is a graph $latex K_n&s=1$. However, a complete bipartite graph $latex K_{m,n}&s=1$ has its vertex set $latex V$ partitioned into m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.

The total number of vertices in the set $latex V = m + n$ and the total number of edges is $latex E = m * n$ in a complete bipartite graph.

Graph Terminologies

In the previous lesson, you learned about graph models. In this article, you will learn about basic graph terminologies. There are some important terminologies that you will come across frequently, it is important to learn them first.

Definition 1:

Two vertices u and v are adjacent or neighbor in graph G if u and v are endpoints of edge e of G. Then we can say that edge e is incident with vertices u and v and also, connects u and v.

Definition 2:

The set of all neighbors of graph G = (V, E) is denoted by N(v) and it is called Neighborhood of v. The smaller v denotes a single vertex and larger V is a set of all vertices for the graph. If A is a subset of V, then N(A) is set of all vertices that are adjacent to at least one vertex in A.

$latex N(A) = \cup_{v \epsilon A}N(v)$

Definition 3:

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop contributes twice to the degree of the vertex. The degree of a vertex is denoted by $latex deg(v)$.

Degree of Graph

In the above figure, $latex deg(A) = deg(B) =2, deg(C) = 3$. When the degree is 0 then the node is said to be isolated and when the degree is 1, the node is said to be a pendant.

For example, $latex deg(D) = 1$ and $latex deg(E) = 0$.

The Handshake Theorem

The handshake theorem is a special theorem that takes the total amount of degrees of a graph. It goes like this, let $latex G = (V, E)$ be an undirected graph with m edges, then

$latex 2m = \Sigma_{v \epsilon V} deg(v)$

Note: This applies even when multiple edges and loops are present.

Example:-

Consider the above example  graph $latex G = (V, E)$ where $latex V = {A, B, C, D, E }$ and $latex E = { (A, B), (A, C), (B, C), (C, D) } = |E| = 4$

$latex 2 x 4= deg(A) + deg(B) + deg(C) + deg(D) + deg(E)$

$latex 8 = 2 + 2 + 3 + 1 + 0$

$latex 8 = 8$

Right Hand Side = Left Hand Side

Theorem 2: Even Number of Vertices with Odd degree

An undirected graph has an even number of vertices of odd degree.

To prove the above statement, we will consider a graph $latex G = (V, E)$ where $latex V$ is the non-empty set of vertices and $latex E$ is a set of edges for the graph. Now, we will divide the $latex V$ into two sets – $latex V1$ and $latex V2$.

The set $latex V1$ has all nodes with odd degrees. The set $latex V2$ has all the nodes with even degrees.

Therefore,

$latex V = V1 + V2$

Example:-

To prove this theorem let’s take a graph with $latex G = (V, E)$.

A graph with vertices that has even and odd degrees

The above graph we can split the vertices into V1 (odd degrees) and V2 (even degrees).

$latex V1 = { A, B, C , E}$

$latex V2 = { D }$

$latex deg(A) = 3$

$latex deg(B) = 3$

$latex deg(C) = 3$

$latex deg(E) = 1$

$latex \Sigma_{v \epsilon V1}deg(v) = 10$

$latex deg(D) = 2$

$latex \Sigma_{v \epsilon V2}deg(v) = 2$

Now, we need the total number of edges in G which is $latex |E| = 6$.

therefore,

$latex 2 \times 6 = 10 + 2$

$latex 12 = 12$

R.H.S = L.H.S

That means, the theorem is correct and also, $latex V1 = { A, B, C, E }$ is a set with even number of vertices with odd degrees.

The Degree of Directed Edges

We already know that a directed graph has directed edges from the lesson – graph models.

In a graph with directed edges the in-degree of vertex v, denoted by deg-{v}, is the number of edges with v as a terminal vertex.

The out-degree of vertex v, denoted by deg+{v}, is the number of edges with v as an initial vertex for the edges.

Note:- A loop on the vertex contribute 1 to both in-degree and out-degree at the same time.

Example:-

Find the in-degree and out-degree for the following directed graph $latex G = (V, E)$.

The Directed Graph with In-Degree and Out-Degrees for Each Node.

The solution to the problem of counting in-degree and out-degree of each node in the above-directed graph is given in tabular format. You can see that some nodes have 0 degrees or 0 out-degree.

In-Degree and Out-Degree for the Directed graph

Note that a graph with a directed edge and its underlying undirected graph has the same number of edges.