Logic

tags : Functional Programming, Type Systems, Programming Languages, Math

FAQ §

Propotional vs Predicate Logic §

Quantifications §

• Quantification means making statements about things.
• In logic, this often involves variables that stand for different things in a domain.
• Properties are characteristics/attributes that you can talk about. Eg. “even” and “prime” are properties of numbers.

First order §

In both these cases, we’re talking about some individual element/variable

• Universal Quantifier (∀)
  • This symbol (∀) is like saying “for all” or “for every.” It allows us to make statements about every individual element in a certain group or domain. Let’s use an example to illustrate this:
  • Example: Consider the domain of natural numbers. If we say ∀x (x is greater than 0), it means that we are making a statement about every natural number. In simpler terms, it’s like saying “Every natural number is greater than 0.” This statement covers all the numbers in the domain of natural numbers.
• Existential Quantifier (∃)
  • This symbol (∃) is like saying “there exists” or “there is at least one.” It allows us to make statements about the existence of at least one individual element in a certain group or domain. Here’s an example:
  • Example: Using the domain of natural numbers again, if we say ∃x (x is even), it means that we are making a statement about the existence of at least one even number in the group of natural numbers. So, it’s like saying “There exists a natural number that is even.” This statement doesn’t specify which number it is; it simply asserts that there is at least one.

Second order §

In second order, we’re usually quantifying about property in some domain

• property as set : Sets of individual things that have that property. For example, the set of all even natural numbers is a set that includes 2, 4, 6, and so on.
• property as fn: functions that take in an element and return a Boolean indicating whether the element satisfies the property. (Characteristic function)

Third order §

In third and other higher orders, we’re usually quantifying about property of properties

• Eg. “All properties of sets of cats have the property of being mammal-related.” (Here, you’re not only looking at sets of cats but also at properties of those sets. i.e You’re reasoning about the property)
• Even though higher-order logics seem more powerful and expressive, you can still capture their ideas and statements using second-order logic.

Implementation §

Datalog §

• https://github.com/fkettelhoit/bottom-up-datalog-js/tree/master