.Title Discrete Mathematics in Software Engineering .( .Author Dr. Richard J. Botting, .Address Computer Science Dept., California State University, San Bernardino .EMail rbotting@Wiley.csusb.edu .Contents Abstract 1 Introduction 1.1 Problems in Software Engineering (1) 1.2 Mathematics to the Rescue (2) 1.3 Problems with Mathematics (2) 1.4 A Prototype Solution (3) 2 Example - A University 2.1 Sets (3) 2.2 Maps (4) 2.3 Relations (4) 2.4 Axioms (4) 2.5 Object Oriented Conceptual Model (4) 3 MATHS Notation 3.1 Propositions (4) 3.2 Predicates and Quantifiers (5) 3.3 Sets (5) 3.4 Maps and Functions (6) 3.5 Structures (7) 3.6 Binary Relations (7) 4 Use in Software Engineering 5 Use in Teaching 6 Index .Abstract This poster describes a notation for discrete mathematics which is easy to use with any computer and needs no software except a simple ASCII editor. The name of the notation is MATHS and stems from my research into why software is expensive, late and low quality. . Introduction .( . Problems in Software Engineering The literature on Software Engineering makes it clear that mistakes are made in understanding and expressing the problem, which is then solved (sometimes incorrectly), The solution is then coded as a complex piece of software - at which time the errors are discovered. Some mistakes remain hidden until the system is used. The results can be wide spread inconvenience and damage - as when the New York Telephone Exchanges ceased to work last year... More specific analysis of methods shows that this 'Art of Computer Programming' can be replaced by a process based on science and mathematics - See Figure 1. .Page .SADT_DFD Software_engineering::=Net{ P1::=Analysis:Process. P2::=Design:Process. P3::=Implementation:Process. Models, Systems, Designs, Proposals,Problems:Flow. Clients, Discrete_mathematics,Scientific_method, Concrete_mathematics, Computer_Science, C_A_S_E, Computing, Software_tools : Entities. P1.Input::=(Models). P1.Outputs::= (Models). P1.Controls::=(Systems, Clients, Proposals). P1.Mechanisms::=(Discrete_mathematics, Scientific_method, C_A_S_E). P2.Inputs::=(Designs). P2.Outputs::=(Proposals, Computer_science, Designs). P2.Controls::=(Models, Problems). P2.Mechanisms::=(Concrete_mathematics, Computer_Science, C_A_S_E). P3.Inputs::=(Systems). P3.Outputs::=(Problems, Software_tools, Systems). P3.Controls::=(Designs). P3.Mechanisms::=(Computing, Software_tools). Notes::=("P1, P2, P3 are concurrent processes"). }=::Software_engineering. . Mathematics to the Rescue Logic, mathematics, and proofs should be a part of project documentation from the initial stages. Set Theory and Logic are important for defining the problem area. In general Formal Analysis proceeds by stating the obvious. Simple facts determine the set of logically correct structures. Grammar theory is useful for documenting sequential data. The same theory helps define the dynamics (entities, events and patterns) in a situation. Sets and functions describe the structure of the problem domain and are used to document requirements and specifications. These sets and functions define entity types, abstract data types, classes of objects, and/or paths through the data structures and data base. Thus maps and sets define the structure shared by the solution and the problem's environment. Design involves other mathematical methods - The calculus of relations plus an extension to the lower predicate calculus can be used for specifying designs. Statistical analysis and simulations are needed to ensure satisfactory performance as well. Projects that use mathematics and logic can "zero-in" on the best software. First: Define things that appear in the description of the problem and (1) are outside the software, (2) interact with the software, and (3) are individually identifiable by the software. Second: Define events, entities, identifiers, relationships, attributes, facts, and patterns. These initial steps are an exercise in stating the obvious. The Scientific Method is an effective way to develop a mathematical theory or model of the situation. Abstracting a formal model reveals a natural internal structure and so a structure for a design. The models are used to validate requirements, specifications, designs, algorithms, data structures, and data bases. . Problems with Mathematics However there is a problem which is not noticeable in the typical discrete mathematical model: A digraph G is a pair (N, A ) where N is a set and A is a subset of N >->A and 2nd:(A>->B`. Formally, Pairs is the universal (free, initial, or universally repelling) object in the category of all types with 1st and 2nd. This means that all types with two maps called 1st and 2nd into the A and B respectively, is modeled by Pairs. This means that we can map Pairs into any other type without loosing the information about 1st and 2nd items. Therefore A>b rel[x,y](x=a and y=b)={(a,b)} Maplet(Z) A->b rel[x,y](x in A and y=b) Constant Map Id(X) rel[x,y](x=y in X) Identity $Net{D, D'} Relation between D and D' Dynamic Predicate Operators R; S rel[x,y] (for some z(x R z S y)) Product /R rel[x,y]( y R x ) Inverse R^n R;R^(n-1) when n>0, (/R)^(-n) when n<0, Power Id when n=0. do(R) Id | R; do(R) Closure no(R) rel[x,y] (x=y and for no z(x R z)) Complement Functions R(x)=x.R { y || x R y } R(A)=A.R { y || for some x:A( x R y) } /R(y)=y./R y.(/R)={x || x R Y} There are many familiar results, since relations form a semiring with a pseudo- inverse: //R=R, /(R;S)=/S;/R .) . Use in Software Engineering I have shown a piece of a formal description of a typical university that can be the basis for requirements analysis, problem solving, and formal specification. Standard technology and techniques can then be used to implement objects, classes, sets and mappings - using a DBMS, or data structures (in Ada, Pascal, C,...) or Objected Oriented programming (in C++, Smalltalk,...). An alternative is to treat each entity and relationship as a predicate or functor in a logic programming system(eg PROLOG). . Use in Teaching In a Discrete Mathematics class students can draw up formal models as homework and present them for grading, or later in class for review by their peers. Each model has endless homework exercises in using set theory, functions, simple combinatorics, relations etc. The familiarity gained by making abstractions from concrete situations prepares for the introduction of theories at a higher level of abstraction - Posets, Algebras,... . Index . (6) :| (6) {} (6), (8) {e1,e2,e3,...} (6) {e1} (6) {x:T || W(x) } (6)$Net{D} (3), (6-8) /R (8) /R(x) (8) <> (6) = (6) ==> (6) =>> (6) >== (6) & (6) @ (4) @T (5) | (6) ~ (6) A(x) (6) A---B (3) A->b (8) ABELIAN (3) Abelian_semigroup (3) Analysis (1) And (5) Associative (3) C::=Courses (3) C_A_S_E (2) Clients (2) Commutative (3) Complement (6) Computing (2) Concrete_mathematics (2) Course (4) D::=Departments (3) D:C>->D (4) D:Q>->D (4) Declared:@(S, Q) (4) Design (1) Designs (2) Digraph (2) Discrete_mathematics (2) do(R) (8) E::=Sets_of_electives (3) Electives:@(E, Q) (4) Enrolled:@(S, N) (4) F::=Faculty (3) False (4) For (5) For 0 (5) For 0..1 (5) For all (5) For no (5) For some (5) Formal Analysis (2) Group (3) Id(X) (8) If P then Q (5) Iff (5) Implementation (1) In (6) Infix (3) Intersection (6) Member:@(F, D) (4) Models (2) Monoid (3) N (2-3) No(R) (8) Not (5) Or (5) P::=People (3) Parallel (5) Problems (2) Proposals (2) Q::=Qualification (3) R; S (8) R(A) (8) R(x) (8) R^n (8) Required:@(C, Q) (4) S::=Students (3) Scientific_method (2) Sections (3) Semigroup (3) Serial (5) Software_engineering (2) Software_tools (2) Systems (2) Teacher:@(F, N) (4) True (4) Union (6) Units (3) University (2-3) x./R (8) x:X (5) .) Discrete Mathematics in Software Engineering