Enhancing the Minimization of Boolean and Multivalue Output Functions With eQMC

Abstract

Configurational comparative methods have gained in popularity among sociologists and political scientists. In particular, Qualitative Comparative Analysis (QCA) has attracted considerable attention in recent years. The process of Boolean minimization by means of the Quine-McCluskey algorithm (QMC) is the central procedure in QCA, but QMC's exactitude renders it memory intensive and slow in processing complex output functions. In this article, we introduce the enhanced QMC algorithm (eQMC) to alleviate these problems. eQMC is equally exact but, unlike QMC, capable of processing multivalent condition and outcome factors. Instead of replacing QMC, however, eQMC acts as an optimizing complement in contexts of limited empirical diversity. We demonstrate its speed and computer memory performance through simulations.

Keywords:

• Boolean minimization
• enhanced Quine-McCluskey algorithm
• Qualitative Comparative Analysis (QCA)
• Quine-McCluskey algorithm
• set theory

ACKNOWLEDGMENTS

Previous versions of this article have been presented at the 2013 Annual Conference of the Swiss Political Science Association, University of Zurich (Switzerland), the 2013 Annual Conference of the Empirical Methods Section of the German Political Science Association, University of Konstanz (Germany) and the 2013 Annual Meeting of the American Political Science Association, Chicago (USA). An early draft of this article has been published as WP-2007-49 in the COMPASSS Working Paper series at www.compasss.org. We thank Barry Cooper, Charles Ragin and the two anonymous reviewers of this journal for very helpful comments and suggestions.

Notes

¹According to the COMPASSS database, about 37% of all applied QCA publications have appeared in sociology and comparative politics. See http://www.compasss.org/bibdata.htm for more details (accessed March 1, 2015).

²Two generalized variants of crisp-set QCA exist. The first extension is multivalue QCA (Cronqvist & Berg-Schlosser, 2009), the second fuzzy-set QCA (Ragin, 2008). Although the former rests on multivalue logic and the latter on fuzzy logic, both of which generalize Boolean algebra in different directions, we refer to Boolean algebra throughout this article for simplicity because the principle behind the minimization procedure to be introduced remains the same. A fourth variant called generalized-set QCA has recently joined the fold (Thiem, 2013, 2014).

³For an introduction to Boolean algebra, see Hohn (1966). The standard terms in QCA for Boolean input and output variables are condition and outcome factors. We use these terms and the nomenclature of set theory as one branch of Boolean algebra to distinguish between linear-algebraic and Boolean-algebraic operations.

⁴Ragin (2000) has also introduced an inclusion algorithm which parted in many ways with QMC, but abandoned it again later to replace it with the QMC-based truth table algorithm (Ragin, 2008).

⁵The eQMC algorithm has been implemented in the QCA package for the R environment (Duşa & Thiem, 2014; Thiem & Duşa, 2013b, 2013c; R Development Core Team, 2014), currently in version 1.1-4, and is thus available to applied users and open to review. For a review of current software and their specific minimization algorithms, see Thiem and Duşa (2013a).

⁶We use the terms bivalent, trivalent, multivalent, etc. to indicate the number of levels a factor comprises.

⁷We explicitly speak of “possibilities” since the advantages of eQMC over QMC do not materialize under all research designs. We elaborate on this point in Section 4.

⁸Function tables are also commonly known in QCA as truth tables or tables of combinations.

⁹Configuration matrices can also be constructed by representing its rows as numbers from 0 to d − 1 using a binary, tertiary, etc., number system. For example, with four Boolean condition factors, the last row (15) in the configuration matrix would contain the combination X₁{1}X₂{1}X₃{1}X₄{1} because 1 · 2³ + 1 · 2² + 1 · 2¹ + 1 · 2⁰ = 15. In order not to have to switch between different number systems, we have opted for an arithmetic approach to presentation.

¹⁰We disregard cases of contradictions (not to be understood in the logical sense). Contradictions describe an indeterminate state between 𝒵(O{v_h}) = 1 and 𝒵(O{v_h}) = 0 for which analysts are reluctant to assign binary function values.

¹¹For an application of such maps in multivalue QCA, see Thiem (2015).

¹²In the extreme case where no Boolean minimization is possible, ℱ¹ = ℐ¹ = 𝒫¹.

¹³For more detailed explanations of prime implicant charts, see Edwards (1973, p. 98ff.), Lewin and Protheroe (1992, p. 76ff.), and McCluskey (1965, p. 140ff.).

¹⁴Potentially, this could also apply to function tables, but as this solution is not generally considered, we draw an explicit distinction between factors and their level indices.

¹⁵As Eq. (9) is computed in base 10, which starts with 0, but r_i starts with i = 1, the unit vector has to be added.

¹⁶The analysis by Cress and Snow (1996) on homeless social movement organizations provides an extreme example of a mismatch between cases and configurations. It features 15 objects which cover 10 configurations, but 14 conditions create a property space of no fewer than 16,384 configurations.

¹⁷This allows us to compare both algorithms up to 15 condition factors. We use a regular end-user machine with the following components: Microsoft Windows 7 64-bit operating system, 6 GB RAM, Intel Core i7-2640 M CPU, 2.80 GHz.