## 24029Re: [Clip] VanWeerthuizenian Expressions

Expand Messages
• Sep 13, 2013
• 0 Attachment
At 9/10/2013 05:11 PM, Flo wrote:
>It has been discussed several times that NT doesn't master Boolean Expressions (cf message #21773). And we considered tools like DOS Findstr, Agent Ransack etc to be used in this case. It should also be mentioned that, to some extent, we could simulate Boolean Expressions with RegEx.
>
>Some years ago, Wayne VanWeerthuizen described another approach in his 'NoteTab Tutorial Control Structures v003.OTL' (see the 'File' section of this group).
>
>I picked up another topic (#22762) and tried to find a solution for that job based on instructions given by Wayne in his tutorial.
>
>Example: We've got five lines...
>
>tR4hGGUK
>2UJeiy9m
>WbNDSk9e
>Mytrip12
>My.tip12
>
>The task is to select lines which fulfill five criteria:
>
>(A) 8 characters
>(B) at least 2 upper characters
>(C) at least 2 lower characters
>(D) at least one digit
>(E) no punctuation characters or spaces

Flo, If I can jump in here. [Sorry for the length. This was meant to be a quicky but it grew!]

In testing boolean expressions I prefer converting them to simple arithmetic expression rather than a series of IF - Than - Else trees. If you restrict the values of your logical variables to either zero or one you can take advantage of the common properties between arithmetic and logic systems and use arithmetic instead of if tests to evaluate logical expressions.

Since zero is the identity element for addition and one is the identity element for multiplication and letting one equal true and zero equal false, one can map all logical operations and expressions onto equivalent arithmetic operations and expressions.

Basic properties:
=================
Identity Elements: 0, 1 (Add, Mult) <==> False, True (OR, AND)
Operators: Negation, Mult, Add, MOD <==> NOT, AND, OR, XOR
Distributive: I AND (J OR K) == (I AND J) OR (I AND K)
Commutative: (I  J) == (J  I)
Associative: (I  J  K) == (I  J)  K == I  (J  K)
Where  = either OR or AND; Optional parentheses added for clarity

Logical Identities ( De Morgan's Laws)
========================================
A OR False = A
A AND TRUE = A
NOT (A AND B) = (NOT A) OR (NOT B) 
NOT (A OR B) = (NOT A) AND (NOT B) 
(A XOR B) = (A AND NOT B) OR (NOT A AND B)

Logical - Arithmetic Equivalents
================================
A OR FALSE <==> A + 0 = A
A AND TRUE <==> A * 1 = A
A OR B <==> MAX (A, B)
A AND B <==> A * B
NOT A <==> (A + 1) MOD 2
A XOR B <==> (A + B) MOD 2
NOT A AND B <==> (MIN (A, B) + 1) MOD 2
NOT A OR B <==> (MAX (A, B) + 1) MOD 2
NOT A XOR B <==> ((A + B) Mod 2 + 1) MOD 2 == (A + B + 1) Mod 2

[Hopefully Yahoo's reformatting doesn't bastardize those tables too much. See separate post and uploaded file for clips implementing each of the above seven non-trivial operations. These tables and more info is included in the uploaded cliplib.]

^!If ^\$Calc(MIN(^%A%;MIN(^%B;MIN(^%C%;MIN(^%D%;1-^%E%)))))\$=1 Next Else Skip

reduces to just the product of the variables:

^!If ^\$Calc(^%A%*^%B*^%C%*^%D%*^%E%)\$=1 Next Else Skip

The analogous test for unions would simply be the sum of the variables compared to zero. However, for more complex expressions that doesn't work since using a sum operation for unions can result in values not contained in the set {0,1}. However, by using the above identities it is possible to transform any expression into a pure product expression (or other form), which might or might not simplify your code. For example:

(A AND B AND C) OR (B AND NOT D)

is equivalent to

NOT (A AND B AND C) AND NOT (B AND NOT D)

Note also that since the operations are commutative, associative and distributive, B may be "factored" out to make an equivalent expression (from the original):

B AND ((A AND C) OR (NOT D))

As you can see, you can play around with logical expressions just like we did with trig equations in HS to simplify (or to make them more complex).

For specific applications you can write down and optimize the truth table (I forget what the name for the process is). This is done quite frequently for logic circuits as the optimization pays off in reduced components and gate delays. That may not be as beneficial for software. There is a formal process that guarantees an optimum result but is has been too many years to remember. Short of that just eye balling the truth table could reveal some useful reductions. For four input conditions it is only a 16 by 16 table. Or you could use the logic functions I will post later.

All this is a perfect example for the need for Notetab to fully support custom functions. By fully support I mean supporting Far Functions and being usable in clipbar clips. Custom functions are very useful and handy tools. They can make the code easier to write and program flow much more transparent. They greatly reduce code size (at least by 50% where you can use them). Thanks to Ian Ntnerd's post last August there is a workaround for FarFunctions. However, custom functions still have one fatal deal-breaking (for me), drawback: They CANNOT be reliably used for any clipbar clips!

In Notetab, all variables are global but the clipbar uses a
separate storage area
Variable values set in clipbook panel are not seen by clip
bar clips & vice versa
Clipbar clip variables are not global across different clipbooks

Perhaps if we make enough noise and we can get the no clipbar restriction removed. It would greatly enhance the clip functionality and ease coding efforts.

Namaste', Art

OK, this was bugging me so I had to look it up. Geesh. it's only been 40+ years. One shouldn't forget so soon!!!

The process of optimizing a truth table is called a Karnaugh map
http://en.wikipedia.org/wiki/Karnaugh_map
The formal name for the Boolean identities above is De Morgan's laws
http://en.wikipedia.org/wiki/De_Morgan%27s_laws

Two other terms that you may want to look up are "Disjunctive Normal Form (DNF)" and its dual, the "Conjunctive Normal Form (CNF)".
http://en.wikipedia.org/wiki/Disjunctive_normal_form
http://en.wikipedia.org/wiki/Conjunctive_normal_form

These are canonical forms for describing the truth table for a system. A DNF is a disjunction of conjunctive clauses, also known as an "OR of ANDs" or a "sum of products". A CNF is a conjunction of a disjunction of literals, also known as an "AND of ORs" or a "product of sums". Basically they are fully expanded forms that involve only one level of parentheses.
• Show all 12 messages in this topic