# chartFunctions: Create and solve a prime implicants chart In QCA: Qualitative Comparative Analysis

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

 ```1 2 3 4 5 6``` ```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, 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 observed positive output configurations on the columns. Such a chart is produced by `makeChart()`, and it is useful to visually determine which prime implicants (if any) are 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, Charles C. (1987) The Comparative Method. Moving beyond qualitative and quantitative strategies, Berkeley: University of California Press

## Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87``` ```# 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) # 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) # 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 ```

QCA documentation built on May 2, 2019, 4:47 p.m.