Implicant matrix functions: allExpressions, createMatrix, getRow: Functions Related to the Implicant Matrix

Description

This is a set of functions dedicated to the implicant matrix, a space where all causal configurations and their minimized solutions are found.

They can produce all possible implicants and prime implicants, or all possible combinations for a specific number of causal conditions and their number of values (either binary or multi-value).

Usage

allExpressions(noflevels, raw = FALSE, arrange = FALSE)
createMatrix(noflevels)
getRow(noflevels, row.no, zerobased = FALSE)

Arguments

noflevels

The number of levels (values) for each causal condition.

raw

Logical, if TRUE it returns the matrix indicating which conditions have been minimized, using -1.

arrange

Logical, if TRUE the program tries hard to arrange the result matrix for visual inspection.

row.no

A vector, the desired row numbers.

zerobased

Logical, the first row number is zero.

Value

A matrix with $k$ columns and:$v_{1} * v_{2} * ... * v_{k}$ rows if a truth table;$(v_{1} + 1) * (v_{2} + 1) * ... * (v_{k} + 1)$ rows if an implicant matrix;$x$ rows, equal to the length of row.no.

Details

A truth table for binary crisp conditions is a matrix with $2^k$ rows, where $k$ is the number of causal conditions.

For multi-value causal conditions, the same equation can be generalised to:

$v_{1} * v_{2} * ... * v_{k}$

where $v$ is the number of values (levels) for every causal condition from 1 to k.

Implicant matrices contain all rows from the truth table, plus all of their supersets, (all implicants and prime implicants), including the empty set (Dusa 2007, 2010).

For a binary crisp set procedure, there are $3^k - 1$ possible expressions (groupings), see Ragin (2010). Including the empty set (the situation when all causal conditions have been minimized), the implicant matrix consists of exactly $3^k$ rows, including the truth table configurations.

In fact, $3^k$ is also obtained by the product:

$(2 + 1) * (2 + 1) * ... * (2 + 1)$

For multi-value causal conditions, the same equation can be generalised to:

$(v_{1} + 1) * (v_{2} + 1) * ... * (v_{k} + 1)$

where every number of levels in each causal conditions is incremented with 1, to allow coding the minimization of literals in each (prime) implicant (see examples).

The function allExpressions() creates a matrix which contains all possible implicants and prime implicants, displayed in the original values form using the code -1 to point the minimized literals, while the other functions use the code 0, all other values being incremented with 1.

The function createMatrix() creates a base matrix for truth tables and implicant matrices.

The function getRow() takes the number of a row in the truth table or implicant matrix (in its decimal form), and transforms it into its binary (or multi-base) representation, as a configuration of binary or multi-values for each causal condition.

Note that R is not a zero-based language (where all numbers start from 0), and positions in vectors and matrices start with 1. For this reason, although (mathematicall) the binary representation of the decimal number 0 (for example, at three causal conditions) is 0 0 0, in R that would be the “first” line in the implicant matrix, therefore 0 0 0 is translated into the number 1.

References

Dusa, Adrian. 2007. Enhancing Quine-McCluskey. COMPASSS: Working Paper 2007-49. URL: http://www.compasss.org/wpseries/Dusa2007b.pdf.

Dusa, Adrian. 2010. “A Mathematical Approach to the Boolean Minimization Problem.” Quality & Quantity vol.44, no.1, pp.99-113.

Ragin, Charles C. (2000) Fuzzy-Set Social Science. Chicago: University of Chicago Press.

Examples

Run this code

if (require("QCA")) {

# three binary causal conditions, having two levels each: 0 and 1=
noflevels <- c(2, 2, 2)

# for three binary causal conditions
allExpressions(noflevels)

# the same matrix, this time arranged better
# (last rows represent the truth table)
allExpressions(noflevels, arrange = TRUE)

# using the raw form
allExpressions(noflevels, raw = TRUE)



# create a truth table based on 3 conditions
createMatrix(noflevels)

# its implicant matrix
createMatrix(noflevels + 1)

# create a truth table based on 3 conditions where the second has three levels
createMatrix(c(2, 3, 2))



# deriving rows
rows <- c(2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17)
mat <- getRow(noflevels + 1, rows) # note the +1
rownames(mat) <- rows
colnames(mat) <- c("A", "B", "C")
mat

# implicant matrix     normal values

#      A  B  C    |       A  B  C       
#   2  0  0  1    |    2  -  -  0       c      
#   4  0  1  0    |    4  -  0  -       b
#   5  0  1  1    |    5  -  0  0       bc
#   7  0  2  0    |    7  -  1  -       B
#   8  0  2  1    |    8  -  1  0       Bc
#  10  1  0  0    |   10  0  -  -       a  
#  11  1  0  1    |   11  0  -  0       ac                 
#  13  1  1  0    |   13  0  0  -       ab   
#  14  1  1  1    |   14  0  0  0       abc
#  16  1  2  0    |   16  0  1  -       aB
#  17  1  2  1    |   17  0  1  0       aBc
                          
}

Run the code above in your browser using DataCamp Workspace