# Presentation: 813876

## Disciplined Software Engineering Lecture #9

**Watts S. Humphrey**
**Software Engineering Institute**
**Carnegie Mellon University**
**Pittsburgh, PA 15213**
**Sponsored by the U.S. Department of Defense**

## Design Notation - Overview

**The importance of notation**
**Boolean algebra**
**Karnaugh maps**
**useful symbols**
**using Boolean functions**
**Simplification**
**Formal methods**

## The Importance of Notation 

**Many software development defects are caused by misunderstandings and confusion.**
**The notation used to represent program requirements and designs should be**
**precise and concise**
**convenient to use**
**commonly understood**
**suitable for representing a broad range of software functions**
**Formal notations meet these criteria.**

## Class Properties- Mathematical Notation

**English****	****	****	****Symbol****	****                Example**
**Union, sum****	****	****	****	****A or B, A+B**
**Intersection, product****	****	****	****A and B, A*B, AB**
**Complement, not****	****	****      '****	****	****A', not A**
**All, universal****	****	****     1**
**None, empty set****	****	****     0****	****	****	****	****	****	**

## Using This Notation 

**Advantages**
**builds familiarity with an important notation**
**consistent with the notation used in formal methods for proving program correctness**
**distinguishes logic from other expressions**
**Disadvantages**
**generally takes more time to enter**
**will take practice to build familiarity**
**your coworkers may not understand it**

## Boolean Algebra

**The algebra of classes**
**defines and manipulates class relationships**
**consistency - whether statements are self-    consistent**
**validity - whether statements represent reality **
**Class representations**
**Venn diagrams**
**basic relationships**
**the universal and empty sets**

## Venn Diagrams

**Humans**

**Men**

**Women**

**Humans**

**Non-adult**
**Women**

**Adult**
**Women**

**Adult**
**Men**

**Non-**
**adult**
**Men**

**A’B’C’**

**Universal Class**

**AB’C’**

**A’BC’**

**A’B’C**

**AB’C**

**A’BC**

**ABC**

**ABC’**

## Properties of Classes - 1

**Reflexive:          for every x, x<=x**
**Idempotent:      xx=x, x+x=x**
**Antisymmetric: if x<=y and y<=x then x=y**
**Transitive:         if x<=y and y<=z then x<=z**
**Commutative:   xy=yx, x+y=y+x**
**Associative:      x(yz)=(xy)z, x+(y+z)=(x+y)+z**
**Distributive:      x(y+z)=xy+xz, x+yz=(x+y)(x+z)**

## Properties of Classes - 2

**Empty and universal classes:**
**                           ****xx’=0, x+x’=1, 0<=x<=1**
**                           ****x0=0, x+1=1, x+0=x, x1=x**
**Consistency:     x<=y, xy=x, x+y=y **
**                           ****are equivalent**
**Absorption:       x(x+y)=x+xy=x**
**DeMorgan’s theorem:**
**                           ****(x’)’=x, (xy)’=x’+y’, (x+y)’=x’y’**

## An Example

**Suppose you had a switch that you wanted to be on under the following conditions**
**A or B or C are on**
**not when A and B are on**
**not when A and C are on**
**You would represent this as follows**
**On = (A+B+C)*[(A*B)+(A*C)]’**

## Simplifying Boolean Expressions

**Consider the following guidelines when you  simplify Boolean expressions**
**if there are any primed parenthetical expressions, use DeMorgan’s theorem to remove them**
**look for common terms that can be factored by the distributive law**
**make substitutions to reduce complexity**
**attempt to reduce expressions to a union of intersections**

## Simplification Example - 1

**Use the light bulb example**
**   ****On = (A+B+C)*[(A*B)+(A*C)]’ **
**Apply DeMorgan’s theorem**
**   ****On = (A+B+C)*[(A’+B’)*(A’+C’)]**
**Now, A’ is common to the last terms so**
**   ****On = (A+B+C)*[A’+(B’*C’)]**
**Now, substitute x for B+C, and x’ for B’*C’**
**   ****On = (A+x)*(A’+x’)**

## Simplification Example - 2

