How do I apply 'A Logical Approach to Discrete Math' to programming?

Question

I am a professional programmer and when I came across David Gries' book(rather expensive) and his website I was fascinated. This wasn't how I learnt to code(mainly Java but also basic Haskell and Ocaml ). But I couldn't understand how this mode of logic or math can be applied to application code. So I seek some guidance from those who really code like this. Can one read this rigorous book and learn to code ( mainly functional programming languages ) ? Is this logic and math directly applicable to code ?

Answer 1

I'd rephrase the question as Should I apply 'A Logical Approach to Discrete Math' to programming, and if so, how?

My answer to the rephrased question is No. Logic is a must but that approach doesn't work well.

Back in the 90ies we tested the book by using it to teach undergrads. The outcome was discouraging. Most students got lost in the myriad of rewrite rules and failed to see the forest for the trees. While doing so, they missed out on heaps of other relevant material typically taught under the discrete maths umbrella.

Nowadays, I'd argue that students are better served with a course along the lines of Lehman, Leighton, and Meyer's course at MIT, which is much stronger on intuitions and content. Combine that with Morgan's 'Programming from Specifications for learning how to use logical reasoning to derive beautiful imperative code.

For rigorous functional programming, equational reasoning comes in handy, yet I'd warn against pursuing that the Schneider & Gries way. There is no need to turn students into symbol-pushing rewrite systems. Computers are much better at that.

Once the value of logic (so far, propositional and predicate logic) is established, other logics can be introduced, for instance, temporal logic in the context of a course on concurrency.

Answer 2

Introduction

Studying logic and discrete mathematics prepares students for a powerful realization in their life:

Computer programmers use English words very differently than people outside of the profession of computer programming do.

The English word mist is used to describe times when you can see, smell, or taste that there are thousands of tiny droplets of water in the air.

The word mist is also a word in German, not just English. However, mist has a very different meaning in German than in English. I will let you look-up what it means. As a hint, the answer is not nebel and the answer is not fog or aerosolized water spray.

---

Logical Disjunction

Studying logic and discrete mathematics prepares students for the fact that computer programmers use the word or differently than people outside of the profession do.

In computer programming the word or is used the same way as the word or is used by mathematicians.

However, Americans use the word or differently in mathematics and computer programming than they do in every-day life.

Suppose that King Soopers might be the name posted on a sign hung above one building where food is sold.

Also, Mi Pueblo Market might be the name posted above a different building where food is sold, a building at least 100 meters away from King Soopers.

Someone might say:

We need spinach, eggs, cheese, and flour. Should we go to King Soopers OR Mi Pueblo Market?

In somthing related to common English parlance, we have:

# THIS USAGE IS *MORE* CONSISTENT WITH THE ENGLISH LANGUAGE, THAN CONSISTENT WITH MATH, RELATIVLY SPEAKING
 
or(a, b)          = exactly one of {a, b} is true
or(a, b, c)       = exactly one of {a, b, c} is true
or(a, b, c, d)    = exactly one of {a, b, c, d} is true
or(a, b, c, d, e) = exactly one of {a, b, c, d, e} is true

In logic, mathematics, and computer science,

The statement x1 or x2 or... xn
... means the same thing as...
the statement one or more of the statements x1 though xn is true

Studying logic and discrete mathematics prepares students for the fact that computer programmers use English words differently than normal people do.

The following argument is valid in English, but is invalid in mathematical logic:

Axiom 1. (We went to King Soopers for the groceries) or (we went to Mi Pueblo Market for the groceries).

Axiom 2. It is not the case that (we went to King Soopers for the groceries).

Conclusion. We must have gone to to Mi Pueblo Market for the groceries.

The standards for the English language define the word OR differently for English than for OR in logic.

The German word mist has the same meaning as the English word manure.

A string of text, such as mist or the word or can have different meanings in different languages.

Mathematics is a different language than English. The word or has a meaning in computer programming which seems alien to many people who know English, but who do not know very much mathematics or much about computer programming either.

In a programming language named MathJax some people write lor for logical-or instead of writing or.

Writing lor in computer programmes and writing or in English makes it very clear that the two words are different, but most computer programmers just write or.

---

---

The Universal Quantifier ∀

