Summary: The systematic formulation in the module Minterms shows that each Boolean combination, as a union of minterms, can be designated by a vector of zero-one coefficients. A coefficient one in the ith position (numbering from zero) indicates the inclusion of minterm Mi in the union. We formulate this pattern carefully below and show how MATLAB logical operations may be utilized in problem setup and solution.
The concepts and procedures in this unit play a significant role in many aspects of the analysis of probability topics and in the use of MATLAB throughout this work.
The systematic formulation in the previous module Minterms shows that each Boolean combination, as a union of minterms, can be designated by a vector of zero-one coefficients. A coefficient one in the ith position (numbering from zero) indicates the inclusion of minterm Mi in the union. We formulate this pattern carefully below and show how MATLAB logical operations may be utilized in problem setup and solution.
Suppose E is a Boolean combination of
where Mi is the ith minterm and JE is the set of indices for those Mi included in E. For example, consider
We may designate each set by a pattern of zeros and ones
It should be apparent that this formalization can be extended to sets generated by any finite class.
Minterm vectors for Boolean combinations
If E and F are combinations of n generating sets, then each is represented by a unique minterm vector of length 2n. In the treatment in the module Minterms, we determine the minterm vector with the aid of a minterm map. We wish to develop a systematic way to determine these vectors.
As a first step, we suppose we have minterm vectors for E and F and want to obtain the minterm vector of Boolean combinations of these.
We illustrate for the case of the two combinations E and F of three generating sets, considered above
Then
MATLAB logical operations
MATLAB logical operations on zero-one matrices provide a convenient way of handling
Boolean combinations of minterm vectors represented as matrices. For two zero-one
matrices
Thus, if
This suggests a general approach to determining minterm vectors for Boolean combinations.
Suppose, for example, the class
of generating sets is
If
MATLAB implementation
A key step in the procedure just outlined is to obtain the minterm vectors for the generating
elements 0 0 1 1 is replicated
twice to give
0 0 1 1 0 0 1 1
The function minterm(n,k) generates the kth minterm vector for a class of n generating sets.
>> A = minterm(3,1)
A = 0 0 0 0 1 1 1 1
>> B = minterm(3,2)
B = 0 0 1 1 0 0 1 1
>> C = minterm(3,3)
C = 0 1 0 1 0 1 0 1
F = (A&B)|(~B&C)
F = 0 1 0 0 0 1 1 1
>> G = A|(~A&C)
G = 0 1 0 1 1 1 1 1
>> JF = find(F)-1 % Use of find to determine index set for F
JF = 1 5 6 7 % Shows F = M(1, 5, 6, 7)
These basic minterm patterns are useful not only for Boolean combinations of events but also for many aspects of the analysis of those random variables which take on only a finite number of values.
Zero-one arrays in MATLAB
The treatment above hides the fact that a rectangular array of zeros and ones can have two quite different meanings and functions in MATLAB.
Some simple examples will illustrate the principal properties.
>>> A = minterm(3,1);
>> B = minterm(3,2);
>> C = minterm(3,3);
>> F = (A&B)|(~B&C)
F = 0 1 0 0 0 1 1 1
>> G = A|(~A&C)
G = 0 1 0 1 1 1 1 1
>> islogical(A) % Test for logical array
ans = 0
>> islogical(F)
ans = 1
>> m = max(A,B) % A matrix operation
m = 0 0 1 1 1 1 1 1
>> islogical(m)
ans = 0
>> m1 = A|B % A logical operation
m1 = 0 0 1 1 1 1 1 1
>> islogical(m1)
ans = 1
>> a = logical(A) % Converts 0-1 matrix into logical array
a = 0 0 0 0 1 1 1 1
>> b = logical(B)
>> m2 = a|b
m2 = 0 0 1 1 1 1 1 1
>> p = dot(A,B) % Equivalently, p = A*B'
p = 2
>> p1 = total(A.*b)
p1 = 2
>> p3 = total(A.*B)
p3 = 2
>> p4 = a*b' % Cannot use matrix operations on logical arrays
??? Error using ==> mtimes % MATLAB error signal
Logical inputs must be scalar.
Often it is desirable to have a table of the generating minterm vectors. Use of the function minterm in a simple “for loop” yields the following m-function.
The function mintable(n) Generates a table of minterm vectors for n generating sets.
>> M3 = mintable(3)
M3 = 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
As an application of mintable, consider the problem of determining the probability
of k of n events. If
In the matrix M = mintable(n) these are the minterms corresponding to columns
with exactly k ones. The event
If we have the minterm probabilities, it is easy to pick out the appropriate minterms and combine the probabilities. The following example in the case of three variables illustrates the procedure.
In the software survey problem, the minterm probabilities are
where
SOLUTION
We form a mintable for three variables. We count the number of “successes” corresponding to each minterm by using the MATLAB function sum, which gives the sum of each column. In this case, it would be easy to determine each distinct value and add the probabilities on the minterms which yield this value. For more complicated cases, we have an m-function called csort (for sort and consolidate) to perform this operation.
>> pm = 0.01*[0 5 10 5 20 10 40 10];
>> M = mintable(3)
M =
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
>> T = sum(M) % Column sums give number
T = 0 1 1 2 1 2 2 3 % of successes on each
>> [k,pk] = csort(T,pm); % minterm, determines
% distinct values in T and
>> disp([k;pk]') % consolidates probabilities
0 0
1.0000 0.3500
2.0000 0.5500
3.0000 0.1000
For three variables, it is easy enough to identify the various combinations “by eye” and make the combinations. For a larger number of variables, however, this may become tedious. The approach is much more useful in the case of Independent Events, because of the ease of determining the minterm probabilities.
Minvec procedures
Use of the tilde
We wish to generate a matrix whose rows are the minterm vectors for
>> minvec3 % Call for the setup procedure
Variables are A, B, C, Ac, Bc, Cc
They may be renamed, if desired
>> V = [A|Ac; A; A&B; A&B&C; C; Ac&Cc]; % Logical combinations (one per
% row) yield logical vectors
>> disp(V)
1 1 1 1 1 1 1 1 % Mixed logical and
0 0 0 0 1 1 1 1 % numerical vectors
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
0 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0
Minterm probabilities and Boolean combination
If we have the probability of every minterm generated by a finite class, we can determine the probability of any Boolean combination of the members of the class. When we know the minterm expansion or, equivalently, the minterm vector, we simply pick out the probabilities corresponding to the minterms in the expansion and add them. In the following example, we do this “by hand” then show how to do it with MATLAB .
Consider
Use of a minterm map shows
This is easily handled in MATLAB.
The following is a transcript of the MATLAB operations.
>> minvec3 % Call for the setup procedure
Variables are A, B, C, Ac, Bc, Cc
They may be renamed, if desired.
>> E = (A&(B|Cc))|(Ac&~(B|Cc));
>> F = (Ac&Bc)|(A&C);
>> pm = 0.01*[21 6 29 11 9 3 14 7];
>> PE = E*pm' % Picks out and adds the minterm probabilities
PE = 0.3600
>> PF = F*pm'
PF = 0.3700
We set up the matrix equations with the use of MATLAB and solve for the minterm probabilities. From these, we may solve for the desired “target” probabilities.
>> minvec3
Variables are A, B, C, Ac, Bc, Cc
They may be renamed, if desired.
Data vector combinations are:
>> DV = [A|Ac; A; B; C; A&B&C; Ac&Bc; (A&B)|(A&C)|(B&C); (A&Bc&C) - 2*(Ac&B&C)]
DV =
1 1 1 1 1 1 1 1 % Data mixed numerical
0 0 0 0 1 1 1 1 % and logical vectors
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0
0 0 0 1 0 1 1 1
0 0 0 -2 0 1 0 0
>> DP = [1 0.8 0.65 0.3 0.1 0.05 0.65 0]; % Corresponding data probabilities
>> pm = DV\DP' % Solution for minterm probabilities
pm =
-0.0000 % Roundoff -3.5 x 10-17
0.0500
0.1000
0.0500
0.2000
0.1000
0.4000
0.1000
>> TV = [(A&B&Cc)|(A&Bc&C)|(Ac&B&C); Ac&Bc&C] % Target combinations
TV =
0 0 0 1 0 1 1 0 % Target vectors
0 1 0 0 0 0 0 0
>> PV = TV*pm % Solution for target probabilities
PV =
0.5500 % Target probabilities
0.0500
The previous procedure first obtained all minterm probabilities, then used these to determine probabilities for the target combinations. The following procedure does not require calculation of the minterm probabilities. Sometimes the data are not sufficient to calculate all minterm probabilities, yet are sufficient to allow determination of the target probabilities.
Suppose the data minterm vectors are linearly independent, and the target minterm vectors are linearly dependent upon the data vectors (i.e., the target vectors can be expressed as linear combinations of the data vectors). Now each target probability is the same linear combination of the data probabilities. To determine the linear combinations, solve the matrix equation
Then the matrix
>> CT = TV/DV;
>> tp = CT*DP'
tp = 0.5500
0.0500The procedure mincalc performs calculations as in the preceding examples. The refinements consist of determining consistency and computability of various individual minterm probabilities and target probilities. The consistency check is principally for negative minterm probabilities. The computability tests are tests for linear independence by means of calculation of ranks of various matrices. The procedure picks out the computable minterm probabilities and the computable target probabilities and calculates them.
To utilize the procedure, the problem must be formulated appropriately and precisely, as follows:
Computational note. In mincalc, it is necessary to turn the arrays DV and TV consisting of
zero-one patterns into zero-one matrices. This is accomplished for DV by the
operation DV = ones(size(DV)).*DV. and similarly for TV. Both the original and the
transformed matrices have the same zero-one pattern, but MATLAB interprets them differently.
Usual case
Ṡuppose the data minterm vectors are linearly independent and the
target vectors are each linearly dependent on the data minterm vectors. Then each target
minterm vector is expressible as a linear combination of data minterm vectors. Thus, there is a
matrix
Cautionary notes
The program mincalc depends upon the provision in MATLAB for solving equations when less than full data are available (based on the singular value decomposition). There are several situations which should be dealt with as special cases. It is usually a good idea to check results by hand to determine whether they are consistent with data. The checking by hand is usually much easier than obtaining the solution unaided, so that use of MATLAB is advantageous even in questionable cases.
MATLAB Solutions for examples using mincalc
% file mcalc01 Data for software survey
minvec3;
DV = [A|Ac; A; B; C; A&B&C; Ac&Bc; (A&B)|(A&C)|(B&C); (A&Bc&C) - 2*(Ac&B&C)];
DP = [1 0.8 0.65 0.3 0.1 0.05 0.65 0];
TV = [(A&B&Cc)|(A&Bc&C)|(Ac&B&C); Ac&Bc&C];
disp('Call for mincalc')
>> mcalc01 % Call for data
Call for mincalc % Prompt supplied in the data file
>> mincalc
Data vectors are linearly independent
Computable target probabilities
1.0000 0.5500
2.0000 0.0500
The number of minterms is 8
The number of available minterms is 8
Available minterm probabilities are in vector pma
To view available minterm probabilities, call for PMA
>> disp(PMA) % Optional call for minterm probabilities
0 0
1.0000 0.0500
2.0000 0.1000
3.0000 0.0500
4.0000 0.2000
5.0000 0.1000
6.0000 0.4000
7.0000 0.1000
% file mcalc02.m Data for computer survey
minvec3
DV = [A|Ac; A; B; C; A&B&C; A&C; (A&B)|(A&C)|(B&C); ...
2*(B&C) - (A&C)];
DP = 0.001*[1000 565 515 151 51 124 212 0]; TV = [A|B|C; Ac&Bc&C];
disp('Call for mincalc')
>> mcalc02
Call for mincalc
>> mincalc
Data vectors are linearly independent
Computable target probabilities
1.0000 0.9680
2.0000 0.0160
The number of minterms is 8
The number of available minterms is 8
Available minterm probabilities are in vector pma
To view available minterm probabilities, call for PMA
>> disp(PMA)
0 0.0320
1.0000 0.0160
2.0000 0.3760
3.0000 0.0110
4.0000 0.3640
5.0000 0.0730
6.0000 0.0770
7.0000 0.0510
% file mcalc03.m Data for opinion survey
minvec4
DV = [A|Ac; A; B; C; D; A&(B|Cc)&Dc; A|((B&C)|Dc) ; Ac&B&Cc&D; ...
A&B&C&D; A&Bc&C; Ac&Bc&Cc&D; Ac&B&C; Ac&Bc&Dc; A&Cc; A&C&Dc; A&B&Cc&Dc];
DP = 0.001*[1000 200 500 300 700 55 520 200 15 30 195 120 120 ...
140 25 20];
TV = [Ac&((B&Cc)|(Bc&C)); A|(B&Cc)];
disp('Call for mincalc')
>> mincalc03
Call for mincalc
>> mincalc
Data vectors are linearly independent
Computable target probabilities
1.0000 0.4000
2.0000 0.4800
The number of minterms is 16
The number of available minterms is 16
Available minterm probabilities are in vector pma
To view available minterm probabilities, call for PMA
>> disp(minmap(pma)) % Display arranged as on minterm map
0.0850 0.0800 0.0200 0.0200
0.1950 0.2000 0.0500 0.0500
0.0350 0.0350 0.0100 0.0150
0.0850 0.0850 0.0200 0.0150
The procedure mincalct
A useful modification, which we call mincalct, computes the available target
probabilities, without checking and computing the minterm probabilities. This procedure
assumes a data file similar to that for mincalc, except that it does not need the target
matrix
Suppose mincalc has been applied to the data for the opinion survey and that it
is desired to determine
>> mincalct
Enter matrix of target Boolean combinations (A&D)|(B&Dc)
Computable target probabilities
1.0000 0.2850
Repeated calls for mcalct may be used to compute other target probabilities.