4.1.1 A Discipline of Specification

The specification of a software product is a description of the properties that the product must have to fulfill its purpose. The specification is usually derived by identifying all the relevant stakeholders of the (existing or planned) software product, eliciting the requirements that they expect the product to meet, formulating and combining these requirements, and compiling them into a cohesive document. While specifications typically pertain to functional and operational requirements, we focus primarily on functional requirements in this book, that is, requirements that pertain to the input/ output behavior of the software product.

As a product, a specification must meet two conditions, which are as follows:

1. Formality: The specification must be represented in such a way as to describe precisely what functional behavior is required.
2. Abstraction: The specification must describe what requirements the software product must satisfy, not how to satisfy them. In other words, it must focus on what candidate programs must do rather than how they must do it, the latter being the prerogative of the designer.

As a process (the process of identifying stakeholders, eliciting requirements, compiling them, etc.), a specification must meet two conditions, which are as follows:

1. Completeness: The specification must capture all the relevant requirements of the product.
2. Minimality: The specification must capture nothing but the relevant requirements of the product.

A specification that is deemed to be complete and minimal is said to be valid. In Sections 4.2 and 4.3, we will have an opportunity to discuss how to ensure the validity of specifications; in the remainder of this section, we introduce elements of relational mathematics, which we use throughout the book, starting in this chapter.

4.2.1 Sets and Relations

We represent sets using a programming-like notation, by introducing variable names and associated data type (sets of values). For example, if we represent set S by the variable declarations

x: X; y: Y; z: Z,

then S is the Cartesian product X × Y × Z. Elements of S are denoted in lower case s and are triplets of elements of X, Y, and Z. Given an element s of S, we represent its X component by x(s), its Y component by y(s), and its Z component by z(s). A relation on S is a subset of the Cartesian product S×S; given a pair (s,s′) in R, we say that s′ is an image of s by R. Special relations on S include the universal relation L=S × S, the identity relation I={(s,s′)| s′=s}, and the empty relation φ={}. To represent relations graphically, we use the Cartesian plane in which set S is represented on the abscissas (for s) and the ordinates (for s′). Using this device, we represent an arbitrary relation on S, as well as L, I, and φ in Figure 4.1.

4.2.2 Operations on Relations

Because a relation is a set, we can apply to relations all the operations that are applicable to sets, such as union (∪), intersection (∩), difference ( ∕ ), and complement . In addition, we define the following operations:

• The converse of relation R is the relation denoted by and defined by .
• The domain of relation R is the subset of S denoted by dom(R) and defined by .
• The range of relation R is the subset of S denoted by rng(R) and defined as the domain of .
• The (pre)restriction of R to (sub)set A is the relation denoted by _AR and defined by .
• The postrestriction of R to (sub)set A is the relation denoted by R_/A and defined by .

Figure 4.2 depicts a graphic illustration of a relation, its complement, and its converse.

Given a set A (subset of S), we define three relations of interest, which are as follows:

• The vector defined by A is the relation A × S.
• The inverse vector defined by A is the relation S × A.
• The monotype defined by A is the relation denoted by I(A) and defined by .

Figure 4.3 represents, for set A (a subset of S), the vector, inverse vector, and monotype defined by A.

Given two relations R and R′, we let the product of R by R′ be denoted by R•R′ (or RR′, if no ambiguity arises) and defined by . The Figure 4.4 illustrates the definition of relational product.

If we denote the vector and the inverse vector defined by A by, respectively, ω(A) and μ(A), then the following identities hold, by virtue of the relevant definition:

Vectors are a convenient (relational) way to represent sets, when we want everything to be a relation. Hence, for example, the domain of relation R can be represented by the vector RL, and the range of relation R can be represented by the inverse vector LR (Fig. 4.5).

Note that we can represent the prerestriction and the postrestriction of a relation to a set, say A, using the vector and inverse vector defined by A, as shown in the Figure 4.6.

4.2.3 Properties of Relations

Among the properties of relations, we cite the following:

• A relation R is said to be total if and only if RL = L.
• A relation R is said to be surjective if and only if LR = L.
• A relation R is said to be deterministic if and only if .
• A relation R is said to be reflexive if and only if .
• A relation R is said to be symmetric if and only if .
• A relation R is said to be transitive if and only if .
• A relation R is said to be antisymmetric if and only if .
• A relation R is said to be asymmetric if and only if .
• A relation R is said to be connected if and only if .
• A relation R is said to be an equivalence relation if and only if it is reflexive, symmetric, and transitive.
• A relation R is said to be a partial ordering if and only if it is reflexive, antisymmetric, and transitive.
• A relation R is said to be a total ordering if and only if it is a partial ordering and is connected.

