What is Discrete Mathematics?

Discrete mathematics deals with the separated values of data such as integers. It is widely used in the practical field of computer science and mathematics. By knowing discrete mathematics one can improve their reasoning and problem-solving capabilities. Discrete mathematics became popular after the boom of computers which operate in discrete steps and store data in discrete bits. It also useful in studying computer programming, algorithms, and cryptography.

What is Logic?

There are several components under discrete mathematics one among those is logic and proof. Logic allows us to specify the method of reasoning statements. Propositional logic is a collection of statements in a declarative manner of its truth value which is either “TRUE” or “FALSE”. We assign propositional variables in capital letters as (A,B,..). The main purpose is to analyse whether the statements are in a composite or individual manner. There are three mathematical logics:

• Propositional logic
• Predicate logic
• Rules of inference

Connectives

The connectives are those which connect the propositional variables. There are five connectives in propositional logic. They are:

• Or (∨)
• And (∧)
• Not (¬)
• If-then (→)
• If and only if (↔)     

Or (V) Operator

Let us take two proposition variables A and B, then the connection is written as (A ᴠ B). If at least any one of the proposition logic variables is true then A ᴠ B is TRUE.

Truth Table Of Or

And (ᴧ) Operator

In ‘and’ operator the connection of two propositional variables A and B is written as A ᴧ B. This operator is TRUE only when both the variables are TRUE.

Truth Table of And

Not (¬) Operator

The ‘not’ operator is also called a negation. The negation of a variable can be written as ¬A. This functions like when the variable A is TRUE then ¬A is FALSE, when the variable A is FALSE then ¬A is TRUE.

Truth Table of Not

If-Then (→) Operator

The ‘if-then’ operator is also called an implication. Implication is denoted as A → B. It is TRUE in all three cases except when A is FALSE and B Is TRUE.

Truth Table of If – Then

If and Only If (↔) Operator

The ‘if and only if’ operator is also called a bi-conditional logical connective which is TRUE only when A and B have the same truth value.

Truth Table for If and Only If

Prepositional Equivalences

There are two statements where A and B are logically equivalent they are,

• The truth tables of each and every statement have the same truth values
• The bi-conditional statement is a tautology (i.e., A↔B)

Note: A formula is said to be a tautology if it is always true for every value of its propositional variables.

Example

¬(X ᴠ Y) and [(¬X) ᴧ (¬Y)] are Equivalent.

Proof

By first statement method,

Here the columns of ¬(X ᴠ Y) and [(¬X) ᴧ (¬Y)] are same, hence the statements are equivalent.

By second statement method,

As [¬(XᴠY)]↔ [(¬X) ᴧ (¬Y)] is a tautology, the statements are equivalent.

Predicate Logic

Predicate logic contains various statements and two or more variables determined on a specific domain that does not have any values. If we assign some values to the statement and variables then it becomes propositional logic. Predicate logic has a well-formed formula which is useful to evaluate the TRUE or FALSE variables therefore it is also called as a Boolean valued function. Predicate logic contains an atomic formula which is also a well-formed formula but this connects with logical connectives. Predicate logics are denoted by capital variables like P,Q,R.

Well-Formed Formula (WFF)

A wff is a predicate holding any of the following:

• Every propositional constant and variable is WFF.
• Truth and false values are WFF.
• The atomic formula is WFF.
• If x is variable and B is a WFF, then ⩝xB and ∃xB are also WFF.

Quantifiers

The predicate logic variables are quantified by the quantifiers. A predicate that does not contain any quantifier is called a propositional formula. There are three types of quantifiers:

• Universal quantifier
• Existential quantifier
• Nested quantifier

Universal Quantifier

Universal quantifier quantifies the statement within the scope where every value of the specific variable a TRUE. It is denoted by ⩝.

∀xP(x) is taken as for all values of x, P(x) is TRUE.

Existential quantifier

Existential quantifier quantifies the statement within the scope where some values of the specific variable are TRUE. It is denoted by ∃.

∃xP(x) is taken as for some value of x, P(x) is TRUE.

Nested quantifier

Nested quantifier quantifies the statement where the scope lies in another quantifier.

Rules of Inference

Rules of inference give us the guidelines to construct valid arguments from the statements we already know. It is denoted by ∴ .

Proofs

Proofs are collections of statements in a sequential manner where the last statement is a conclusion and the preceding statements are known as hypotheses. The last statement is followed by the preceding statement so the conclusion must be true if the preceding statement is true. There are different methods for proofs. Some of the main methods are:

• Direct proof
• Proof by contradiction
• Proof by contrapositive
• Proof by cases

Direct Proof

Direct proof is the simplest form. This requires proving everything in their systematic explanation of what it means. It is mostly used in proving implications. The general form of this proof is A→B.

Proof by Contradiction

Proof of contradiction is that we assume some statement that we want to prove is not true and then work to show its falsity until the assumption of the statement contradicts.

Example

The given statement is 2 is irrational. We want to assume that it is rational and work on it until it contradicts the statement.

Proof by Contrapositive

A contrapositive statement is also called a contraposition proof. It is a conditional statement in which we negate both. If A is true then B is inferred as true, if B is not true then A is also not true.

Proof by Cases

Proof by cases is also known as proof by exhaustion, where the statement is split into a finite number of cases. For example, we take A is TRUE by proving A → B AND ¬B→A for some statement B. We know that A is true but we want to generalize it so we know that when any of the Q₁,Q_2,…Q_n is true. So by equating  Q₁→P,…we can say any of the Q_i must be true.   

Context and Applications  

This topic is significant in the professional exams for both undergraduate and graduate courses, especially for:      

• B.Sc. Mathematics
• M.Sc. Mathematics