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.