**While this expression is fully simplified, it should be converted to a union of intersections**
**On = (A+x)*(A’+x’)**
**On = [(A+x)*A’]+[(A+x)*x’]**
**On = [(A*A’)+(x*A’)]+[(A*x’)+(x*x’)]**
**On = (x*A’)+(A*x’)**
**Now, replacing x with B+C**
**On = [(B+C)*A’]+[A*(B’*C’)]**
**On = (A*B’*C’)+[A’*(B+C)]**

## Simplification Exercises

**Simplify the following expressions**
**1.  F = X+(X’*Y)**
**2.  F = (X+Y)+[(X*Z)+Y]**
**3.  F = (X’*Y’*Z’)+(X*Y*Z’)+(X*Y’*Z’)**
**4.  F = [X’*(Y+Z’)]’*(X+Y’+Z)*(X’*Y’*Z’)’**

## Exercise 1 Answer

**Starting with  F = X+(X’*Y)**
**Use the distributive law**
**     ****F = (X+X’)*(X+Y)**
**Now, with the property of the universal class**
**     ****X+X’ = 1 AND 1*(X+Y) = X+Y**
**So the answer is**
**     ****F = X+Y**

## Exercise 2 Answer

**Starting with F = (X+Y)+[(X*Z)+Y],**
**Apply the distributive law to give**
**    ****F = (X+Y)+(X+Y)*(Z+Y)**
**Now, factor out the common X+Y term**
**    ****F = (X+Y)*[1+(Z+Y)]**
**By the property of the universal class, 1+Z+Y=1**
**so the answer is**
**    ****F = X+Y**

## Exercise 3 Answer

**Starting with F = (X’*Y’*Z’)+(X*Y*Z’)+(X*Y’*Z’)**
**Factor out the common Z’ term**
**   ****F = Z’*(X’Y’+XY+XY’)**
**Factoring out the common X term**
**   ****F = Z’*[X’Y’+X(Y+Y’)] = Z’*(X’Y’+X)**
**Now, with the distributive law**
**   ****F = Z’*(X’+X)*(Y’+X) = Z’*(Y’+X)**

## Exercise 4 Answer

**Starting with F = [X’*(Y+Z’)]’*(X+Y’+Z)*(X’*Y’*Z’)’**
**First apply DeMorgan’s theorem, giving**
**   ****F = (X+Y’Z)*(X+Y’+Z)*(X+Y+Z)**
**Factoring out the common X term gives**
**   ****F = X+Y’Z*(Y’+Z)*(Y+Z)**
**Factoring out the common Z term**
**   ****F = X+Y’Z*(Z+Y’Y) = X+Y’Z**

## Karnaugh Maps - 1

**For expressions of 6 variables or less, Karnaugh maps can aid the simplification process.**
**Karnaugh maps are a structured way to represent all possible combinations of the variables in an expression.**
**Factoring is then done by associating related terms to achieve simplification.**

## Karnaugh Maps - 2

**Boolean expressions can be represented in minterm form.**
**The minterms are the products of the variables in all possible combinations.**
**The minterms for X and Y are:**
**   ****X’*Y’, X*Y’, X’*Y, XY**
**There are 2**n minterms for n variables.**

## Karnaugh Maps - 3

**X**

**YZ**

**00       01      11       10**

**0**

**1**

**XY’**

**X**

**X**

**00       01      11       10**

**0**

**1**

**X’Z**

**X**

**X**

**X**

**YZ**

**00       01      11       10**

**0**

**1**

**X**

**X**

**X**

**YZ**

**X**

**X**

**XY’+X’Z**

## A 4-Variable Karnaugh Map

**WX**

**00       01      11       10**

**00**

**01**

**X**

**X**

**11**

**10**

**X**

**X**

**YZ**

**X**

**X**

## A 5 Variable Karnaugh Map

**110      111    101     100**

**VW**

**000      001     011    010**

**00**

**01**

**11**

**10**

**XYZ**

## Map Factoring - 1

**When two adjacent cells both have 1s, then those cells can be factored, eliminating the variable that is different for the two cells.**
**For example, the 0100 and 0101 cells can be factored, eliminating the variable z.**
**This is shown on the following map.**

## Map Factoring - 2

**WX**

**00       01      11       10**

**00**

**01**

**X**

**X**

**11**

**10**

**X**

**X**

**YZ**

**X**

**X**

## Map Factoring - 3

