CS486 Applied Logic Assignment 9 Due Thurs, April 19, 2001

Reading: Please read The Foundations of Mathematics, by Stewart & Tall, to page 80. Most of this is a review.

Exercises:

1. Monoids

A monoid is an algebraic structure with one operation, op, which is associative and has a unit element, 1, such that

x op 1 = x and 1 op x = x.

Say that a monoid is commutative iff x op y = y op x, and is idempotent iff x op x = x.

(a) Write the axioms for a commutative idempotent monoid using first-order logic.

Prove or disprove using first-order logic that:

(b) The unit element of a monoid is unique.

(c) An idempotent monoid is commutative.

2. Boolean Rings

(a) A Boolean ring R is a ring (with unit) such that x * x = x for all x Î R. Show that any Boolean ring is commutative, i.e.,
x * y = y * x for all x, y Î R.

(b) Define x + y as x Û y, -x as x, and x * y as x Ú y.

Take 0 as true (T) and 1 as false (^).

Show that with these definitions the class of propositions, Prop, is a Boolean ring. Use the truth definition to prove properties of the logical connectives and constants.

Note, you need not express this in first-order logic.

3. Problem 7, page 82, in Stuart & Tall.