Artificial Intelligence/Logic Types

Propositional Logic

Propositional Logic is "declarative" logic, in that syntax corresponds to facts. In fact, it can be summarized as "assuming the world contains facts".

Seems to generally be the "default" way of thinking about logic, for programming and math. Ex: Discrete Math/Propositional Logic.

This form of logic tends to be compositional. That is, smaller sections of statements can be combined to form a larger meaning, and it's generally context-independent.

However, it has some fallbacks. For example, it struggles to accurately describe full sets of objects, and can also struggle to define relationships between objects.

For example, when trying to describe a set, it generally needs to describe each individual object in the set, instead of describing the set at large (and by extension, all objects within the set).

First-Order Logic

First-Order Logic is similar to natural language. It tends to assume the world contains:

• Objects - People, places, numbers, colors, ...
• Relations - Bigger than, inside, red, brother of, ...
• Functions - Parent of, one more than, end of, ...

First-Order Logic also tends to use symbols to represent values:

• Variables - x, y, a, b, ...
• Constants - KingJohn, 2, ...
• Predicates - Brother, >, ...
• Functions - P(x, y), Sqrt(), LeftLegOf(), ...
• Connectives - ∧, ∨, ⇒, ⇔, ...
• Quantifiers - ∀, ∃, ...

Complex sentences tend to be made by combining individual parts via connectives.

Basic Examples

For example, given:

• xyz - Describes a specific population.
• At(x, <location>) - Function to describe a population at a given location.
• Smart(x) - Function to describe part of a population that is smart.

We can quickly describe an entire set of the college student population:

# States "Everyone at College is smart."
∀xyz At(xyz, College) ⇒ Smart(xyz)

Not to be mistaken for:

# States "Everyone is at College and everyone is smart."
∀xyz At(xyz, College) ∧ Smart(xyz)

Similarly, instead of universal quantifiers, we can use existential quantifiers:

# States "Someone is at College and they are smart." Aka "Someone at College is smart."
∃xyz At(xyz, College) ∧ Smart(xyz)

Note: Typically, universal (∀) uses implications (⇒) while existential (∃) uses and (∧).

Further Examples

# "All birds fly."
∀x Bird(x) ⇒ Fly(x)

# "All birds except penguins fly."
∀x Bird(x) ∧ ¬Penguin(x) ⇒ Fly(x)

# "Every kid likes candy."
∀x Kid(x) ⇒ Likes(x, candy)

# "Some kids like candy."
∃x Kid(x) ∧ Likes(x, candy)

# "Brothers are siblings."
∀x,y Brothers(x,y) ⇒ Siblings(x,y)

# "One's mother is one's female parent."
∀x,y Mother(x,y) ⇒ Female(x) ∧ Parent(x,y)

Other Forms of Logic

Not covered in-depth here, but possibly worth examining in the future:

• Temporal Logic
• Probability Theory - Degree of Belief
• Fuzzy Logic - Known Internal Values