>> [CS656/556 Course Materials]
Mon Mar 3 14:43:01 PST 2003
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?
\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
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 /\.
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.
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:
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
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.
Chapter 6.1 OBDDs