A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.

Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.

The interconnection problem of binary circuits becomes seriously as the exponential growth of the circuits complexity has been driven by a combination of down scaling of the device size and up scaling of the chip size. Motivated by the problem, there is much research of circuits based on multiple-valued logic. On the other hand, caused by the signal propagation delay, there exist hazards in binary logic circuits. To analyze hazards in binary logic circuits, many multiple-valued logics have been proposed, and studied on their mathematical properties. The paper will discuss on a multiple-valued logic which is suitable for treating static hazards in multiple-valued logic circuits. Then, the paper will show that the prime implicants expressions of r-valued logic functions realize static hazards free r-valued logic circuits.

In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.

This paper presents a technique to determine prime implicants in multi-level combinational networks. The method is based on a graph representation of Boolean functions called AND/OR reasoning graphs. This representation follows from a search strategy to solve the satisfiability problem that is radically different from conventional search for this purpose (such as exhaustive simulation, backtracking, BDDs). The paper shows how to build AND/OR reasoning graphs for arbitrary combinational circuits and proves basic theoretical properties of the graphs. It will be demonstrated that AND/OR reasoning graphs allow us to naturally extend basic notions of two-level switching circuit theory to multi-level circuits. In particular, the notions of prime implicants and permissible prime implicants are defined for multi-level circuits and it is proved that AND/OR reasoning graphs represent all these implicants. Experimental results are shown for PLA factorization.

A P-Fuzzy Switching Function is a meaningful class of fuzzy switching functions that is representable by a logic formula consisting of prime implicants. This paper aima at extracting knowledge represented as prime implicants from a given learning data. The main results are the necessary and sufficient conditions for the learning data to be representable with P-fuzzy switching functions, and to be determined by unique logic formula.