# Functions Related to the Implicant Matrix

## Usage

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

## Arguments

noflevels
  The number of levels (values) for each causal condition.
arrange
  Logical, if TRUE the program tries hard to arrange the result matrix for visual inspection.
depth
  Integer, an upper number of causal conditions to form expressions with.
raw
  Logical, if TRUE it returns the matrix indicating which conditions have been minimized, using `-1`.
row.no
  A vector, the desired row numbers.
zerobased
  Logical, the first row number is zero.
...
  Other arguments.

## 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).

## 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.

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 `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.

## 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`.

## 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

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

    # for three binary causal conditions
    allExpressions(noflevels)

     1
     2              0
     3              1
     4         0
     5         0    0
     6         0    1
     7         1
     8         1    0
     9         1    1
    10    0
    11    0         0
    12    0         1
    13    0    0
    14    0    0    0
    15    0    0    1
    16    0    1
    17    0    1    0
    18    0    1    1
    19    1
    20    1         0
    21    1         1
    22    1    0
    23    1    0    0
    24    1    0    1
    25    1    1
    26    1    1    0
    27    1    1    1

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

     1
     2              0
     3              1
     4         0
     5         1
     6    0
     7    1
     8         0    0
     9         0    1
    10         1    0
    11         1    1
    12    0         0
    13    0         1
    14    0    0
    15    0    1
    16    1         0
    17    1         1
    18    1    0
    19    1    1
    20    0    0    0
    21    0    0    1
    22    0    1    0
    23    0    1    1
    24    1    0    0
    25    1    0    1
    26    1    1    0
    27    1    1    1

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

     1   -1   -1   -1
     2   -1   -1    0
     3   -1   -1    1
     4   -1    0   -1
     5   -1    0    0
     6   -1    0    1
     7   -1    1   -1
     8   -1    1    0
     9   -1    1    1
    10    0   -1   -1
    11    0   -1    0
    12    0   -1    1
    13    0    0   -1
    14    0    0    0
    15    0    0    1
    16    0    1   -1
    17    0    1    0
    18    0    1    1
    19    1   -1   -1
    20    1   -1    0
    21    1   -1    1
    22    1    0   -1
    23    1    0    0
    24    1    0    1
    25    1    1   -1
    26    1    1    0
    27    1    1    1

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

         [,1] [,2] [,3]
    [1,]    0    0    0
    [2,]    0    0    1
    [3,]    0    1    0
    [4,]    0    1    1
    [5,]    1    0    0
    [6,]    1    0    1
    [7,]    1    1    0
    [8,]    1    1    1

    # its implicant matrix
    createMatrix(noflevels + 1)

          [,1] [,2] [,3]
     [1,]    0    0    0
     [2,]    0    0    1
     [3,]    0    0    2
     [4,]    0    1    0
     [5,]    0    1    1
     [6,]    0    1    2
     [7,]    0    2    0
     [8,]    0    2    1
     [9,]    0    2    2
    [10,]    1    0    0
    [11,]    1    0    1
    [12,]    1    0    2
    [13,]    1    1    0
    [14,]    1    1    1
    [15,]    1    1    2
    [16,]    1    2    0
    [17,]    1    2    1
    [18,]    1    2    2
    [19,]    2    0    0
    [20,]    2    0    1
    [21,]    2    0    2
    [22,]    2    1    0
    [23,]    2    1    1
    [24,]    2    1    2
    [25,]    2    2    0
    [26,]    2    2    1
    [27,]    2    2    2

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

          [,1] [,2] [,3]
     [1,]    0    0    0
     [2,]    0    0    1
     [3,]    0    1    0
     [4,]    0    1    1
     [5,]    0    2    0
     [6,]    0    2    1
     [7,]    1    0    0
     [8,]    1    0    1
     [9,]    1    1    0
    [10,]    1    1    1
    [11,]    1    2    0
    [12,]    1    2    1

    # 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

       A B C
    2  0 0 1
    4  0 1 0
    5  0 1 1
    7  0 2 0
    8  0 2 1
    10 1 0 0
    11 1 0 1
    13 1 1 0
    14 1 1 1
    16 1 2 0
    17 1 2 1

    # 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

## See also

`expand.grid`

## Author

Adrian Dusa