**Similarly, when four adjacent cells have 1s, then those cells can be factored, eliminating the two variables that are different for the four cells.**
**For example, the 0101, 0111, 1101, and 1111 cells can be factored, eliminating the variables w and y.**
**This is shown on the following map.**

## Map Factoring - 4

**WX**

**00       01      11       10**

**00**

**01**

**X**

**X**

**11**

**10**

**X**

**X**

**YZ**

**X**

**X**

## Map Factoring - 5

**When all three of the possible factorings are made, the resulting expression is**
**F = w’yz + w’xy’ + xz**
**This is shown on the following map.**

## Map Factoring - 6

**WX**

**00       01      11       10**

**00**

**01**

**X**

**X**

**11**

**10**

**X**

**X**

**YZ**

**X**

**X**

**W’YZ+W’XY’+XZ**

## Simplification Exercises

**Using Karnaugh Maps, simplify the following expressions**
**1.  F = X+(X’*Y)**
**2.  F = (X+Y)+[(X*Z)+Y]**
**3.  F = (X’*Y’*Z’)+(X*Y*Z’)+(X*Y’*Z’)**
**4.  F = [X’*(Y+Z’)]’*(X+Y’+Z)*(X’*Y’*Z’)’**

## Exercise 1 Answer

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****0**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**The function is F = X+(X’*Y)**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****0**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**Factoring this gives**
**F = X+Y**

## Exercise 2 Answer

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****0**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**The function is **
**F = (X+Y)+[(X*Z)+Y]**
**   ****= X+Y+XZ+Y**
**   ****= X+Y+XZ**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****0**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**Factoring this gives**
**F = X+Y**

## Exercise 3 Answer

**00       01      11       10**

**0**

**1**

**0**

** ****1**

** ****0**

** ****0**

** ****0**

**1**

** ****0**

**  ****1**

**X**

**YZ**

**The function is **
**F = (X’*Y’*Z’)+(X*Y*Z’)+(X*Y’*Z’)**
**   ****= X’Y’Z’+XYZ’+XY’Z’**

**00       01      11       10**

**0**

**1**

**0**

** ****1**

** ****0**

** ****0**

** ****0**

**1**

** ****0**

**  ****1**

**X**

**YZ**

**Factoring this gives**
**F = Y’Z’+XZ’**
**   ****= Z’(Y’+X)**

## Exercise 4 Answer - 1

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****0**

** ****0**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**The function is **
**F = [X’*(Y+Z’)]’*(X+Y’+Z)*(X’*Y’*Z’)’**
**   ****= (X+Y’Z)*(X+Y’+Z)*(X+Y+Z)**
**This can be covered in 3 maps.**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**X+Y’Z**

**00       01      11       10**

**0**

**1**

**1**

** ****1**

** ****1**

** ****1**

** ****0**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**X+Y’+Z**

**X+Y+Z**

## Exercise 4 Answer - 2

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****0**

** ****0**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**The total function is the product**
**of these maps, or a map with 1s**
**where all 3 maps have 1s and 0s**
**elsewhere.  This is**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****0**

** ****0**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**Factoring this map gives the answer**
**F = X+Y’Z**

## Factoring Zeros

**When factoring 1s, the 1s on a map are covered.  This gives the minterm form of the expression.**
**The same map can be factored by covering the 0s and then applying DeMorgan’s Theorem.**
**This gives the maxterm form of the expression, or the intersection of unions.**

## Example of Zeros Factoring

**The following map could be factored **
**by covering 1s as follows, giving**
**F = X+Y+Z **

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****1**

** ****1**

**1**

** ****1**

**  ****1**

**X**

**YZ**

**Covering the 0s, however, gives**
**F’ = X’Y’Z’ **
**Applying DeMorgan’s**
**Theorem gives the answer**
**F = X+Y+Z**

## Another Factoring Example

**The following map could be factored **
**by covering 1s as follows, giving the**
**minterm result**
**F = XY’+X’Y+Z **

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****1**

** ****1**

**1**

** ****1**

**  ****0**

**X**

**YZ**

**00       01      11       10**

**0**

**1**

**1**

** ****0**

** ****1**

** ****1**

** ****1**

**1**

** ****1**

**  ****0**

**X**

**YZ**