The Figure 4.7 illustrates some of these properties.

4.3.1 REPRESENTING SPECIFICATIONS

If one asks junior computer science (CS) students in a programming course to write a C++ function that reads a real number and compute its square root, they would rush immediately to their computers to write code and run it; and yet this problem statement, despite being simple and short, leaves many questions unanswered. Consider that this statement may be interpreted in a wide range of manners, leading to a wide range of possible specifications, where space S is defined to be the set of real numbers:

1. Only nonnegative arguments will be submitted; the output is a (positive or nonpositive) square root of the input value:
   
2. Only non-negative arguments will be submitted; the output is the nonnegative square root of the input value:
   
3. Only nonnegative arguments will be submitted; the output is an approximation (within a precision ε) of a (positive or non-positive) square root of the input value:
   
4. Only nonnegative arguments will be submitted; the output is an approximation (within a precision ε) of the non-negative square root of the input value:
   
5. Negative arguments may also be submitted; for negative arguments, the output is −1; for nonnegative arguments, the output is a (positive or nonpositive) square root of the input value:
   
6. Negative arguments may also be submitted; for negative arguments, the output is −1; for nonnegative arguments, the output is the nonnegative square root of the input value:
   
7. Negative arguments may also be submitted; for negative arguments, the output is arbitrary; for nonnegative arguments, the output is an approximation (within a precision ε) of a (positive or nonpositive) square root of the input value:
   
8. Negative arguments may also be submitted; for negative arguments, the output is arbitrary; for nonnegative arguments, the output is an approximation (within a precision ε) of the non-negative square root of the input value:
   
9. Only nonnegative arguments will be submitted; the output must be within ε of the exact square root of the input (comparison with specification R₄: Precision ε applies to the square root scale rather than the square scale):

We could go on and on. This simple example highlights two lessons: First, the importance of precision in specifying program requirements and second, the premise that relations enable us to achieve the required precision.

As a second illustrative example, consider the following requirement pertaining to space S defined by an array a[1..N] of some type, where N is greater than or equal to 1, a variable x of the same type, and an index variable k, which we use to address array a: Search x in a and place its index in k . Again, this simple requirement lends itself to a wide range of interpretations, some of which we write as follows, along with their relational representation:

1. Variable x is known to be in a; place in k an index where x occurs in a.
   
2. Variable x is known to be in a; place in k the first (smallest) index where x occurs in a.
   
3. Variable x is known to be in a; place in k an index where x occurs in a, while preserving a and x.
   
4. Variable x is known to be in a; place in k the first (smallest) index where x occurs in a, while preserving a and x.
   
5. Variable x is not known to be in a; if it is not, place 0 in k; else place in k an index where x occurs in a.
   
6. Variable x is not known to be in a; if it is not, place 0 in k; else place in k the first (smallest) index where x occurs in a.
   
7. Variable x is not known to be in a; if it is not, place 0 in k; else place in k an index where x occurs in a, while preserving a and x.
   
8. Variable x is not known to be in a; if it is not, place 0 in k; else place in k the first (smallest) index where x occurs in a, while preserving a and x.

Note that F₁ can be written simply as since the clause is a logical consequence of . We draw the reader’s attention to the importance of carefully watching which variables are primed and which are unprimed in a specification. By writing F₁ as we did, we mean that the final value of k points to a location in the original array a where the original value of x is located. As written, this relation specifies a search program. If, instead of F₁, we had written the specification as follows:

then it would be possible to satisfy this specification by the following simple program:

{k=1; x=a[1];}

If, instead of F₁, we had written the specification as follows:

then it would be possible to satisfy this specification by the following simple program:

{k=1; a[1]=x;}

If, instead of F₁, we had written the specification as follows:

then it would be possible to satisfy this specification by the following simple program:

{k=1; x=0; a[1]=0;}

Neither of these three programs is performing a search of variable x in array a.

4.3.2 ORDERING SPECIFICATIONS

When we consider specifications on a given space S, we find it natural to order them according to the strength of their requirement, that is, some of them impose more requirements than others. Let us, for the sake of illustration, consider the specifications of the search program written in the previous section:

