chartFunctions: Create and solve a prime implicants chart

Description Usage Arguments Details Value Author(s) References Examples

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.

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