Home » Discrete Mathematics

Propositional Logic in Discrete Mathematics

In this tutorial, we will learn about the proposition or statement, propositional logic, and basic logical operations in Discrete Mathematics. By Prerana Jain Last updated : May 09, 2023

What is Proposition or Statement?

A proposition is a definition sentence which is true or false but not both.

For example: The following 8 sentences,

1. Paris in France
2. 2 + 2 =4
3. London in Denmark
4. X = 2 is solution of x^2 = 4
5. 1 + 1 = 2
6. 9<6
7. Where are you going?
8. Do your homework

All of them are preposition except vii and viii moreover i, ii and vi are true whereas iii, iv, v are false.

Compound proposition

Many propositions are composite that is composed of subpropositions and various connectives discussed subsequently. Such a composite proposition is said to be compound propositions. A proposition is called primitive if it cannot be broken down into the simpler proposition that is if it is not composite.

Example:

1. "John intelligent or studies every night" is a compound proposition with subproposition. "John is intelligent" and "john studies every night".
2. "Roses are red and violets are blue" is a compound proposition with subproposition "Roses are red" and "violets are blue".

Basic Logical Operation

The Three basic logical operations conjunction, disjunction, and negation which corresponds respectively. To the English words "and", "or" and "not".

1. Conjunction (p ^ q)

Any two proposition can be combined by the word and to form a compound proposition said to be the conjunction of the original proposition. Symbolically p ^ q read p and q denotes the conjunction of p and q. Since, p ^ q is a proposition it has the truth value and this truth value depends only on the truth values of p and q, specifically:

Definition: If p and q are true then p ^ q is true otherwise p ^ q is false.

p	q	p ^ q
T	T	T
T	F	F
F	T	F
F	F	F

Example

Consider the following 4 statements:

1. Paris is in France and 2+2 = 4
2. Paris is in France and 2 + 2 = 5
3. Paris is in England and 2 + 2 = 4
4. Paris is in England and 2 + 2 = 5

In the given four statements only the first statement is true. Each of the other statements is false since at least one of its substatements is false.

2. Disjunction (p V q)

Any two proposition can be combined by the word "or" to form a compound proposition is said to be the disjunction of the original proposition, symbolically p V q.

Read "p or q" denotes the disjunction of p and q. The truth value of p V q depends only on the truth values of p and q as follow:

Definition: If p and q are false then p V q is false, otherwise p V q is true.

p	q	pVq
T	T	T
T	F	T
F	T	T
F	F	F

Example

Consider the following four statements:

1. Paris is in France or 2 + 2 = 4
2. Paris is in France or 2 + 2 = 5
3. Paris is in England or 2 + 2= 4
4. Paris is in England or 2 + 2 = 5

Only the last statements are false. Each of the other statements is true since at least of its substatements is true.

3. Negation( ~p)

Given any proposition p another proposition is said to be the negation of p can be formed by writing - it is not the case that... or "it is false that ...", before p or if possible by inserting in p the word "not" symbolically. ~p or ~p.

Read "not p", denotes the negation of p. The truth value of p depends on the truth value of p as follows:

Definition: If p is true then ~p is false and if p is false then ~p is true.

p	~p
T	F
F	~F

---