It is natural/ intuitive to consider that F₂ is stronger than F₁ since the latter would be satisfied with k′ pointing to any occurrence of x in a, while the former requires that k′ points to the smallest such occurrence. Also, it is natural to consider that F₃ is stronger than F₁ since the latter requires that a and x be preserved whereas the former does not; for the same reason, F₄ is stronger than F₂. On the other hand, F₅ can be considered stronger than F₁ since the latter makes provisions for the case when x is not in a, whereas the former does not; for the same reason, we can consider that F₆ is stronger than F₂, that F₇ is stronger than F₃, and that F₈ is stronger than F₄. These ordering relations are depicted in Figure 4.8.

We notice that F₂ and F₅ are both considered stronger than F₁, but while the former is a subset of F₁, the latter is a superset thereof. There appears to be two (nonexclusive) ways for a specification R to be considered stronger than a specification R′: by having a larger domain, and by having fewer images for elements in the common domain. Whence the following definition.

Henceforth, we use the term refines to refer to the property of being a “stronger’” specification. We admit without proof that the relation refines is a partial ordering between specifications, that is, that it is reflexive, antisymmetric, and transitive. We refer to this relation as the refinement ordering. The graph in Figure 4.9 shows two relations, R′ and R″, that refine relation R.

4.3.3 SPECIFICATION GENERATION

Let space S be defined by a real array a[1..N] and a real variable x and an index variable k. We are interested to write a relation to reflect the following requirement:

Place in x the largest value of a and in k the smallest index where the largest value occurs.

For example, if array a has the following values,

then we want x′to be equal to 9.4 and k′ to be equal to 4. Because it is too difficult to specify all the requirements at once, we consider them one by one:

1. Place in x a value larger than all the values in the array:
   
2. Place in x an element of the array (note that M₁ alone ensures that x′ is greater than all the elements of the array but does not ensure that it is the maximum: 500.0 could be a possible value, for the array aforementioned):
   
3. Place in k′ an index of a where the maximum of the array occurs:
   
4. Ensure that no index smaller than k′ carries the maximum of the array (hence ensuring that k′ is the smallest index):

Then we compute the overall specification as the intersection of M₁, M₂, M₃, and M₄, that is,

As a second example, we consider space S made up of three nonnegative real variables x, y, z, and a variable t that represents the enumerated type: {notri, scalene, isosceles, equilateral, right, rightisoceles}. We consider the following requirement:

Given that x, y, and z represent the sides of a triangle, place in t the class of the triangle represented by x, y, and z from the set {notri, scalene, isosceles, equilateral, rightisoceles, right}. We assume that the label “isosceles” is reserved for triangles that are isosceles but not equilateral and that the label ‘right’ is reserved for triangles that are right but not isosceles.

To write this specification, we write one relation for each type of triangle, then form their union. To this effect, we define the following predicates in triplets of real numbers:

Using these predicates, we define the following relations:

Using these relations, we form the relational specification of the triangle classification problem:

From these two examples, we want to discuss the question of how do we generate a complex specification from simple/ elementary specifications?

1. In the case of the specification that finds the maximum of the array, we compute the overall specification as the intersection of elementary specifications; in the case of the specification of triangle classification, we compute the overall specification as the union of elementary specifications.
2. It appears that we use the intersection when the domains of the elementary specifications are identical and we use the union when the domains of the elementary specifications are disjoint. In the former case we generate the compound specification as the conjunction of elementary properties; whereas in the latter case, we generate the compound specification by case analysis.

The question that we wish to address then is as follows: Given two relations R1 and R2 on space S, how do we compose them into a specification that captures all the requirements of R1 and all the requirements of R2 (for the sake of completeness) and nothing more (for the sake of minimality), assuming that the domains of R1 and R2 are neither (necessarily) identical nor (necessarily) disjoint? Consider the following graph depicting the configuration of dom(R1) and dom(R2) (Fig. 4.10).

If we want R to capture all the specification information of R1 and all the specification information of R2, then R has to be identical to R1 outside the domain of R2 and identical to R2 outside the domain of R1, and for each element of the intersection of the domains of R1 and R2, it has to be identical to the intersection of R1 and R2. This justifies the following definition.

This formula is a mere relational representation of the Figure 4.10, depicting how can be derived from R₁ and R₂ The following proposition, which we present without proof, gives an important property of the join operator.

