Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [papers] >> rjb9Xb.discrete
[Index] [Contents] [Source] [Notation] [Copyright] [Comment] [Search ]
Fri May 12 15:36:12 PDT 2006
This part of my site contains partly baked ideas (PBI). It has drafts for publications, essays, plus illustrations and visual aids for presentations and seminars.

Disclaimer. CSUSB and the CS Dept have no responsibility for the content of this page.

Copyright. Richard J. Botting ( Fri May 12 15:36:12 PDT 2006 ). Permission is granted to quote and use this document as long as the source is acknowledged.

Contents

    Discrete Mathematics in Software Engineering

      .Author Dr. Richard J. Botting, <dick@silicon.csci.csusb.edu>
      Computer Science Dept., California State University, San Bernardino

      .EMail rbotting@Wiley.csusb.edu

      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.

      1. Software_engineering::=following
        Net
        1. P1::=Analysis::Process. P2::=Design::Process. P3::=Implementation::Process.
        2. Models, Systems, Designs, Proposals,Problems::Flow.
        3. Clients, Discrete_mathematics,Scientific_method, Concrete_mathematics,
        4. Computer_Science, C_A_S_E, Computing, Software_tools :: Entities.
        5. P1.Input::=(Models). P1.Outputs::= (Models).
        6. P1.Controls::=(Systems, Clients, Proposals).
        7. P1.Mechanisms::=(Discrete_mathematics, Scientific_method, C_A_S_E).
        8. P2.Inputs::=(Designs).
        9. P2.Outputs::=(Proposals, Computer_science, Designs).
        10. P2.Controls::=(Models, Problems).
        11. P2.Mechanisms::=(Concrete_mathematics, Computer_Science, C_A_S_E).
        12. P3.Inputs::=(Systems).
        13. P3.Outputs::=(Problems, Software_tools, Systems).
        14. P3.Controls::=(Designs).
        15. P3.Mechanisms::=(Computing, Software_tools).
        16. Notes::=("P1, P2, P3 are concurrent processes").

        (End of Net 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 ><N....

        If we model a typical problem area then we might see:

      2. A university U is a 17-tple ( P, S, F, C, E, N, D, Q, ...) where...

        One problem is obvious - there are too many components! The computer professional is further struck by the informality of the language and the difficult of processing it with a computer. The typical client will be dumb founded, of course.

        A Prototype Solution

        My research has focussed on putting together a formal language, that can be handled by any computer and even translated into 'client friendly' language and graphics. I have designed a prototype formal language that uses ASCII. I call it the Multi-purpose Abstraction, Terminology, Heuristic Symbology (MATHS).

      . . . . . . . . . ( end of section Introduction) <<Contents | End>>

      MATHS

        In MATHS documentation the following are important parts:
      1. Declarations Identifier :: Set
      2. (Introduce name/variable and bind to type)
      3. Definition Term ::= Expression
      4. (Equivalent to declaring term and asserting '=')
      5. Term::Context=Expression
      6. Variable::=Term::Context
      7. (introduces Mathematical shorthand)
        Axiom |- (label): Well Formed Formula
      8. Theorem (reasons)|- (label): Well Formed Formula
      9. Proofs, etc See [ logic_2_Proofs.html ]
      10. Comments Anything that is not formal.

        If D is a collection of declarations, definitions, axioms, theorems etc. then Net{ D } is called a set of documentation and Net{ D } is the set of objects that satisfies the documentation. A degenerate case is when D contains nothing recognisably formal - it is then treated as a natural language comment - with perhaps some variables/parameters embedded in it.

        SAMPLES FROM ALGEBRA

      11. For all Sets A, B, A---B ::= { f:B^A || for all b:B, one a:A ( f(a)=b)}.

      12. For all Sets X,
      13. infix(X) ::= X^( X><X ),
      14. associative(X) ::={ *:infix(X)||for x,y,z:X (x*(y*z)=(x*y)*z)},
      15. commutative(X) ::={ *:infix(X)||for x,y:X (x*y = y*x)},

      16. For X, *, units(X,*) ::={ u:X||x*u = u*x = x},

      17. Semigroup::=SEMIGROUP,
      18. SEMIGROUP::=Net{ Set::Sets, op::associative(Set) }.


      19. |-Semigroup = { (Set=>X, op=>(*))|| X:Sets, (*) :associative(X)}.

      20. ABELIAN::=Net{ Set::Sets, op::commutative(Set). }.

      21. Abelian_semigroup::=Net{ SEMIGROUP. ABELIAN. }.
      22. Monoid::=MONOID,
      23. MONOID::=Net{ SEMIGROUP. u::units(Set, op). }.
      24. Group::=GROUP,
      25. GROUP::=following
        Net

        1. |-MONOID.
        2. i::=inversion::Set---Set.
        3. |- (inverse): for all x:Set(x op i(x)=i(x) op x =u).

        (End of Net GROUP.)

      Example - A University

      1. UNIVERSITY::=following,
        Net
          This is a model of a college or university that illustrate the above ideas.

          Sets

        1. People::Finite_Sets.
        2. P::=People.
        3. Students::@P,
        4. S::=Students,
        5. (S, P) |-S in Finite_Sets.
        6. Faculty::@P,
        7. F::=Faculty,
        8. (F, P) |-F in Finite_Sets.
        9. Courses::Finite_Sets,
        10. C::=Courses,
        11. Sets_of_electives::@C,
        12. E::=Sets_of_electives,
        13. (E, C) |-E in Finite_Sets.
        14. Sections::Finite_Sets,
        15. N::=Sections,
        16. Departments::Finite_Sets,
        17. D::=Departments,
        18. Qualification::Finite_Sets,
        19. Q::=Qualification,

          Maps

        20. dept::C->D. Each course is offered by one dept.
        21. dept::Q->D. Each qualification belongs to a department.
        22. d::=dept.
        23. course::N->C. Each section covers one course.
        24. c::=course.

          (S, P) |-(=) ::S->P. - by definition Students are people. (F, P) |-(=) ::F ->P. - by definition Faculty are people.

          Relations

        25. Teacher::F(1..4)-(0..)N.
        26. T::=Teacher.
        27. For f:F, s:S, f T s::@=f teaches s .
        28. Enrolled::S(10..200)-(0..15)N.
        29. L::=Enrolled.
        30. For t:S, n:N, t L n::@=t is enrolled in n .
        31. Member::F(1..)-(0..1)D.
        32. M::=Member.
        33. For f:F, d:D, f M d::@=f is member of d .
        34. Electives::E(0..)-(1..)Q.
        35. V::=Electives.
        36. For e:E, q:Q, e V q::@=e is set of electives in q .
        37. Declared::S(0..)-(0..)Q.
        38. W::=Declared.
        39. For t:S, q:Q, t W q::@=t declared major q .
        40. Required::C(1..)-(0..)Q.
        41. R::=Required.
        42. For c:C, q:Q, c R q::@= { c} is required in q .
        43. (above) |- in::C(1..)-(0..)E.
        44. For c:C,e:E, c in e::@=c is an elective in set e .

          Axioms


        45. |-For f:F, s:N, if f T s then f M d(c(s))

          Object Oriented Conceptual Model

          After some manipulation this can be turned into a data base or an object oriented design (also in ASCII) : 
             --------------People-----------
             "1                             "1
             "                              "
             "0..1                          "
          Faculty   Department              "
           "1  "1   |1   |1  |1             "
           "   "    |    |   |              "
           "   "0,1 |1.. |   |0..           "0..1
           "   Member    |  Qualification  Student
           "             |        |1   |1  |1  |1
           "             |        |    |0..|0..|
           "             |0..     |   Declared |
           "         Course       |1..         |
           "        |1    |1    Electives      |
           "        |     |       |1           |
           "        |     |       |            |
           "        |0..  |0..    |1..         |
           "     Section   --in---             |
           "     |1    |1                      |
           "0..  |1..4 |10..200                |0..15
           Teacher      ------Enrolled---------

          (Each vertical line is a mapping. Ditto marks show a subset of the upper one.)

        46. ...(Further concepts)

        (End of Net UNIVERSITY.)

      MATHS Notation

        Propositions

         A proposition can have two possible meanings - true and false. In MATHS the symbol @ represents the Boolean type with two standard values { true, false}. Here are the operators
        • not P
        • P and Q
        • P or Q
        • P iff Q
        • if P then Q

      Unlike most programming languages mathematics has two kinds of infix operator.

    1. (Serial): P1 and P2 and P3 = (P1 and P2) and P3
    2. (Parallel): P1 iff P2 iff P3 = (P1 iff P2) and (P2 iff P3).

      For more see [ logic_0_Intro.html ]

      Predicates and Quantifiers

      A predicate can have variables, quantifiers and equalities as well the propositions listed above. MATHS spells quantifiers out and includes numerical quantifiers like "one", "no", "0..1". The syntax attempts to make the writing of formal statements as natural as possible. In the following X is a set or a type, x is a variable and W(x) a proposition containing x in a number of places. for all x:X(W(x)) ::=For all x of type X, W(x) is true ,
    3. for x:X(W(x)) ::= for all x:X(W(x)),
    4. for no x:X(W(x)) ::=for all x:X(not W(x)),
    5. for some x:X(W(x)) ::=not for no x:X(W(x)).

    6. for 0 x:X(W(x)) ::=for no x:X(W(x) ),
    7. for 1 x:X(W(x)) ::=for some x:X(W(x) and for 0 y:X(x<>y and W(x))),
    8. for 2 x:X(W(x)) ::=for some x:X(W(x) and for 1 y:X(x<>y and W(y))).
    9. for 3 x:X(W(x)) ::=for some x:X(W(x) and for 2 y:X(x<>y and W(y))).
    10. . . .
    11. for 0..1 x:X(W(x)) ::=for all y,z:X( if W(y) and W(z) then y=z),
    12. . . . [ logic_10_Props_+_Predicates_.html ] [ logic_11_Equality_etc.html ] [ logic_2_Proofs.html ]

      Sets

       For any type T there is an another type symbolized by @T with objects that are sets of objects of type T. In MATHS a subset of a type is not a type, but a subset (or set for short) does belong to a particular type and so determines the type of an element in it: If a set A is of type @T then As elements must be of type T. It is therefore unambiguous to use sets to declare the type of a variable. In MATHS the symbol for the type is also symbol for the universal set of that type. It can also be used to indicate the type of a value - if e can have values of different types then T(e)=(e).T is the value in T.

      Here are some typical expressions

    13. { } -- the null set
    14. T -- the universal set (the name ofthe type)
    15. {e} -- a singleton set
    16. {e1,e2,e3,...} -- set with listed elements
    17. { x:T || P } -- set of x's of type T defined by P
    18. Net{ D } -- Set satisfying documentation D tupls defined by D
    19. n..m -- Range, closed interval @T (T must have a linear order)

      Predicates

    20. e1 in S1 -- membership
    21. S1<> S2 -- inequality
    22. S1 = S2 -- equality
    23. S1==>S2 -- subset or equal
    24. S1=>>S2 -- proper subset
    25. S1 >==S2 -- S1 partitions into S2

      Operators

    26. S1 & S2 -- intersection
    27. S1 | S2 -- union
    28. S1 ~ S2 -- complement

      Forthe full details see: [ logic_30_Sets.html ] [ logic_31_Families_of_Sets.html ] [ logic_32_Set_Theory.html ]

      Maps and Functions

      MATHS uses both the traditional functional notation (f(x)) and a dot notation(x.f). So
      For x:X and f:X>-Y, f(x)=x.f= the f of x in Y.

      The dot notation fits with Ada, C, Pascal,... where item names map record values into item values. In mathematics '.' projects a vector into a scalar. MATHS uses functions to project structured objects to their components.

      The symbol fun (and also 'map') is used to abstract functions from expressions:

    29. fun[x:Domain] ( Expression ).

      For more see: [ logic_5_Maps.html ] [ logic_6_Numbers..Strings.html ]

      Structures

      All modern formal notations from Ada to Z provide means for creating a new type of object by listing components and specifying constraints and operations on these components. In MATHS a special set of declarations can be interpreted as defining a set of labeled tupls. If D is a list of declarations then
    30. Net{ D }

      is a set of documentation and

    31. Net{ D }

      is the set of labelled tupls that satisfy the documentation. A name can be given to documentation (

    32. N::=Net{ D }

      ) and if N is the name then N represents the set of objects that satisfy the documentation. The formal meaning of a structure is as a collection of maps. Thus

    33. Pair::=A><B::=Net{ 1st::A, 2nd::B }

      implies 1st: (A><B)->A and 2nd:(A><B)->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 = Pairs encodes all sets of objects with two components.

      Given a structured type T=N then we can talk about its subsets (@T). Sets of structures are universal. Codd has shown that any set of data can be expressed as simple structured tables. This justifies modelling all abstract objects as tuples. A collection of sets of tuples is a relational data base and forms a category. The objects in an object oriented design also forms a similar category. These collection form a conceptual model of the area being studied that is readily implemented using modern techniques such as data bases, logic programming, and object oriented programming.

      Binary Relations

      A special kind of relationship is one with two components - equivalent to a set of 2-tuples. They are turn up in all formal and natural settings. A relation is typically defined like this
    34. For x:A, y:B, x R y::=W(x,y) ,

      where W(x,y) is a well formed formula. Given the above definition then

    35. rel[x:A,y:B](W(x,y)) = R. The set of all relations between sets A and B is written @(A,B) but can be treated as a subset of A><B:
    36. R = { (x, y) :A><B || x R y }

      Thus relations inherit set operations of intersection, union and complement.

      They have their own operators as well:

    37. a+>b =rel[x,y](x=a and y=b)={ (a,b)} Maplet(Z)
    38. A+>b =rel[x,y](x in A and y=b) Constant Map
    39. Id(X) =rel[x,y](x=y in X) Identity
    40. Net{ D, D' } =Relation between D and D' Dynamic Predicate
    41. R; S =rel[x,y] (for some z(x R z S y)) Product
    42. /R =rel[x,y]( y R x ) Inverse
    43. R^n =R;R^(n-1) when n>0,
    44. = (/R)^(-n) when n<0, Power
    45. = Id when n=0.
    46. do(R) =Id | R; do(R) Closure
    47. no(R) =rel[x,y] (x=y and for no z(x R z)) Complement Functions
    48. R(x)=x.R ={ y || x R y }
    49. R(A)=A.R ={ y || for some x:A( x R y) }
    50. /R(y)=y./R =y.(/R)={ x || x R Y}

      For more see [ logic_40_Relations.html ] [ logic_41_HomogenRelations.html ] [ logic_42_Properties_of_Relation.html ] [ logic_44_n-aryrelations.html ]

      Other Logics

      See [ logic_7_Semantics.html ] [ logic_8_Natural_Language.html ] [ logic_9_Modalities.html ]

    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,...

. . . . . . . . . ( end of section Discrete Mathematics in Software Engineering) <<Contents | End>>

End