# Create and solve a prime implicants chart

## Description

These functions help creating a demo for a prime implicant chart, and also show how to solve it using a minimum number of prime implicants.

## Usage

    makeChart(primes = "", configs = "", snames = "", mv = FALSE,
              collapse = "*", ...)
    findmin(chart)
    solveChart(chart, row.dom = FALSE, all.sol = FALSE, depth, ...)

## Arguments

`primes` |  |  |  | A string containing prime implicants, separated by commas, or a matrix of implicants.
`configs` |  |  |  | A string containing causal configurations, separated by commas, or a matrix of causal configurations in the implicants space.
`snames` |  |  |  | A string containing the sets' names, separated by commas.
`mv` |  |  |  | Logical, write row and column names in multi-value notation.
`collapse` |  |  |  | Scalar character, how to collapse different parts of the row or column names.
`chart` |  |  |  | An object of class `"QCA_pic"` or a logical matrix.
`row.dom` |  |  |  | Logical, apply row dominance to eliminate redundant prime implicants.
`all.sol` |  |  |  | Derive all possible solutions, irrespective if the disjunctive number of prime implicants is minimal or not.
`depth` |  |  |  | A maximum number of prime implicants for any disjunctive solution.
`...` |  |  |  | Other arguments (mainly for backwards compatibility).

## Details

A PI chart, in this package, is a logical matrix (with `TRUE`/`FALSE` values), containing the prime implicants on the rows and the starting configurations of causal conditions, on the columns, like the one produced by `makeChart()`. It is useful to determine visually which prime implicant (if any) is essential.

When `primes` and `configs` are character, the individual sets are identified using the function `translate()`, using the SOP - Sum Of Products form, which needs the set names in the absence of any other information. If products are formed using the standard `*` operator, specifying the set names is not mandatory.

When `primes` and `configs` are matrices, they have to be specified at implicants level, where the value `0` is interpreted as a minimized literal.

The chart is subsequently processed algorithmically by `solveChart()` to find the absolute minimal number `M` of rows (prime implicants) necessary to cover all columns, then searches through all possible combinations of `M` rows, to find those which actually cover the columns.

The number of all possible combinations of `M` rows increases exponentially with the number of prime implicants generated by the Quine-McCluskey minimization procedure, and the solving time quickly grows towards infinity for large PI charts.

To solve the chart in a minimal time, the redundant prime implicants need to first be eliminated. This is the purpose of the argument `row.dom`. When activated, it eliminates the dominated rows (those which cover a smaller number of columns than another, dominant prime implicant).

The identification of the full model space (including the non-minimal solutions) requires the entire PI chart and is guaranteed to consume a lot of time (towards infinity for very large PI charts). This is done by activating the argument `all.sol`, which automatically deactivates the argument `row.dom`.

The argument `depth` is relevant only when the argument `all.sol` is activated, and it is automatically increased if the minimal number of rows `M` needed to cover all columns is larger. By default, it bounds the disjunctive solutions to at most 5 prime implicants, but this number can be increased to widen the search space, with a cost of increasing the search time.

## Value

For `makeChart`: a logical matrix of class `"QCA_pic"`.

For `findmin`: a numerical scalar.

For `solveChart`: a matrix containing all possible combinations of PI chart rows necessary to cover all its columns.

## References

Quine, W.V. (1952) The Problem of Simplifying Truth Functions, The American Mathematical Monthly, vol.59, no.8. (Oct., 1952), pp.521-531.

Ragin, C.C. (1987) The Comparative Method. Moving beyond qualitative and quantitative strategies, Berkeley: University of California Press

## Examples

    # non-standard products, it needs the set names
    chart <- makeChart("a, b, ~c", "abc, a~b~c, a~bc, ~ab~c")
    chart

         abc   a~b~c a~bc  ~ab~c
    a      x     x     x     -
    b      x     -     -     x
    ~c     -     x     -     x

    findmin(chart)

    [1] 2

    solveChart(chart)
    # first and second rows (a + b)
    # and first and third rows (a + ~c)
    # a is an essential prime implicant
    #  a + b  a + ~c

         [,1]   [,2]
    [1,]    1      1
    [2,]    2      3

    # using SOP standard product sign
    rows <- "EF, ~GH, IJ"
    cols <- "~EF*~GH*IJ, EF*GH*~IJ, ~EF*GH*IJ, EF*~GH*~IJ"
    chart <- makeChart(rows, cols)
    chart

        ~EF*~GH*IJ EF*GH*~IJ ~EF*GH*IJ EF*~GH*~IJ
    EF      -          x         -         x
    ~GH     x          -         -         x
    IJ      x          -         x         -

    solveChart(chart)
    # ~GH is redundant
    #  EF + IJ

         [,1]
    [1,]    1
    [2,]    3

    # using implicant matrices
    primes <- matrix(c(2,2,1,0,2,2,0,2,2,2), nrow = 2)
    configs <- matrix(c(2,2,2,1,1,2,2,2,2,1,2,2,2,2,2), nrow = 3)
    colnames(primes) <- colnames(configs) <- letters[1:5]

    # the prime implicants: a~bce and acde
    primes

         a b c d e
    [1,] 2 1 2 0 2
    [2,] 2 0 2 2 2

    # the initial causal combinations: a~bc~de, a~bcde and abcde
    configs

         a b c d e
    [1,] 2 1 2 1 2
    [2,] 2 1 2 2 2
    [3,] 2 2 2 2 2

    chartLC <- makeChart(primes, configs, collapse = "")
    chartLC

            a~bc~de a~bcde   abcde
    a~bce      x       x       -
    acde       -       x       x

## Author

Adrian Dusa