minimalize: Eliminate logical redundancies from Boolean expressions

Description

minimalize eliminates logical redundancies from a Boolean expression cond based on all configurations of the factors in cond that are possible according to classical Boolean logic. That is, minimalize performs logical (i.e. not data-driven) redundancy elimination. The output is a set of redundancy-free DNFs that are logically equivalent to cond.

Usage

minimalize(cond, x = NULL, maxstep = c(4, 4, 12))

Value

A list of character vectors of the same length as cond. Each list element contains one or several redundancy-free disjunctive normal forms (DNFs) that are logically equivalent to cond.

Arguments

cond: Character vector specifying Boolean expressions; the acceptable syntax is the same as that of condition.
x: A data frame, a configTable, or a list determining the possible values for each factor in cond; x has no effect for a cond with only binary factors but is mandatory for a cond with multi-value factors (see details).
maxstep: Maximal complexity of the returned redundancy-free DNFs (see cna).

Details

The regularity theory of causation underlying CNA conceives of causes as parts of redundancy-free Boolean dependency structures. Boolean dependency structures tend to contain a host of redundancies. Redundancies may obtain relative to an analyzed set of empirical data, which, typically, are fragmented and do not feature all logically possible configurations, or they may obtain for principled logical reasons, that is, relative to all configurations that are possible according to Boolean logic. Whether a Boolean expression (in disjunctive normal form) contains the latter type of logical redundancies can be checked with the function is.inus.

minimalize eliminates logical redundancies from cond and outputs all redundancy-free disjunctive normal forms (DNF) (within some complexity range given by maxstep) that are logically equivalent with cond. If cond is redundancy-free, no reduction is possible and minimalize returns cond itself (possibly as an element of multiple logically equivalent redundancy-free DNFs). If cond is not redundancy-free, a cna with con = 1 and cov = 1 is performed relative to full.ct(x) (relative to full.ct(cond) if x is NULL). The output is the set of all redundancy-free DNFs in the complexity range given by maxstep that are logically equivalent to cond.

The purpose of the optional argument x is to determine the space of possible values of the factors in cond. If all factors in cond are binary, x is optional and without influence on the output of minimalize. If some factors in cond are multi-value, minimalize needs to be given the range of these values. x can be a data frame or configTable listing all possible value configurations or simply a list of the possible values for each factor in cond (see examples).

The argument maxstep, which is identical to the corresponding argument in cna, specifies the maximal complexity of the returned DNF. maxstep expects a vector of three integers c(i, j, k) determining that the generated DNFs have maximally j disjuncts with maximally i conjuncts each and a total of maximally k factor values. The default is maxstep = c(4, 4, 12). If the complexity range of the search space given by maxstep is too low, it may happen that nothing is returned (accompanied by a corresponding warning message). In that case, the maxstep values need to be increased.

Examples

Run this code

# Binary expressions
# ------------------
# DNFs as input.
minimalize(c("A", "A+B", "A + a*B", "A + a", "A*a"))
minimalize(c("F + f*G", "F*G + f*H + G*H", "F*G + f*g + H*F + H*G"))

# Any Boolean expressions (with variable syntax) are admissible inputs.
minimalize(c("!(A*B*C + a*b*c)", "A*!(B*d+E)->F", "-(A+-(E*F))<->H"))

# Proper redundancy elimination may require increasing the maxstep values.
minimalize("!(A*B*C*D*E+a*b*c*d*e)")  
minimalize("!(A*B*C*D*E+a*b*c*d*e)", maxstep = c(3, 5, 15))


# Multi-value expressions
# -----------------------
# In case of expressions with multi-value factors, the relevant range of factor 
# values must be specified by means of x. x can be a list or a configTable:
values <- list(C = 0:3, F = 0:2, V = 0:4)
minimalize(c("C=1 + F=2*V=0", "C=1 + C=0*V=1"), values)
minimalize("C=1 + F=2 <-> V=1", values, maxstep=c(3,10,20))
minimalize(c("C=1 + C=0 * C=2", "C=0 + C=1 + C=2"), configTable(d.pban))


# Eliminating logical redundancies from non-INUS asf inferred from real data
# --------------------------------------------------------------------------
fsdata <- configTable(d.jobsecurity)
conds <- asf(cna(fsdata, con = 0.8, cov = 0.8, inus.only = FALSE))$condition
conds <- lhs(conds)
noninus.conds <- conds[-which(is.inus(conds, fsdata))]
minimalize(noninus.conds)