BooleanTransformations.frink

View or download BooleanTransformations.frink in plain text format


// These transformation rules are found in Fundamentals of Logic Design,
// Third Editition, by Charles H. Roth, Jr.  p. 37
// The comments refer to the equation number in this book.
transformations Boolean
{
   // Operations with false and true
   _x OR false <-> _x            // 1
   _x OR true  <-> true          // 2

   _x AND true  <-> _x           // 1D
   _x AND false <-> false        // 2D

   // Idempotent laws
   _x OR  _x        <-> _x       // 3
   _x OR  _x  OR _y <-> _x OR _y // 3 with other parts
   
   _x AND _x        <-> _x        // 3D
   _x AND _x AND _y <-> _x AND _y // 3D with other parts.

   // Involution law
   !(!_x) <-> _x                 // 4

   // Laws of complementarity
   _x OR  !_x        <-> true    // 5
   _x OR  !_x  OR _y <-> true    // 5 with other parts
   
   _x AND !_x        <-> false   // 5D
   _x AND !_x AND _y <-> false   // 5D with other parts

   // Commutative and associative laws are built in to Frink's handling
   // of AND and OR operators, so they don't need to be implemented here.

   // Distributive laws (reversed for simplification.)
   (_x AND _y) OR (_x AND _z)        <->  _x AND (_y OR _z)      // 8, reversed
   (_x AND _y) OR (_x AND _z) OR _o  <-> (_x AND (_y OR _z)) OR _o // 8 reversed
   
   (_x OR _y) AND (_x OR _z)          <->  _x OR (_y AND _z)  // 8D, reversed
   (_x OR _y) AND (_x OR _z) AND _o   <-> (_x OR (_y AND _z)) AND _o  // 8D, reversed plus other parts

   // Simplification theorems
   (_x AND _y) OR (_x AND !_y)       <-> _x         // 9
   (_x AND _y) OR (_x AND !_y) OR _z <-> _x  OR _z  // 9 plus other parts
   
   (_x OR _y) AND (_x OR !_y)        <-> _x         // 9D
   (_x OR _y) AND (_x OR !_y) AND _z <-> _x AND _z  // 9D plus other parts
   
   _x OR (_x AND _y)           <-> _x           // 10
   _x OR (_x AND _y) OR _z     <-> _x OR _z     // 10 plus other parts
   
   _x AND (_x OR _y)           <-> _x           // 10D
   _x AND (_x OR _y) AND _z    <-> _x AND _z    // 10D plus other parts
   
   (_x OR !_y) AND  _y          <-> _x AND  _y         // 11
   (_x OR !_y) AND  _y AND _z   <-> _x AND  _y AND _z  // 11, plus parts
   (_x OR  _y) AND !_y          <-> _x AND !_y         // 11, converse
   (_x OR  _y) AND !_y AND _z   <-> _x AND !_y AND _z  // 11, converse, plus
   
   (_x AND !_y) OR  _y          <-> _x OR  _y          // 11D
   (_x AND !_y) OR  _y OR _z    <-> _x OR  _y OR _z    // 11D plus extras
   (_x AND  _y) OR !_y          <-> _x OR !_y          // 11D, converse
   (_x AND  _y) OR !_y OR _z    <-> _x OR !_y OR _z    // 11D, converse, plus

   // Consensus theorem
   (_x AND_y) OR (_y AND_z) OR (!_x AND _z)        <-> (_x AND _y) OR (!_x AND _z)   // 17
   (_x AND_y) OR (_y AND_z) OR (!_x AND _z) OR _o  <-> (_x AND _y) OR (!_x AND _z) OR _o  // 17 plus others
   
   (_x OR _y) AND (_y OR _z) AND (!_x OR _z)        <-> (_x OR _y) AND (!_x OR _z) // 17D
   (_x OR _y) AND (_y OR _z) AND (!_x OR _z) AND _o <-> (_x OR _y) AND (!_x OR _z) AND _o // 17D   
}


View or download BooleanTransformations.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17682 days, 18 hours, 48 minutes ago.