Application Center - Maplesoft

App Preview:

Converting truth tables into Boolean expressions

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application


Converting truth tables into Boolean expressions 

Dr.Laczik B?lint HUNGARY, Technical University of Budapest 


The simple method for designing such a circuit is found the normal form of Boolean expressions. The worksheet demonstrate the applicaton of Maple for the simplification of Boolean expressions by Maxterm-Minterm Methode.
The logic system is shown in the next figure.
 

 

The number of input Boolean variables is nu  (`<=`(nu, 4) ). 

The variables A, B, C, .., and they negated a = not(A), b = not(B), c = not(C), ..., are defined in the array 

 

                                                        var :=[A,a,B,b,C,c, ...,] 

             

The full truth table of input variables is 

                                                           

 

The number of different inputs is `assign`(Nu, `^`(2, nu)). The outputs [0,, ..., 0] and [1,,...,1] are not used, buth all of different permutations with length `assign`(Mu, `*`(2, `*`(nu))) of 0 and 1 elements are practicable. The number of the different outputs is  `assign`(NUMOUT_MAX, `+`(`^`(2, Nu), `-`(2)))

The binary form of the number n is the  n-th value  of the truth table! 

The pre-defined Boolean rules for the simplification are: 

`assign`(rules1, [`*`(`^`(A, 2)) = A, `*`(`^`(a, 2)) = a, `*`(`^`(B, 2)) = B, `*`(`^`(b, 2)) = b, `*`(`^`(C, 2)) = C, `*`(`^`(c, 2)) = c, () .. (), `*`(a, `*`(A)) = 0, `*`(b, `*`(B)) = 0, `*`(c, `*`(C... 

 

 

The maxterm is sum of products of the input variables for logic value 1 . The minterm is product of sum's of the input variables for logic value 0. 

 

The maxterm is defined by very simple way as
                                                                 `assign`(maxterm, sum(`*`(U[i], `*`(ss[i])), i = 1 .. Nu)) 

   

The minterm derived by the following recursion:
 

                                                               `assign`(minterm, 1) 

                                                               for i to Nu do if U[i] = 0 then `assign`(minterm, `*`(minterm, `*`(q[i]))) end if end do 


The choose between  maxterm or minterm depend from the number of its operator. So 

 

if `<`(nops(expand(minterm)), nops(maxterm)) then `assign`(tipus,
if `<`(nops(expand(minterm)), nops(maxterm)) then `assign`(tipus,
if `<`(nops(expand(minterm)), nops(maxterm)) then `assign`(tipus,
if `<`(nops(expand(minterm)), nops(maxterm)) then `assign`(tipus,  

 

In first step we substitute all of the subexpressions rules1 into an expression minterm S:
 

                                         for ii to `*`(2, `*`(Mu)) do `assign`(S, expand(algsubs(rules1[ii], S))) end do 

 

In second step we substitute all of the subexpressions rules2[j] into an expression S two time: 

 

                                                          for ii to 2 do for j to 20 do `assign`(S, expand(subs(rules2[j], S))) end do end do 

 

The next step is the application of Boolean rules the so-called redundance law. If the expression for variables P and Q in form yield by 

 

                                                            expression = Q + P*Q 

 

then 

                                                           expression = Q + P*Q = Q*(1 + P) = Q 

 

For the simplification we define the matrix T with n columns and n rows where n = nops(S). In general 

 

                                                            `assign`(T[ii, jj], `/`(`*`(op(ii, S)), `*`(op(jj, S)))) 

 

If the denominator of element T[ii, jj]  is   denom(T[ii, jj]) = 1    and  `<>`(T[ii, jj], 1)   then   the iist element of S is 

 

                                                                 `assign`(SS, `+`(SS, `-`(op(ii, S)))) 

If the logic form is
                                                SS = P.q + P.Q + R = P.(q + Q) + R = P + R 

 

we apply the possible Boolean rule by matrice 

                                                                               `assign`(T[iI, j], `/`(`*`(op(iI, SS)), `*`(var[j]))) 

We can the number of operators SS to reduce by following loop: 

 

for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `...
for iI to N do for j to nu do `assign`(p1, T[iI, `+`(`*`(2, `*`(j)), `-`(1))]); for k to N do `assign`(p2, T[k, `*`(2, `*`(j))]); if `+`(p1, `-`(p2)) = 0 then `assign`(SSS, `+`(SSS, `-`(op(iI, SS)), `... 

 

    The  values of input variables kezd are `<=`(1, kezd[1])  ,  `<=`(kezd[1], NUMOUT_Max), `<=`(kezd[1], kezd[2])     

     

> restart; with(linalg); with(ArrayTools); with(StringTools)
 

> for xi to 4 do `assign`(u, Char(`+`(64, xi))); `assign`(v, Char(`+`(96, xi))); `assign`(var[`+`(`*`(2, `*`(xi)), `-`(1))], convert(u, name)); `assign`(var[`*`(2, `*`(xi))], convert(v, name)) end do
for xi to 4 do `assign`(u, Char(`+`(64, xi))); `assign`(v, Char(`+`(96, xi))); `assign`(var[`+`(`*`(2, `*`(xi)), `-`(1))], convert(u, name)); `assign`(var[`*`(2, `*`(xi))], convert(v, name)) end do
for xi to 4 do `assign`(u, Char(`+`(64, xi))); `assign`(v, Char(`+`(96, xi))); `assign`(var[`+`(`*`(2, `*`(xi)), `-`(1))], convert(u, name)); `assign`(var[`*`(2, `*`(xi))], convert(v, name)) end do
 

> `assign`(nu, 3)
 

> `assign`(Nu, `^`(2, nu)); `assign`(Mu, `*`(2, `*`(nu))); `assign`(NUMOUT_MAX, `+`(`^`(2, Nu), `-`(2)))
 

`assign`(NUMOUT_MAX, 254) (1)
 

> kezd:=238,242:
 

> `assign`(k, convert(1, symbol)); `assign`(M, matrix(Nu, `*`(2, `*`(nu)), []))
 

> for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
for xi to Nu do `assign`(p, convert(`+`(xi, `-`(1)), binary)); `assign`(q, convert(p, string)); while `<`(Length(q), nu) do `assign`(t, cat(0, q)); `assign`(q, convert(t, string)) end do; `assign`(hx,...
 

> `assign`(n, 0); `assign`(ss, vector(Nu, 1)); `assign`(q, vector(Nu, 0)); `assign`(minterm, 1); `assign`(n, 0); `assign`(SS, 0)
 

> for i to Mu do `assign`(rules1[i], `*`(`^`(var[i], 2)) = var[i]) end do; for i to Mu do `assign`(rules1[`+`(Mu, i)], `*`(var[`+`(`*`(2, `*`(i)), `-`(1))], `*`(var[`*`(2, `*`(i))])) = 0) end do
 

> for i to 20 do `assign`(rules2[i], i = 1) end do
 

> for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
for i to Nu do for j to Mu do if M[i, j] = 1 then `assign`(ss[i], `*`(ss[i], `*`(var[j]))) end if; if M[i, j] = 0 then `assign`(q[i], `+`(q[i], var[j])) end if end do end do; unassign('i')
 

> `assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
`assign`(Hw, matrix(`+`(kezd[2], `-`(kezd[1]), 1), Nu, [])); `assign`(qq, convert(0, string)); for i from kezd[1] to kezd[2] do `assign`(inn, `+`(i, `-`(kezd[1]), 1)); `assign`(p, convert(`+`(kezd[1],...
 

> printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
 

  (2)
 

                        Converting truth tables into Boolean expressions (2)
 

  (2)
 

        Logic variables and truth table of inputs: (2)
 

v (2)
 

(2)
 

  (2)
 

      1    Output values [1, 1, 1, 0, 1, 1, 1, 0] (2)
 

           Boolean function is from MAXTERM = B*c+b (2)
 

______________________________________________________________________________ (2)
 

      2    Output values [1, 1, 1, 0, 1, 1, 1, 1] (2)
 

           Boolean function is from MINTERM = A+b+c (2)
 

______________________________________________________________________________ (2)
 

      3    Output values [1, 1, 1, 1, 0, 0, 0, 0] (2)
 

           Boolean function is from MAXTERM = a (2)
 

______________________________________________________________________________ (2)
 

      4    Output values [1, 1, 1, 1, 0, 0, 0, 1] (2)
 

           Boolean function is from MAXTERM = A*B*C+a (2)
 

______________________________________________________________________________ (2)
 

      5    Output values [1, 1, 1, 1, 0, 0, 1, 0] (2)
 

           Boolean function is from MAXTERM = A*B*c+a (2)
 

______________________________________________________________________________ (2)
 

Verification 

> restart
 

`assign`(F, `or`(`and`(B, not C), not B)) 

> `assign`(F, `or`(`or`(A, not B), not C))
 

`assign`(F, not A) 

`assign`(F, `or`(`and`(`and`(A, B), C), not A)) 

`assign`(F, `or`(`and`(`and`(A, B), not C), not A)) 

> `assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
`assign`(X, [false, true]); `assign`(Y, X); `assign`(Z, Y); for i to 2 do `assign`(A, X[i]); `assign`(AA, piecewise(A = true, 1, 0)); for j to 2 do `assign`(B, Y[j]); `assign`(BB, piecewise(B = true, ...
 

   
 

     A = 0    B = 0      C = 0     F = 1  
 

   
 

     A = 0    B = 0      C = 1     F = 1  
 

   
 

     A = 0    B = 1      C = 0     F = 1  
 

   
 

     A = 0    B = 1      C = 1     F = 0  
 

   
 

     A = 1    B = 0      C = 0     F = 1  
 

   
 

     A = 1    B = 0      C = 1     F = 1  
 

   
 

     A = 1    B = 1      C = 0     F = 1  
 

   
 

     A = 1    B = 1      C = 1     F = 1  
 

>  
 

>  
 

>