**Covering the 0s, however, gives**
**F’ = X’Y’Z’+XYZ’ **
**Applying DeMorgan’s**
**Theorem gives the answer in**
**maxterm form**
**F = (X+Y+Z)*(X’+Y’+Z)**
**   ****= (X+Y)*(X’+Y’)+Z**

## Factoring Out Zeros

**Sometimes, a 1s factoring will be complicated by one or two badly placed 0s.  This can be handled as follows**
**Factor the map as if the inconvenient 0s were 1s.**
**Then, treating each of these factors as a small map, factor out the 0s.**

## Factoring Out 0s Example - 1

**WX**

**00       01      11       10**

**00**

**01**

**1**

**1**

**11**

**10**

**1**

**0**

**YZ**

**0**

**1**

**1**

**0**

**0**

**1**

**1**

**0**

**1**

**1**

**1**

**0**

**Except for two inconvenient**
**0s, this map has a very**
**simple factoring**
**F = Y’+W’Y = Y’+W’**

**Because of the 0 at**
**W’X’Y’Z’ and the 0**
**at W’XYZ, however,**
**we must factor out**
**0s.**

## Factoring Out 0s Example - 2

**WX**

**00       01      11       10**

**00**

**01**

**1**

**1**

**11**

**10**

**1**

**0**

**YZ**

**0**

**1**

**1**

**0**

**0**

**1**

**1**

**0**

**1**

**1**

**1**

**0**

**The first factor, Y’,**
**creates the mini map**
**in the variables W, X,**
**and Z.  On this map,**
**W’X’Z’ is factored out:**
**F1 = Y’*(W’X’Z’)’**
**     ****= Y’*(W+X+Z)**
**This factoring is essentially**
**Y’ and not W’X’Z’.**

**The second factoring is**
**F2 = W’Y*(XZ)’**
**     ****= W’Y*(X’+Z’)**
**So the function is**
**F = Y’*(W+X+Z)+W’Y*(X‘+Z’)**

## Factoring With More Variables

**Karnaugh maps are possible with up to 6 variables.  Beyond that, special tricks are needed.**
**If the expression involves 6 or fewer variables in most of the terms with an occasional additional variable, an approach much like factoring out 0s can be used.  **
**This method is called exception factoring and can be used with any number of variables.**

## Exception Factoring - 1

**To factor the following function on a 4-variable Karnaugh map**
**   ****F = AX’Y’+WXY’+W’Y’Z+XY’Z+W’XY’Z’+WX’Y’**
**1.  Construct the function, using the variables**
**     ****W, X, Y, and Z.**
**2.  For the term with the A, instead of 1, enter an **
**     ****A in that square.**
**3.  In factoring out zeros, treat A as A+0.**

## Exception Factoring - 2

**WX**

**00       01      11       10**

**00**

**01**

**1**

**1**

**11**

**10**

**1**

**0**

**YZ**

**0**

**0**

**1**

**0**

**0**

**1**

**1**

**0**

**0**

**0**

**1**

**0**

**First, construct the map, using**
**only the terms containing W,**
**X, Y, and Z.**

**F1 = WXY’+W’Y’Z+XY’Z+W’XY’Z’+WX’Y’**

**WX**

**00       01      11       10**

**00**

**01**

**0**

**0**

**11**

**10**

**0**

**0**

**YZ**

**0**

**0**

**0**

**0**

**0**

**A**

**A**

**0**

**0**

**0**

**A**

**A**

**Next, enter the A term.  Put an A**
**wherever there are 0s and nothing**
**where there is a 1.**

**F2 = AX’Y’**

## Exception Factoring - 3

**WX**

**00       01      11       10**

**00**

**01**

**1**

**1**

**11**

**10**

**1**

**0**

**YZ**

**0**

**0**

**1**

**0**

**0**

**1**

**1**

**0**

**0**

**0**

**1**

**A**

**First, factor out the 1s, assuming**
**the A was a 1**
**F1 = Y’**
**Next, factor out the A term, treating**
**it as A+0**
**F = Y’*[A+(W’X’Z’)’]**
**   ****= Y’*(A+W+X+Z) **

## Other Useful Symbols

**The following basic mathematical symbols are also useful in defining programming functions.**
**           ****-  means “is a member of the set”**
**           ****-  means “is not a member of the set”**
**           ****-  means “for all members of the set”**
**           ****-  means “there exists a member of the **
**              ****set”**

