Posts tagged ‘logic’

Implication as an Operator

2013-06-02 18:28

A vast majority of code is dealing with logical conditions by using three dedicated operators: not (negation), and (conjunction), or (alternative). These are often written as !, && and ||, respectively, in C-like programming languages.

In principle, this is sufficient. Coupled with true and false, it’s enough to encode any boolean function of zero, one or two arguments. But language designers didn’t seem to be concerned with minimalism here, because it’s possible to replace those three operators with just one of the following binary functions:

  1. nand(x, y) = not (x and y)
  2. nor(x, y) = not (x or y)

If you can’t immediately see how, start with deriving negation first.
So we already have some redundancy for the sake of readability. While it’s surely a bad idea to try and incorporate all 22 before mentioned functions, isn’t there at least few others that would make sense as operators on their own?

I can probably think of one: the material implication (p \to q). It may seem like a weird choice at first, but there are certain common scenarios where such operator would make things more explicit.
Imagine for a second that some mainstream language (like Java) has been enhanced with operator => that acts as implication. Here’s one example of its straightforward usage:

  1. public class NameMatcher {
  2.     @Nullable private String firstName_;
  3.     @Nullable private String lastName_;
  4.  
  5.     public NameMatcher(@Nullable String firstName,
  6.                        @Nullable String lastName) {
  7.         firstName_ = firstName;
  8.         lastName_ = lastName;
  9.     }
  10.  
  11.     public boolean matches(String firstName, String lastName) {
  12.         return firstNameMatches(firstName) && lastNameMatches(lastName);
  13.     }
  14.  
  15.     private boolean firstNameMatches(String firstName) {
  16.         return matchFirstName() => firstName_.equals(firstName);
  17.     }
  18.     private boolean matchFirstName() {
  19.         return firstName_ != null;
  20.     }
  21.  
  22.     private boolean lastNameMatches(String lastName) {
  23.         return matchLastName() => lastName_.equals(lastName);
  24.     }
  25.     private boolean matchLastName() {
  26.         return lastName_ != null;
  27.     }
  28. }

Many situations involving “optionals” could take advantage of logical implication as an operator. Also note how in this case, the alternatives do not look very appealing at all. One could use an if statement to produce equivalent construct:

  1. private boolean firstNameMatches(String firstName) {
  2.     if (matchFirstName()) {
  3.         return firstName_.equals(firstName);
  4.     }
  5.     return true;
  6. }

but this makes a trivial one-liner suddenly look quite involved. We could also expand the implication using the equivalence law p \to q \equiv \neg p \lor q:

  1. private boolean matchFirstName(String firstName) {
  2.     return !matchFirstName() || firstName_.equals(firstName);
  3. }

Reader would then have to perform the opposite transformation anyway, in order to restore the real meaning hidden behind the non-obvious ! and || operators. Finally, we could be a little more creative:

  1. private boolean firstNameMatches(String firstName) {
  2.     return matchFirstName() ? firstName_.equals(firstName) : true;
  3. }

and capture the intent almost perfectly… At least until along comes someone clever and “simplifies” the expression into the not-a-or-b form presented above.

Does any language actually have the implication operator? Not surprisingly, the answer is yes – but it’s most likely a language you wouldn’t want to code in. Older and scripting versions of Visual Basic had the Imp operator, intended to evaluate the logical connective p \to q.
Besides provoking a few chuckles with its hilarious name, its usefulness was limited by the fact that it wasn’t short-circuiting. Both arguments were always evaluated, even if the first one turned out false. You may notice that in our NameMatcher example, such a behavior would produce NullPointerException when one of the names is null. This is also the reason why implication implemented as a function:

  1. bool implies(bool p, bool q) {
  2.     return !p || q;
  3. }

would not work in most languages, for the arguments are all evaluated before executing function’s code.

Tags: , ,
Author: Xion, posted under Math, Programming » 3 comments
 


© 2023 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.