Studying logic and discrete mathematics prepares students for the fact that computer programmers use the following words and phrases differently than people outside of the profession of computer programming do.

• all
• every
• for any
• for each

Suppose that someone does not own a coin-operated laundromat.

The following statement is FALSE in English:

three of the washing machines inside of my coin-operated laundromat are broken.

The statement about three washing machines is TRUE in mathematical logic.

In mathematical logic, statements about non-existent things are always true.

In the English language, if something does not exist, then all statements about that thing are false.

For example, the statement Joe's step-father's brother's pet monkey likes to play the drums is false in English when:

• Joe does not exist.

• Joe exists, but Joe has no step-father

• Joe exists, and Joe has a step-father, but Joe's step-father has no brother.

• Joe exists, and Joe has a step-father, and the step-father has a brother, but the brother does not have a pet monkey.

• Joe exists, and Joe has a step-father, and the step-father has a brother, and the brother has a pet monkey, but it is not true that the monkey likes to play the drums.

In mathematical logic, if the category of things satisfying some property ends up being an empty category, then everything about that category is true.

Suppose that there was an elementary school in the year 2020 in some city.

Also, suppose that every child in that school had a cubby where a cubby is a plastic or wood bin which people put things in.

Suppose that Jill ate her snack, it is the end of the day, and she only has 20 minutes left before she goes home.

Consider the following statement:

For any snack, x, in Jill's Cubby, snack x is a Twinkie.

That statement is false in English, because there do not exist any snacks inside of Jill's cubby.

However, that statement is true in mathematical logic, discrete mathematics, and computer programming, because there do not exist any snacks inside of Jill's cubby.

---

Final Remarks

I am too tired to explain everything now, but suffice it to say that the key words and phrases to learn about are show below:

Predicates of One Input

• Logical Identity ... I(x) is true no matter what x is.

• Logical Contradiction ... NO(x) is false no matter what x is.

• Logical Negation ... NO(x) is false if x is true and NO(x) is true if x is false.

---

Predicates of Two Inputs

There are 16 predicates such that each predicate has two inputs, but only four of them are shown below:

Binary Logical Identity ... I(x, y) is always true. It does not matter if x is true or false, I(x, y) is still true. It does not matter if y is true or false either. We could write ∀ x, y ∈ {0, 1}, I(x, y) = 1 or for any x element of the category 0 or 1 and for any y element of the category 0 or 1, the identity of x and y is 1.

Binary Logical Contradiction ... I(x, y) is always false. It does not matter if x is true or false, I(x, y) is still true. It does not matter if y is true or false either.

• Logical Conjunction ... LAND(x, y) is true if and only if x and y are both true. Did you brush your teeth AND put your sort your clean laundry so that the clean socks are not mixed with shirts and shirt are not mixed together with pants?

• Logical Disjunction ... LOR(x1, x2, x3, ....). For example, You may take an apple and/or a piece of candy from Sam's house on Halloweens. Logical disjunction is the same as the English phrase and/or.

• Logical Implication ... NO(x) is false if x is true and NO(x) is true if x is false.

Predicates of Three or More Inputs

• We can have logical conjunction LAND(x1, x2, x3, ... xn) with three or more inputs. The output is true if and only if all of the inputs are true. If one or more inputs are false, the whole thing is false.

• We can have logical disjunction LOR(x1, x2, x3, ... xn) with three or more inputs. The output is true if and only if at least one of the inputs is true. If false of the inputs are false, then the output of LOR is false.

---

Set Theory

Sets are categories of things.

berries are an example of a subset of the set all edible fruits and vegetables.

The number 1 is an element of {1, 2, 3}

The number 5 is *not an element of {1, 2, 3}

Suppose that:

• a peanut is inside of a can of other peanuts.

• the can is inside of Joe's car

...then...

• the peanut is not inside of Joe's car

Why? Because if the can of peanuts is a set and Joe's car is a set, then we have the element-of operator ∈ is not transitive.

The Transitive Property of English words like in, was fun for certain strange mathematically inclined people, like myself, to learn about, and might be fun for you too.

---

The Universal Quantifier

Learn how to compute whether a statement is true or false when the statement contains a word or phrase such as any or all.

---

The Existential Quantifier

Learn how to compute whether a statement is true or false when the statement contains a word or phrase such as at least one.