##  Notation Examples 

**To update a file when dataset D is a member of the file**
**(D    File) :: Update**
**To add a number x(i), when every number i is an even integer**
**     ****i when (i     even) :: add x(i)**
**To clear a register when any number n is negative**
**      ****i when (i < 0) :: Clear**

## Function Completeness

**A set of functions is complete if it covers all possible conditions.**
**For a complete set of functions, the Karnaugh map for the sum (or union) of the functions covers all map positions.**
**There may be multiply-covered map positions.**

## Function Orthogonality

**A set of functions is orthogonal if no two functions cover the same conditions.**
**This means that the product (intersection) of any function with any other function is zero.**
**     ****i, j where (i   j) => F(i)*F(j) = 0 **
** **
**The map may not be completely covered.**

## Complete and Orthogonal

**A set of functions is complete and orthogonal if **
**the functions cover all elements **
**no two functions cover the same elements**

## Complete and Orthogonal Functions

**f, g, h are orthogonal**

**00       01      11       10**

**0**

**1**

**f**

**00       01      11       10**

**0**

**1**

**f**

**g**

**f, g, h are complete**

**00       01      11       10**

**0**

**1**

**f**

**g**

**f, g, h are complete and orthogonal**

**h**

**g**

**f**

**g**

**gh**

**fh**

**g**

**fh**

**fg**

**h**

**g**

**f**

**f**

**h**

**f**

**h**

## Formal Methods - 1

**Formal methods for software design have been developed based on mathematical concepts**
**The premise of formal methods is that**
**computer programs can be treated as  mathematical statements**
**the principles of mathematics thus apply**
**the design of a correct program can then be    treated as a theorem derivation**
**the use of mathematically rigorous methods should thus produce correct programs.**

## Formal Methods - 2

**Formal methods typically use a program precondition, a program postcondition, and a program invariant.**
**The program then transforms the precondition to the postcondition while preserving the invariant.**
**To prove program correctness**
**prove that the program transforms the    preconditions to the postconditions**
**and preserves the invariants**

## Formal Methods - 3

**To formally develop a new program**
**start with a postcondition **
**derive the precondition**
**determine the invariants**
**   **
**Define a program that transforms the precondition to the postcondition and preserves the invariants.**
**If the program involves iteration, each cycle  should progress toward loop termination.**

## The Pros of Formal Notations

**They are precise.**
**They can compactly represent complicated functions.**
**They form a foundation for learning formal methods.**

## The Cons of Formal Notations

**They take time to learn.**
**They take more time to build the familiarity    needed to use them for design.**
**Your associates may not understand them. **

## Formal Methods in This Course

**Adherents claim formal methods provide a rigorous way to develop quality software.  Sceptics argue that they are not cost effective.**
**While formal methods show promise, their general use will require**
**user training**
**users who make fewer errors with formal proofs than they do in software design**
**Formal methods are not treated further in this course.**

## Formal Method Suggestions - 1

**If you are familiar with or trained in formal methods**
**use them with your PSP**
**measure your quality and productivity**
**compare your results to others who use such    methods**
**compare your results to your results when you do not use formal methods**
**decide if these methods are effective for you **
**Tell others what you find.**

## Formal Method Suggestions - 2

**If you are not familiar with formal methods, consider them**
**ask users to show you their data**
**take a course or study the references**
**try them for yourself**
**  **
**Measure your quality and productivity before and after and decide if they are effective for you.**
**Tell others what you find.**

## Assignment #9

**Read appendix B in the text and work through the examples**
**Using PSP2, write program 8A to sort a linked list of N real numbers into ascending order.  **
**Read the program specifications in Appendix D and the PSP2 description in Appendix C.  Follow the assignment specifications in Appendix C.**

## Messages to Remember from Lecture 9 - 1

**1.  A poor design notation is a source of error.**
**2.  By using a defined and rigorous notation, **
**     ****you can improve the quality of your designs **
**     ****and eliminate defects.**

## Messages to Remember from Lecture 9 - 2

**3.  Select and use an appropriate notation from **
**     ****among those available.**
**4.  Try formal methods in your software **
**     ****development and see if they work for you.**