Up: Research Seminars for 1998
Top: Math Department Research Seminars

TRADING PROPERTIES AND ALEXANDROV KERNELS FOR BOOLEAN FUNCTIONS

by

William Zwicker

October 14, 1998
4:00 pm
Bailey Hall 207

Refreshments in the common room at 3:45 pm.


Abstract:

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.
Up: Research Seminars for 1998
Top: Math Department Research Seminars

[HOME]
Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Fri Apr 20 00:45:42 EDT 2018