Mathematical StructuresA collection of objects with operations defined onthem and the accompanying properties form amathematicalstructure or system.In this book, we deal only with discrete mathematicalstructuresAstructureisclosedwithrespecttoanoperationifthat operation always produces another member ofthe collection of objects. An operation that combines two objects is a binaryoperation; an operation that requires only one objectis a unary operation.If the order of the objects does not affect the outcomeof a binary operation, the operation is commutative,i.e.if xy = yx, where is some binary operation, iscommutative
Mathematical Structures • A collection of objects with operations defined on them and the accompanying properties form a mathematical structure or system. • In this book, we deal only with discrete mathematical structures. • A structure is closed with respect to an operation if that operation always produces another member of the collection of objects. • An operation that combines two objects is a binary operation; an operation that requires only one object is a unary operation. • If the order of the objects does not affect the outcome of a binary operation, the operation is commutative, i.e. if x•y = y•x, where • is some binary operation, • is commutative
Mathematical Structures (cont") If is a binary operation, then is associative or hasthe associative property if(xy)z = x(yz)If a mathematical structure has two binaryoperations,and△,adistributivepropertyhas thefollowing pattern:x(y △ z)= (xy) △ (xz)If the unary operation is * and the binary operationsare and △, then De Morgan's laws are (xy)*= x*△yand (xy)*= x*y*. If a structure with a binary operation contains adistinguished object e, with the property x ·e = e x =x for all x in the collection, then e is an identity for :and e is unique
• If • is a binary operation, then • is associative or has the associative property if (x•y)•z = x•(y•z) • If a mathematical structure has two binary operations, • and , a distributive property has the following pattern: x•(y z)= (x•y) (x•z) • If the unary operation is * and the binary operations are • and , then De Morgan’s laws are (x•y)*= x*y* and (xy)*= x*•y* • If a structure with a binary operation • contains a distinguished object e, with the property x •e = e •x = x for all x in the collection, then e is an identity for • and e is unique. Mathematical Structures (cont’)
Mathematical Structures (cont")Theorem 1. If e is an identity of a binaryoperation ; then e is unique.. If a binary operation has an identity e,then yis a -inverse of x ifxy=yx=eTheorem 2. If is an associative operationand x has a inverse y, then y is unique
Theorem 1. If e is an identity of a binary operation •, then e is unique. • If a binary operation • has an identity e, then y is a •–inverse of x if x •y = y •x = e Theorem 2. If • is an associative operation and x has a •–inverse y, then y is unique. Mathematical Structures (cont’)
Part 2LogicMethods of reasoningTo prove theoremsTo verify the correctness of programsTo draw conclusions from experimentsTo solve a multitude of problems
Part 2 Logic Methods of reasoning To prove theorems To verify the correctness of programs To draw conclusions from experiments To solve a multitude of problems
Propositions and LogicalOperations· Astatement or proposition is a declarativesentence that is either true or false, but notboth. In logic, the letters p,q,r,... denotepropositional variables that can be replacedby statements. Statements or propositional variables can becombined by logical connectives to obtaincompound statements the negation of p is the statement not p, ~p a truth table gives the truth values of acompound statement in terms of itscomponent parts
• A statement or proposition is a declarative sentence that is either true or false, but not both. • In logic, the letters p,q,r,. denote propositional variables that can be replaced by statements. • Statements or propositional variables can be combined by logical connectives to obtain compound statements. • the negation of p is the statement not p, ~p • a truth table gives the truth values of a compound statement in terms of its component parts Propositions and Logical Operations