Open Collections

The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments

University of British Columbia

Denoting the length of a shortest disjunctive normal form of a Boolean function / by l(f), this thesis provides a way to express l(f) in terms of l(g) for some Boolean function g with no more arguments than f and with the same number of zeros as f . This method is useful for finding the shortest disjunctive normal forms of Boolean functions f with few zeros. It also gives explicitly the values of l(f) for f with three or fewer zeros, and some bounds for l(f) for a certain class of Boolean functions f . For n much larger than k, the zeros of a Boolean function f of n arguments with k zeros have the property that for some large subsets P = {i₁,i₂,…,i[sub d]} of {1,2,..., n} and 1 ≤ c ≤ d, all k zeros s satisfy Si₁ = Si₂ = ... = Si[sub c] = Si[sub c]+1 = Si[sub c]+2 = ... = Si[sub d]. Thus, one may consider all dimensions in each P as a single dimension and construct a corresponding Boolean function g with fewer arguments.

Thesis/Dissertation

application/pdf

2009-08-17

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/12280

Computer Science

University of British Columbia

UBCV

DSpace