Sp21 CSCI 2010-91Discrete Mathematical Structures

The objective of this lab is for the student to exercise propositional logic and elementary proofs by programming.

Refer to notes posted for weeks 6 and 7, as well as textbook chapters 3 and 4, and Appendix A.

Tasks (equally weighted in scoring):

1. Write a program in SML, Forth or SQLite to evaluate the logical expression in textbook exercises 3.2.1 and 3.2.2 (p. 100 of the textbook), in a so called brute force manner.

For example, exercise 3.2.3 is to evaluate ~T F T T. Your program uses all combinations of 1s and 0s instead of these Ts and Fs and generates a truth table. With four bits, your program can evaluate all possible combinations of expressions in a table, like the following:

0 0 0 0 ex: ~0 0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1 ex: ~0 1 0 1 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0 ex: ~1 0 1 0 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1 ex: ~1 1 1 1 1

Note that in SML, a value of true signifies boolean true and a value of false signifies boolean false. So, you will need to accommodate that condition. Having SML evaluate these expressions on the fly using its boolean operators will save you time. (You should verify some of the results against your own logic.)

SQLite uses 0 for false and 1 for true, so the true/false bit states are readily represented. In Forth, any number value other than 0 is true.

Use a function in SML (or a word in Forth) to process all these bit sets. For example, define a function that takes as an argument a list of bits... a row from the table. Then call that function inside of a loop so as to evaluate each row.

Repeat the above task for:

2. Exercises 3.2.5 and 3.2.6.

3. Any two exercises from 3.4.5 to 3.4.9.

4. Any two exercises from 3.4.10 to 3.4.14.

5. One of the following exercises: 4.2.1, 4.5.1 or 4.6.1.

6. In each exercise above, prove using logic, putting your logical proof with in code comments near the top of each program. Multi-line code comments in SML and Forth can be contained such as (* comment *). In SQLite, comments can be contained such as /* comment */

7. Non-function option: If you chose to not use functions for the above operations, then you must laboriously enter many print statements (like lab 2 part A) or use SQLite to process a four-column table like the one above (Creating a function in SQLite is not necessary). If you chose this option, then you must additionally complete exercises 3.2.3 and 3.2.4, all with evaluation on bits.

8. Extra credit (10%): Integrate SQLite into at least one of your SML or Forth programs, so that functions rely on SQLite to store and retrieve data. See the file IO discussion in the overview notes for ideas. Also see 8th's built-in SQLite API documentation in the 8th manual and word reference.

What to upload

Along with the code for each set operation, provide the output. You can copy and paste output into a file, or use the command line to generate an output file as follows:

sml < lab_4-1.sml > lab_4-1_output.txt

Put all relevant files in a zipped folder called:

YOUR_NAME_lab4.zip

Upload on D2L: Assignments / lab_4

FAQs

Q: How do you evaluate 4 arguments while in the book it's always 2, with p and q as true or false. Do I need to process every row according to logic ~T v F ^ T v T. For row 1 the program has to output ~0 v 0^ 0 v 0?

A: In exercises with many arguments such as p, q, r, s, ... you can group pairwise, such as:

(p v q) v (r v s)

Symbolically, each pair represents p and q. p can be 0 or 1 and q can be 0 or 1. Such pairwise processing corresponds with list processing in SML, as functions process the head and tail parts of a list as we have seen.

Q: For row 1 the program has to output ~0 v 0 ^ 0 v 0? Am I understanding this right?

A: That is correct. But, print both the bit expression and its evaluation.

Q: How should I work the bit combinations into the solution when exercise 3.2.1 is T^(~FvF)^(TvT)?

A: Instead of the T and F, use all the different bit combinations, with 1s and 0s. For example:

1 1 1 1 1 evaluates as 1 ^ (~1 v 1) ^ (1 v 1) == 1 ^ (0 v 0) ^ (1 v 1) == 1 ^ 0 ^ 1 == 1 == T

0 0 0 0 0 evaluates as 0 ^ (~0 v 0) ^ (0 v 0) == 0 ^ (1 v 0) ^ (0 v 0) == 0 ^ 0 ^ 0 == 0 == F

0 0 0 1 1 evaluates as 0 ^ (~0 v 0) ^ (1 v 1) == 0 ^ (1 v 0) ^ (1 v 1) == 0 ^ 0 ^ 1 == 1 == T

Make sure your code does the above statement evaluations. For example:

val T = true; val F = false; val result = F orelse F; false.

Do similar for the SQLite.

Q: How can a variable be both bool and int in SML?

A: They cannot. int and bool are different data types in SML. The challenge is to write a program that evaluates the expressions specified. To do so, consider 1 to be true and 0 to be false.