# 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,
              use.tilde = FALSE, collapse = "*", ...)
    findmin(chart)
    solveChart(chart, row.dom = FALSE, all.sol = FALSE, depth = NULL, ...)

## 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.
`use.tilde` |  |  |  | Logical, row and column names indicating absence with a tilde.
`collapse` |  |  |  | Scalar character, how to collapse different parts of the row or column names.
`chart` |  |  |  | An object of class `"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 `"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, Abc, AbC, aBc", snames =  "A,B,C")
    chart

      ABC Abc AbC aBc
    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

    # Quine's example, page 528
    rows <- "AB, BC, Ac, aC, abd, bcd"
    cols <- "ABCD, ABCd, ABcD, ABcd, AbcD, Abcd, aBCD, aBCd, abCD, abCd, abcd"

    chart <- makeChart(rows, cols, "A,B,C,D")
    chart

        ABCD ABCd ABcD ABcd AbcD Abcd aBCD aBCd abCD abCd abcd
    AB   x    x    x    x    -    -    -    -    -    -    -
    BC   x    x    -    -    -    -    x    x    -    -    -
    Ac   -    -    x    x    x    x    -    -    -    -    -
    aC   -    -    -    -    -    -    x    x    x    x    -
    abd  -    -    -    -    -    -    -    -    -    x    x
    bcd  -    -    -    -    -    x    -    -    -    -    x

    findmin(chart)

    [1] 4

    solveChart(chart)

         [,1] [,2] [,3] [,4]
    [1,]    1    1    2    2
    [2,]    3    3    3    3
    [3,]    4    4    4    4
    [4,]    5    6    5    6

    # 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: AbCE and ACDE
    primes

         A B C D E
    [1,] 2 1 2 0 2
    [2,] 2 0 2 2 2

    # the initial causal combinations: AbCdE, AbCDE 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)
    chartLC

         AbCdE AbCDE ABCDE
    AbCE   x     x     -
    ACDE   -     x     x

## Author

Adrian Dusa