Maths : Discrete Mathematics : Summary

**SUMMARY**

(1) A **binary
operation** * on a non-empty set *S* is a rule, which associates to each
ordered pair ( *a* , *b*) of elements *a* , *b* in *S* an unique element *a* **b* in *S* .

(2) **Commutative
property: **Any binary operation** ***** **defined on a nonempty
set** ***S*** **is said to satisfy the
commutative property, if *a* ∗ *b*
=
*b* ∗ *a*,
∀*a* , *b* ∈ *S* .

(3)
**Associative
property: **Any binary operation** ***** **defined on a nonempty
set** ***S*** **is said to satisfy** **the associative
property, if *a* ∗ (*b* ∗*c* ) = ( *a* ∗*b* ) ∗ *c* , ∀*a* , *b*, *c* ∈ *S* .

(4)
**Existence of
identity property: **An element *e*
∈ *S* is said to be the **Identity Element** of *S* under** **the
binary operation * if for all** ***a *∈* S *we have that* a *∗* e *=* a *and* e *∗* a *=* a *.

(5)
**Existence of
inverse property: **If an identity element** ***e*** **exists and if for every** ***a*** **∈** ***S*** **, there exists *b* in *S*
such that *a* ∗ *b*
=
*e* and *b* ∗ *a* = *e*
then *b* ∈ *S*
said to be the **Inverse
Element** of *a* . In such instance, we write *b* = *a*^{−}^{1} .

(6)
**Uniqueness
of Identity: **In an algebraic structure the
identity element (if exists) must be** **unique.

(7) **Uniqueness of
Inverse: **In an algebraic structure the
inverse of an element (if exists) must be** **unique.

(8)
A **Boolean
Matrix** is a real matrix whose entries are either 0 or 1.

(9)
**Modular
arithmetic: **Let** ***n*** **be a
positive integer greater than 1 called the** modulus**.
We say**
**that two integers *a* and *b* are congruent
modulo *n* if *b − a* is divisible by *n*.
In other words *a *≡* b *(mod n) means* a *−* b *=* n *⋅* k *for some integer* k *and* b *is the* *l**east non-negative integer*** ***reminder **when** ***a*** **is divided by** ***n*.** **( 0** **≤** ***b*** **≤** ***n*** **−1)

(10)
Mathematical logic is a study of reasoning through mathematical symbols.

(11)
Let *p* be a simple statement. Then the
**negation**
of *p *is a statement whose truth value
is opposite to that of *p* . It is
denoted by ¬ *p*, read as **not** *p ***.**The
truth value of ¬*p *is* T ***,*** *if*
p *is *F*, otherwise it is* F *.

(12) Let
*p* and *q* be any two simple statements. The **conjunction** of *p* and *q* is obtained by connecting *p*
and *q* by the word **and**.
It is denoted by *p* ∧ *q*
, read as ‘ *p* conjunction *q* ’ or ‘ *p* hat *q* ’. The truth
value of *p* ∧ *q*
is *T* , whenever both *p* and *q* are *T* and it is *F* otherwise.

(13)
The **disjunction**
of any two simple statements *p* and *q* is the compound statement obtained by
connecting *p* and *q* by the word ‘or’. It is denoted by *p* ∨ *q* , read as‘ *p* disjunction *q* ’ or ‘ *p* cup *q* ’.The truth value of *p* ∨ *q*
is *F* , whenever both *p* and *q* are *F* and it is *T* otherwise.

(14)
The **conditional
statement** of any two statements *p*
and *q* is the statement, ‘If *p* , then *q* ’ and it is denoted by *p*
→
*q* . The statement *p* → *q*
has a truth value *F* when *q* has the truth value *F* and *p* has the truth value *T*;
otherwise it has the truth value *T.*

(15)
The **bi-conditional
statement** of any two statements *p*
and *q* is the statement ‘ *p* if and only if *q* ’ and is denoted by *p* ↔
*q* The statement *p* ↔ *q* has the truth
value *T* whenever both *p* and *q *have identical truth values; otherwise has the truth value* F*.

(16)
A statement is said to be a **tautology** if its truth value is always *T* irrespective of the truth values of
its component statements. It is denoted by **T**.

(17)
A statement is said to be a **contradiction** if its truth value is always *F* irrespective of the truth values of
its component statements. It is denoted by **F**.

(18)
A statement which is neither a tautology nor a contradiction is called **contingency**.

(19)
Any two compound statements *A* and *B* are said to be **logically equivalent** or simply **equivalent**
if the columns corresponding to *A* and
*B* in the truth table have **identical truth
values**. The logical equivalence of the statements *A* and *B* is denoted by *A* ≡
*B* or *A* ⇔ *B* . Further note that if *A* and *B* are logically equivalent, then *A* ↔ *B*
must be a **tautology**.

(20)
**Some laws of equivalence:**

**Idempotent Laws:** (i) p ∨ p ≡ p (ii) p ∧ p ≡ p .

**Commutative Laws:** (i) p ∨ q ≡ q ∨ p (ii) p ∧ q ≡ q ∧ p .

**Associative Laws:** (i) p ∨ ( q ∨ r ) ≡ ( p ∨ q ) ∨ r (ii) p ∧ ( q ∧ r ) ≡ ( p ∧ q ) ∧ r .

**Distributive Laws:**** **(i) p ∨ ( q ∧ r) ≡ ( p ∨ q) ∧ ( p ∨ r)

(ii) p ∧ ( q ∨ r) ≡ ( p ∧ q) ∨ ( p ∧ r)

**Identity Laws:** (i) p ∨
**T**
≡ **T** and p ∨ ** **≡ *p*

(ii)
p ∧ **T** ≡ p and p ∧
**F** ≡ **F**

**Complement Laws : **(i) p ∨ ¬p ≡ **T** and p ∧
¬ p ≡ **F**

(ii)
¬ **T** ≡ **F** and ¬ **F** ≡ **T**

**Involution Law or
Double Negation Law: **¬(¬p) p

**de Morgan’s Laws:** (i) ¬( p ∧ q) ≡ ¬p ∨ ¬q (ii) ¬( p ∨ q) ≡ ¬p ∨ ¬q

**Absorption Laws:** (i) p ∨ ( p ∧ q) ≡ p (ii) p ∧ ( p ∨ q) ≡ p

Tags : Discrete Mathematics | Mathematics , 12th Maths : UNIT 12 : Discrete Mathematics

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

12th Maths : UNIT 12 : Discrete Mathematics : Summary | Discrete Mathematics | Mathematics

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.