## TRADING PROPERTIES AND ALEXANDROV KERNELS FOR BOOLEAN FUNCTIONS |

**William Zwicker**

October 14, 1998

4:00 pm

Bailey Hall 207

Refreshments in the common room at 3:45 pm.

A Boolean function is simply a map f from {0,1}^n to {0,1}. It can be visualized as a switching circuit with n binary input switches and an indicater light, which glows if f(x) = 1 and is dark if f(x) = 0. Monotonic Boolean functions are nothing other than simple games, but their study is associated with a distinct set of intuitions and questions. In the course of answering a question of P. Hammer, we show how "trading properties" from simple games can be adapted to the nonmonotonic context. We also demonstrate how a number of these trading properties (some new and some old) are tied to each other via three "kernel operations" of the Alexandrov topology. These kernel operations arise from three different ways of tampering with a switching circuit: switching the 0-1 labels on some input switches ("renaming"), ganging certain sets of input switches to operate as single switches ("Rudin-Keisler projection"), and welding some input switches into fixed positions ("Boolean subgame"). The talk is based on joint work with Alan Taylor.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Tue Oct 23 07:20:28 EDT 2018 |