8 Problem (20 points)

A logical expression is in “conjunctive normal form” (CNF) if it is the conjunc- tion of many different “clauses,” where every clause is the disjunction of one or more simple propositions called “terms.” For example, the following expression is in CNF:

(a∨b∨c)∧(¬a∨d)∧(b∨f ∨¬g)... The following clause has two terms:

(¬a∨d) The following clause has four terms:

(w ∨x ∨y ∨z) 7

In a later course in this department, you will learn that any logical expression can be converted (with the addition of some “temporary” variables), into CNF. For this reason, reasoning about CNF expressions is an interesting way to reason about logical expressions in general.

You are a computer programmer, and you have been assigned the task of writing a program which will generate new clauses which can be deduced from the existing clauses in a CNF expression. The only operation that you will perform is to take two clauses (from the original formula and/or new ones you have derived), and use the Rule of Inference of “Resolution” on them:

a∨b ¬b∨c ∴a∨c

After performing Resolution, your program may optionally perform opti- mizations (such as removing duplicate terms), but it must never add new terms which did not already exist - doing so would create a new expression which is not logically equivalent to the first!

So, for example, given the clauses (a∨b∨c),(¬c∨d∨e), your program would generate a new clause (a∨b∨d∨e).

Part (a) - (10 points)

Give a proof of the following theorem:

Theorem 6. If two clauses, one with x terms and one with y terms, are com- bined using Resolution to form a new clause, the new clause will have at most x+y−2 terms.

Proof. TODO: write your proof here

Part (b) - (10 points)

Give a proof of the following theorem:

Theorem 7. If a logical expression starts out made up entirely of clauses with two or fewer terms, then the computer program (which generates new clauses) will never generate a clause with three or more elements.

Proof. TODO: write your proof here

9 Problem (25 points)

Consider the set R+ of positive real numbers. Define a new kind of “addition,” ⊕, and “multiplication,” ⊗, on this set as follows: for any two elements x, y ∈ R+, define x ⊕ y = xy and x ⊗ y = xlny.

Prove the following two theorems. Hint: a direct proof is possible for each.

Part (a) - (10 points)

Theorem 8. The new addition is commutative. That is, a ⊕ b = b ⊕ a.

Proof. TODO: write your proof here

Part (b) - (15 points)

Theorem 9. The new multiplication distributes over the new addition. That is, a⊗(b⊕c) = (a⊗b)⊕(a⊗c).

Proof. TODO: write your proof here

Subject | Mathematics |

Due By (Pacific Time) | 07/08/2014 12:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |