# 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

1 2 3 | ```
makeChart(primes = "", configs = "", snames = "")
solveChart(chart, row.dom = FALSE, all.sol = FALSE, ...)
``` |

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

`chart` |
A logical matrix (as the PI chart). |

`row.dom` |
Logical, apply row dominance to eliminate redundant prime implicants. |

`all.sol` |
Derive all possible solutions, irrespective of the number of PIs. |

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

**are character, the individual sets are identified using the function**

`configs`

**, using the DNF - Disjunctive Normal Form, which needs the set names in the absence of any other information. If products are formed using the standard**

`translate()`

**operator, specifying the set names is not mandatory.**

`*`

When ** primes** and

**are matrices, they have to be specified at implicants level, where the value**

`configs`

**is interpreted as a minimized literal.**

`0`

The chart is subsequently processed algorithmically by ** solveChart()** to further
reduce the reduntant prime implicants. It applies a linear programming function from
package lpSolve, 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.
Since all possible combinations grow exponentially with the number of prime implicants resulted from the Quine-McCluskey minimization procedure, this function tries hard to reduce this number by first eliminating the redundant prime implicants.

When set to ** TRUE**, the argument

**does something like this by eliminating the dominated rows (those which cover a smaller number of columns than another, dominant prime implicant).**

`row.dom`

### Value

For ** makeChart**: a logical matrix.

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

### Author(s)

Adrian Dusa

### 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 | ```
if (require("QCA")) {
# non-standard products, it needs the set names
chart <- makeChart("A, B, c", "ABC, Abc, AbC, aBc", snames = "A,B,C")
prettyTable(chart)
# ABC Abc AbC aBc
# A x x x -
# B x - - x
# c - x - x
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 <- c("AB, BC, Ac, aC, abd, bcd")
cols <- c("ABCD, ABCd, ABcD, ABcd, AbcD, Abcd, aBCD, aBCd, abCD, abCd, abcd")
prettyTable(chart <- makeChart(rows, cols, "A,B,C,D"))
# 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
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 DNF standard product sign
rows <- c("EF, ~GH, IJ")
cols <- c("~EF*~GH*IJ, EF*GH*~IJ, ~EF*GH*IJ, EF*~GH*~IJ")
prettyTable(chart <- makeChart(rows, cols))
# ~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)
prettyTable(chartLC)
# AbCdE AbCDE ABCDE
# AbCE x x -
# ACDE - x x
}
``` |

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker. Vote for new features on Trello.