[CSUSB] >> [CompSci] >> [Dick Botting] >> [CS656/556 Course Materials] >> class/06
[Index] || [Contents] || [Grades] Mon Mar 3 14:43:01 PST 2003
Admin
Last day to drop
Assigned work.  Translate P->Q into a C/C++/Java Condition.
Clue:  Find the right C/C++/Java operator to
fill in the blank:  P __ Q
Hint (11:38am Monday):   Try the relational operators: < <= >= >.

ch1.5 Normal Forms
Problem:  Need faster/simpler ways to work with complex conditions.
Can this proposition be true?  		= Satisfiable
Is this proposition ever false?		= Valid
Are these two propositions equivalent?
Do these propositions entail this conclusion?
Note.
\phi is not valid iff (~\phi) is satisfiable.
\phi is valid iff (~\phi) is not satisfiable.
(~\phi) is not valid iff _____ satisfiable
(~\phi) is valid iff _____ satisfiable
CNF
Simple test for validity: all conjuncts have p \/ ~ p in them.
From truth tables. take each row with an F and write down with \/. Then /\.
Algorithms
DNF
Simple test for satifiable
From truth tables. take each row with an T and write down with /\. Then \/.
DNF maps into And/Or Tables
Semantic Tableax generate DNF
Horn Clauses/Horn Form
Discounts'RUs Example is in Horn Form.
Algorithm.
Basis of Prolog.

Assigned work for next time: Page 84, Exercises 1.14. #1(c).

Lab: Change your truth table program
into one that tests the Discount'RUs requirements:
http://www.csci.csusb.edu/dick/cs656/discounts.html#requirements
For each possible combination
of p, q, and r, take each requirement in turn, and if the
condition holds print out the three p,q, r values and the
discount value.

Here might be the first 3 lines:
p	q	r	discount(%)
0	0	0	0
0	0	1	5

Notice: Anything between 0 and 5 lines might be printed for
each set of p, q, and r values.

next
Chapter 6.1 OBDDs

http://www.csci.csusb.edu/dick/cs656/class/07.html