.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
>X, op=>(*))|| X:Sets, (*):associative(X)}.
ABELIAN::=Net{Set:Sets, op:commutative(Set)}.
Abelian_semigroup::=Net{SEMIGROUP. ABELIAN}.
Monoid::=$MONOID, MONOID::=Net{ SEMIGROUP. u:units(Set, op). }.
Group::=$GROUP, GROUP::=Net{ MONOID. i::=inversion:Set---Set.
for all x:Set(x op i(x)=i(x) op x =u). }.
.)
. Example - A University
.(
UNIVERSITY::=Net{ This is a model of a college or university that illustrate the
above ideas.
. Sets
P::=People:Finite_Sets.
S::=Students:@P, |- S in Finite_Sets.
F::=Faculty:@P, |- F in Finite_Sets.
C::=Courses:Finite_Sets,
E::=Sets_of_electives:@C, |- E in Finite_Sets.
N::=Sections:Finite_Sets,
D::=Departments:Finite_Sets,
Q::=Qualification:Finite_Sets,
. Maps
d::=dept:C>->D. Each course is offered by one dept.
d::=dept:Q>->D. Each qualification belongs to a department.
c::=course:N>->C. Each section covers one course.
|- (=):S>->P. - by definition Students are people.
|- (=):F >->P. - by definition Faculty are people.
. Relations
T::=Teacher:F(1..4)-(0..)N. For f:F, s:S, f T s:@::=`f teaches s`.
L::=Enrolled:S(10..200)-(0..15)N. For t:S, n:N,t L n:@::=`t is enrolled in n`.
M::=Member:F(1..)-(0..1)D. For f:F, d:D, f M d:@::=`f is member of d`.
V::=Electives:E(0..)-(1..)Q. For e:E, q:Q, e V q:@::=`e is set of
electives in q`.
W::=Declared:S(0..)-(0..)Q. For t:S, q:Q, t W q:@::=`t declared major q`.
R::=Required:C(1..)-(0..)Q. For c:C, q:Q, c R q:@::={c}V q::=`c is required
in q`.
|- in:C(1..)-(0..)E. For c:C,e:E, c in e:@::=`c is an elective in set e`.
. Axioms
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):
.Display
----------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.)
...(Further concepts)
} =::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}.
The following tables defines the operators in this algebra.
.Table
Symbol Values Syntax
P true false
not P false true prefix
P true true false false
Q true false true false
P and Q true false false false infix(serial)
P or Q true true true false infix(serial)
P iff Q true false false true infix(parallel)
if P then Q true false true true special (distfix)
Unlike most programming languages mathematics has two kinds of infix operator.
Serial: P1 and P2 and P3 = (P1 and P2) and P3
Parallel: P1 iff P2 iff P3 = (P1 iff P2) and (P2 iff P3).
. 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`,
for x:X(W(x))::= for all x:X(W(x)),
for no x:X(W(x))::=for all x:X(not W(x)),
for some x:X(W(x))::=not for no x:X(W(x)).
for 0 x:X(W(x))::= for no x:X(W(x) ),
for 1 x:X(W(x))::= for some x:X(W(x) and for 0 y:X(x<>y and
W(x))),
for 2 x:X(W(x))::= for some x:X( W(x) and for 1 y:X(x<>y and
W(y)) ).
for 3 x:X(W(x))::= for some x:X( W(x) and for 2 y:X(x<>y and
W(y)) ).
. . .
for 0..1 x:X(W(x))::=for all y,z:X( if W(y) and W(z) then y=z),
. . .
. 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 `A`s 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`.
.Table
Expression Meaning Type Example.
Sets {} null or empty set Ambiguous
T universal set @T Numbers
{e1} singleton @T (e is of type T){1}
{e1,e2,e3,...}extension @T (e1,e2,...are type T){1,2,3}
{x:T || W(x) } intention @T {n:Nat||n*n=4}
$Net{D} Set satisfying documentation D tupls defined by D (See above)
n..m Range, closed interval @T (T must have a linear order)
Predicates
e1 in S1 membership T><@T >-> @ 1 in 1..
S1<> S2 inequality @T><@T >-> @ 1..<>0..
S1 = S2 equality @T><@T >-> @ 1..2={1,2}
S1==>S2 subset or equal @T><@T >-> @ 1..2==>1..3
S1=>>S2 proper subset @T><@T >-> @ 1..2=>>1..3
S1 >==S2 S1 partitions into S2 @T><@T >-> @ 1..3>=={1..2,{3}}
Operators
S1 & S2 intersection @T><@T >-> @T ..n&m..=n..m
S1 | S2 union @T><@T >-> @T ..n-1 | m+1..
S1 ~ S2 complement @T><@T >-> @T = Nat ~(n..m)
We can use a set anywhere a type could be used, for example, when A:@T and W a
well formed formula:
for all x:A(W)::=for all x:T (if x in A then (W))
In English and mathematics the common idiom puts a type name before the variable -
for example:
For all real x and \eta>0 there is a real \delta>0 such that |f(x+\delta)-f(x)| < \eta,
or in MATHS
for all Real x, Real \eta>0, some Real \delta>0( |f(x+\delta)-f(x)| < \eta),
meaning
for all x:Real(for all \eta:Real (if \eta>0 then for some \delta:Real
(\delta>0 and |f(x+\delta)-f(x)| < \eta ) ) ).
Another useful form is like `There are two elevators and five floors`. MATHS
form is `2 Elevators and 5 Floors`. The general form is when Q is any
quantifier(all,some,none,...) or number and A:@T,
Q A::= for Q x:T (x in A).
Thus |- for all A, no A iff A={}, 1 A iff for some a:T(A={a}), . . .
So, for example, we can show:
|- A=>>B iff some (A~B).
|- A>=={B,C} iff A=B|C and no A&B.
. 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 vector scalar. functions project structured objects their components. symbol `map` used abstract from expressions: map[x:domain] expression ). structures all modern notations ada z provide means for creating new `type object` listing components specifying constraints operations these special interpreted as defining labeled tupls. d list net{d} $net{d} labelled tupls satisfy documentation. given n::="Net{D})" n $n represents meaning structure collection maps. thus pair::="A">**->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
**