Discrete Mathematics: Validity, Inference Rules, Consistency, and Set Theory

PADMAVANI ARTSAND SCIENCE COLLEGE FOR WOMEN,SALEM-11 DEPARTMENT OF MATHEMATICS DISCRETE MATHEMATICS BY M.DEEPA

UNIT-I THEORY OF INFERENCE VALIDITY USING TRUTH TABLES: Let A and B be two statement formulas. We say that, B logically follows from A or B is a valid conclusion (consequence) of the premise A iffA B is a tautology, that is , A B.

RULES OF INFERENCE Two rules of inference which are called rules P and T. Rule P: A premise may be introduced at any point in the derivation. Rule T: A formula S may be introduced in a derivation if S is tautologically implied by any one or more of the preceedingformulas in the derivation.

CONSISTENCY OF PREMISES CONSISTENT: A set of formulas H1,H2, .Hmis said to be consistent if their conjunction has the truth value T. A set of formulas H1,H2, .Hmis said to be inconsistent if their conjunction has the truth value F.

THE STATEMENT FUNCTION, VARIABLES AND QUANTIFIERS A simple statement function of one variable is defined to be an expression consisting of a predicate symbol and an individual variable. The resulting from a replacement is called a substitution instance of the statement function and is a formula of statement calculus.

FREE AND BOUND VARIABLES Given a formula containing a part of the form (x) P(x) or( x) P(x),such a part is called an x-bound part of the formula. Any occurrence of x is an x-bound part of the formula is called a bound occurrence of x, while any occurrence of x or of any variable that is not a bound occurrence is called free occurrence.

UNIT-II SET THEORY FUNCTIONS: Let X and Y be any two sets. A relation f from X to Y is called a function if for every x X there is a unique y Y such that (x, y) f.

COMPOSITION OF FUNCTIONS Let f:X Y and g:Y Z be two functions. The composite relation g f such that g f = { <x, z> | (x X) ( z Z) ( y) (y Y y = f(x) z = g (y))} is called the composition of functions or relative product of functions f and g. More precisely, g f is called the left composition of g with f.

INVERSE FUNCTIONS It is easy to see that for a given f:X X, f is a function only if f is one to one. But this condition does not guarantee that f is a function from Y to X. A mapping Ix:X X is called an identity map if Ix ={<x, x>| x X}.

BINARY AND n-ARY OPERATIONS Let X be a set and f be a mapping f: X xX X. Then f is called a binary operation of X. In general, a mapping f: Xn X is called an n-ary operation and n is called the order of the operation. For n=1, f:X X is called a unary operation.

CARDINALITY Two sets A and B are said to be equipotent and written as A~B if and only if there is one to one correspondence between the elements of A and those of B. Note that one to one correspondence can be established by showing a mapping f: A B which is one to one and onto.

UNIT-III ALGEBRAIC STRUCTURES KERNAL OF HOMOMORPHISM: Let g be a group homomorphism from <G, *> to <H, >. The set of elements of G which are mapping to eH, the identity of H, is called the kernel of homomorphism g and denoted by ker (g).

COSETS AND LAGRANGES THEOREM Let <H, *> be a subgroup of <G,*>. For any a G, the set aH defined by aH ={ a*h |h H} Is called the left cosetsof H in G determined by the element a G. The element a is called the representative element of the left coset aH.

NORMAL SUBGROUP DEFINITION: A subgroup <H, *> of <G, *> is called a normal subgroup if for any a G, aH = Ha. EXAMPLE Determine all the proper subgroups of the symmetric group <S3, > as described.

ALGEBRAIC SYSTEM WITH TWO BINARY OPERATIONS DEFINITION: An algebraic system <S, +,.> is called a ring if the binary operation + and . On S satisfies following three properties: 1. <S,+> is an abelian group. 2. <S, .> is an semi group. 3. The operation . Is distributive over +; that is, for any a , b, c S, 4. a.(b+c)=a.b+a.c 5. (b+c).a= b.a+c.a

UNIT-IV LATTICES AND BOOLEAN ALGEBRA LATTICES AND ALGEBRAIC SYSTEM: A lattice is an algebraic system <L,*,+> with two binary operation * and + on L which are both (1) commutative (2) associative and (3) satisfies the absorption laws.

SUBLATTICES, DIRECT PRODUCT AND HOMOMORPHISM Let <P, > and <Q, > be two partially ordered set. A mapping f : P Q is said to be order preserving relative to the ordering in P and in Q if and only if for any a, b belongs to P such that a b, f(a) f(b) in Q . If <P, > and <Q, > are lattices and g : P Q is a lattice homomorphism, then g is the order preserving.

BOOLEAN FORMS AND FREE BOOLEAN ALGEBRA DEFINITION : Two Boolean forms (x1, x2, xn) and (x1, x2 , ..xn) are called equivalent if one can be obtained from the other by a finite number of applications of the identities of a Boolean algebra.

UNIT-v GRAPH THEORY BASIC DEFINITIONS: A graph G= <V, E, > consists of non empty set V called the set of nodes of the graph E is said to be set of edges of the graph, and is a mapping from the set of edges E to be a ordered or unordered pairs of elements of V.

PATHS, REACHABILITY AND CONNECTEDNESS 1. The number of edges appearing in the sequence of a path is called the length of the path . 2. A paths in a digraph in which the edges are all distinct is called a simple path. A path is which all the nodes through which is traverese are distinct is called an elementary path.

THANK YOU