Home | | Maths 12th Std | Summary

# Summary

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 = a1 .

(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 least 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 TT  and p  p

(ii) p T ≡ p and p FF

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

(ii) ¬ TF and ¬ FT

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