Functions Related to the Implicant Matrix
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).
allExpressions(noflevels = NULL, arrange = FALSE, depth, raw = FALSE, ...) createMatrix(noflevels = NULL, ...) getRow(row.no = NULL, noflevels = NULL, zerobased = FALSE, ...)
noflevels |
The number of levels (values) for each causal condition. |
arrange |
Logical, if |
depth |
Integer, an upper number of causal conditions to form expressions with. |
raw |
Logical, if |
row.no |
A vector, the desired row numbers. |
zerobased |
Logical, if |
... |
Other arguments. |
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:
v1 * v2 * ... * vk
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:
(v1 + 1) * (v2 + 1) * ... * (vk + 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.
Specifying a smaller depth automatically activates the argument arrange.
When the argument arrange is activated, the output is arranged in the increasing
order of the number of conditions which form conjunctions, up to the maximum number specified
by the argument depth (which if NULL, it is considered equal to the
number of columns in the matrix).
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 \textsf{R} is a 1-based language (all numbers start from 1), and similarly 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 \textsf{R} that would be the “first” line in the implicant matrix, therefore 0 0 0 is
translated into the number 1, unless the argument zerobased is activated.
A matrix with k columns and:
v1 * v2 * ... * vk rows if a truth table;
(v1 + 1) * (v2 + 1) * ... * (vk + 1) rows if an implicant matrix;
x rows, equal to the length of row.no.
Adrian Dusa
Dusa, A. (2007b) Enhancing Quine-McCluskey. WP 2007-49, COMPASSS Working Papers series.
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.
# 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)
# show only the implicants (excluding the truth table)
allExpressions(noflevels, arrange = TRUE, depth = 2)
# using the raw form
allExpressions(noflevels, raw = TRUE)
# create a base truth table for 3 binary conditions
createMatrix(noflevels)
# its implicant matrix
createMatrix(noflevels + 1)
# create a base truth table where the second condition 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(rows, noflevels + 1) # 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 ~B~C
# 7 0 2 0 | 7 - 1 - B
# 8 0 2 1 | 8 - 1 0 B~C
# 10 1 0 0 | 10 0 - - ~A
# 11 1 0 1 | 11 0 - 0 ~A~C
# 13 1 1 0 | 13 0 0 - ~A~B
# 14 1 1 1 | 14 0 0 0 ~A~B~C
# 16 1 2 0 | 16 0 1 - ~AB
# 17 1 2 1 | 17 0 1 0 ~AB~CPlease choose more modern alternatives, such as Google Chrome or Mozilla Firefox.