×

Learning and testing of properties of Boolean functions. (Chinese. English summary) Zbl 1265.06040

Summary: A concept is decided by a subset of attributes, where a Boolean function presents a concept. A given property \(P\) corresponds to a class \(C\) of Boolean functions with the property \(P\). The decision problem whether or not a function \(f\) has the property \(P\) is transformed into deciding whether \(f\in C\). For testing the property of the function \(f\), a common method reconstructs an approximation function by sampling from \(C\), and the property of \(f\) is described approximately by the property of \(h\). The process of reconstructing \(h\) is called the learning of \(f\). This paper presents a theory and method of learning and testing of properties of Boolean functions, and they can be applied to the learning of concepts and the learning and testing of functions with given properties.

MSC:

06E30 Boolean functions
68T05 Learning and adaptive systems in artificial intelligence
68T30 Knowledge representation