The Figure 4.11 shows an example of two relations R₁ and R₂ that satisfy the compatibility condition and shows their join.

To check whether R₁ and R₂ verify the compatibility condition, we compute the following:

• .
• .
  • .
• .
  • .

Hence the condition is verified. Since R₁ and R₂ verify the compatibility condition, their join ( ) represents the least refined relation that refines them both. On input 1 (outside the domain of R₂), R behaves as R₁; on input 6 (outside the domain of R₁), R behaves like R₂; and on inputs {2,3,4,5} (the intersection of the domains of R₁ and R₂), R behaves like the intersection of R₁ and R₂ (which includes {(2,2),(3,3),(4,4),(5,5)}).

As a second example, consider the following relations R₁ and R₂ (Fig. 4.12).

In this case, R₁ and R₂ do not satisfy the compatibility condition since 4 belongs to the domain of each one of them but does not belong to the domain of their intersection. Indeed, it is not possible to find a relation that refines them simultaneously since R₁ assigns images 5 and 6 to 4, where R₂ assigns images 2 and 3; there is no value that R may assign to 4 to satisfy both R₁ and R₂.

4.3.4 SPECIFICATION VALIDATION

The software engineering literature is replete with examples of software projects that fail, not because programmers do not know how to write code or how to test it, but rather because analysts and engineers fail to write valid specifications, that is, specifications that capture all the relevant requirements (for the sake of completeness) and nothing but relevant requirements (for the sake of minimality). Consequently, it is important to validate specifications for completeness and minimality and to invest the necessary resources to this effect before proceeding with subsequent phases of the software lifecycle. In this section, we briefly and cursorily discuss the process of specification validation, in the narrow context of the relational specifications that we introduce in this chapter, with the modest goal of giving the reader some sense of what it may mean to validate a specification.

Let us start with a very simple illustrative example: We consider space S defined by natural variables x and y, and we consider the following requirement:

Increase x while preserving the sum of x and y.

We submit the following relations as possible specifications for this requirement:

We invite the reader to ponder the following questions: which of these specifications is complete; and for those that are complete, which are minimal. The following table shows our answers to these questions (if a specification is not complete, it makes no sense to check its minimality):

Specification	Complete?	Minimal?	Valid?
	No	N/A	No
	No	N/A	No
	Yes	No	No
	No	N/A	No
	Yes	Yes	Yes
	Yes	Yes	Yes
	Yes	No	No
	Yes	No	No

Specifications N₅ and N₆ are complete and minimal (and are identical, in fact); they specify that x must be increased while preserving the sum of x and y. Specifications N₁ and N₂ are not complete because they do not stipulate that x must increase (they allow it to stay constant); and specification N₄ is not complete because it fails to specify that the sum of x and y must be preserved. Specifications N₃, N₇, and N₈ are complete but not minimal because they specify by how much x must be increased, which is not stipulated in the requirement.

In the example aforementioned, we wrote the specifications on the basis of the proposed requirement (to Increase x while preserving the sum of x and y) and we judged the completeness and minimality of candidate specifications by considering the same source, that is, the proposed requirement. If the same person or group is tasked with generating the candidate specifications and judging their validity (completeness and minimality), then the same biases that cause the person to write invalid specifications may cause him/ her to overlook the invalidity of their specification. The only way to ensure a measure of confidence in the validation of the specification is to separate the team that generates the specification from the team that validates it. To this effect, we propose the following two-team, two-phase approach:

• The Specification Generation Phase: In the specification generation phase, the specification team generates the specification by referring to all the sources of requirements (requirements documents). Using the exact same sources, the validation team generates validation data that it intends to test the specification against. We distinguish between two types of validation data, which are as follows:
  • Completeness properties: These are properties that the specification must have but the validation team suspects the specification team may fail to record.
  • Minimality properties: These are properties that the specification must not have but the validation team suspects the specification team may record inadvertently. For the sake of redundancy, the specification team and the validation team must work independently of each other.
• The Specification Validation Phase: In the specification validation phase, the validation team tests the specification against completeness and minimality data generated in the previous phase, while the specification team updates the specification if it turns out that it was not complete or not minimal.

It remains to discuss the following: what form does the validation data take, and how does one test a specification against the generated validation data. The answers to these questions are given in the following definitions.

Implicit in this definition is that a good completeness property is one that has the potential to detect an incomplete specification; in other words, a good completeness property is one that the validation team believes the specifier team may have overlooked.

