UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments Yung, Ho Sen

Abstract

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.

Item Media

Item Citations and Data

Rights

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.

Usage Statistics