Implicit in this definition is that a good minimality property is one that has the potential to detect a nonminimal specification; in other words, a good minimality property is one that the validation team believes the specifier team may have inadvertently recorded in the specification.

Completeness and minimality are not absolute attributes but rather relative with respect to selected completeness and minimality properties, as provided in the following definition.

We admit without proof that if R refines all of V₁, V₂, …, V_n, then it refines their join. Hence, the range of valid specifications with respect to completeness properties and minimality properties is represented in the Figure 4.13.

As a illustrative example of specification validation, consider the following requirement pertaining to space S defined by an array a[1..N] of some type, a variable x of the same type, and an index variable k, which we use to address array a: Given that x is known to be in a , place in k the smallest index where x occurs. This is a variation of the example discussed in Section 4.2.1.

4.3.4.1 Specification Generation Phase

Examples of completeness properties include the following:

1. If each cell of array a contains the index of that cell and if x=1, then k′ should be 1.
   
2. If array a contains 1 everywhere and x=1, then k′ should be 1.
   
3. If array a contains the sequence 1..N in increasing order and x=N, then k′ should be N.

Examples of minimality properties include the following:

1. There is no requirement to preserve x.
   
2. There is no requirement to preserve a.

4.3.4.2 Specification Validation Phase

So far, we have looked at the requirements documentation, but we have not looked at candidate specifications; generating validation data independently of specification generation is important, for the sake of redundancy. Now, let us consider a candidate specification and check whether it is complete with respect to the completeness properties and minimal with respect to the minimality properties. We consider specification F₂, introduced in Section 4.2.1 as

To prove that F₂ refines V₁, we must prove that F₂ has a larger domain than V₁ and that the restriction of F₂ to the domain of V₁ is a subset of V₁. We find the following:

Clearly, V₁L is a subset of F₂L. We compute the restriction of F₂ to V₁L, and we find the following:

= {substitution}

= {simplification}

= {logic simplification}

= {logic simplification}

= {substitution}

We now consider the completeness property V₂. To prove that F₂ refines V₂, we must prove that F₂ has a larger domain than V₂ and that the restriction of F₂ to the domain of V₂ is a subset of V₂. We find the following:

Clearly, V₂L is a subset of F₂L. We compute the restriction of F₂ to V₂L, and we find the following:

= {substitution}

= {simplification, redundancy}

= {logic}

= {substitution}

We now consider the completeness property V₃. To prove that F₂ refines V₃, we must prove that F₂ has a larger domain than V₃ and that the restriction of F₂ to the domain of V₃ is a subset of V₃. We find the following:

Clearly, V₃L is a subset of F₂L. We compute the restriction of F₂ to V₃L, and we find the following:

= {substitution}

= {simplification}

= {logic}

= {simplification, redundancy}

= {substitution}

We turn our attention to checking the minimality of F₂ with respect to W₁ and W₂.

Because F₂ and W₁ have the same domain, the only way to prove that F₂ does not refine W₁ is to prove that is not a subset of W₁. To this effect, we compute the following:

= { F₂ and W₁ have the same domain}

which is not a subset of W₁. Hence F₂ is minimal with respect to W₁. We can prove, likewise, that it is minimal with respect to W₂. Indeed, F₂ does not preserve x, nor a.

4.5.1 A Relational Model

As we recall from our discussion in Section 4.1, specifications have to have two key attributes, which are formality and abstraction. We can achieve formality by using a mathematical notation, which associates precise semantics to each statement. As for abstraction, we can achieve it by ensuring that the specifications describe the externally observable attributes of candidate software products, but do not specify, dictate, or otherwise favor any specific design or implementation.

We consider the following description of a stack data type: A stack is a data type that is used to store items (through operation push()) and to remove them in reverse order (through operation pop()); operation top() returns the most recently stored item that has not been removed, operation size() returns the number of items stored and not removed, and operation empty() tells whether the stack has any items stored; operation init() reinitializes the stack to an initial situation, where it contains no elements. Imagine that we want to specify a stack without saying anything about how to implement it. How would we do it? Most data structure courses introduce stacks by showing a data structure made up of an array and an index into the array and by explaining how push and pop operations affect the array and its index; but such an approach violates the principle of abstraction since it specifies the stack by describing a possible implementation thereof. An alternative could be to specify the stack by means of an abstract list, along with list operations, without specifying how the list is implemented. We argue that this too violates the principle of abstraction as it dictates a preferred implementation; in fact, a stack does not necessarily require a list of elements, regardless of how the list is represented, as we show here.

• Consider that a stack that stores identical elements can be implemented by a simple natural number, say n:

  • init(): {n=0;}
    
    

  • push(a): {n=n+1;} // a is the only value that can be //stacked
    
    

  • pop(): {if (n>0) {n=n-1;}}
    
    

  • top(): {if (n>0) {return a;} else {return error;}}
    
    

  • size(): {return n;}
    
    

  • empty(): {return (n==0);}
    
    

• Consider that a stack that stores two possible symbols (e.g., ‘{’ and ‘}’) can also be implemented without any form of list, using a simple natural number, say n:

  • init(): {n=1;}
    
    

  • push(a): {n=2*n+code(a);} // where code(a) maps the two //symbols onto 0 nd 1. 
    

  • pop(): {if (n>1) {n=n div 2;}}
    
    

  • top(): {if (n==1) {return error;} else {return decode(n mod 2);}} // ecode() is the inverse of code().
    
    

  • size(): {return floor(log2(n));}
    
    

  • empty(): {return (n==1);}
    
    

• We can likewise implement a stack that stores any number (k) of symbols by using base-k numeration rather than base 2 (used earlier).

Hence, for the sake of abstraction, we resolve to specify the stack by describing its externally observable behavior, without making any assumption, regardless of how vague, about its internal structure. To this effect, we specify a stack by means of three parameters, which are as follows:

• An input space, say X, which includes all the operations that may be invoked on the stack. Hence, , where itemtype is the data type of the items we envision to store in the stack. We distinguish, in set X, between inputs that affect the state of the stack (namely, ) and inputs that merely report on it (namely, ).

  From the set of inputs X, we build the set of input histories, H, where an input history is a sequence of inputs; this is needed because the behavior of the stack is not determined solely by the current input but involves past inputs as well.

  • Hence, we introduce the set of input histories, .
• An output space, say Y, which includes all the values returned by all the elements of VX. In the case of the stack, the output space is as follows: , which correspond, respectively, to inputs top, size, and empty.
• A relation from H to Y, which represents the pairs of the form (h, y), where h is an input history and y is an output that the specifier considers correct for h. We denote this relation by stack and we use the notation stack (h) to refer to the image of h by stack (if that image is unique) or to the set of images of h by stack (if h has more than one image). We present here some pairs of the form (h, y) for relation stack:
  • .
  • .
  • .
  • .
  • .

We can go on describing possible input histories and corresponding outputs. In doing so, we are specifying how operations interact with each other but we are not prescribing how each operation behaves; this leaves maximum latitude to the designer, as mandated by the principle of abstraction.

It is clearly impractical to specify data types by listing elements of their relations; in the next section, we explore a closed-form representation for such relations.

4.5.2 AXIOMATIC REPRESENTATION

We propose to represent the relation of a specification by means of an inductive notation, where we do induction on the structure of the input history; this notation includes two parts, which are as follows:

• Axioms, which represent the behavior of the system for trivial input histories.
• Rules, which represent the behavior of the system for complex input histories as a function of its behavior for simpler input histories.

4.5.3 SPECIFICATION VALIDATION

In the previous section, we have written specifications of a number of ADTs, namely, a stack, a queue, and a set. How do we know that our specifications are valid, that is, that they capture all the properties we want them to capture (completeness) and nothing else (minimality)? To bring a measure of confidence in the validity of these specifications, we envision a validation process, similar to the process we advocated in Section 4.2.3, though this time (for the sake of simplicity) we focus solely on completeness. We imagine that while we are writing these specifications, an independent verification and validation team is generating formulas of the form

for different values of h and y, on the grounds that whatever we write in our specification should logically imply these statements. Then the validation step consists in checking that the proposed formulas can be inferred from the axioms and rules of our specification. If they do, then we can conclude that our specification is complete with respect to the proposed formulas; if not, then we need to check with the verification and validation team to see whether our specification is incomplete or perhaps the validation data is erroneous.

For the sake of illustration, we check whether our specification is valid with respect to the formulas written in Section 4.3 as sample input/output pairs of our stack specification:

For V₁, we find the following:

For V₂, we find the following:

For V₃, we find the following:

For V₄, we find the following:

For V₅, we find the following:

Because our specification has survived five tests unscathed, we gain a bit more confidence in its validity.