Logic

I studied this formally in SE212. The logic that we use in SE212. The logic that we use in Artificial Intelligence is also super interesting.

Logic is “the science of correct reasoning”. Logic is concerned with what is true and how we can know whether something is true.

A logic consists of 3 parts:

• Syntax: What is an acceptable sentence in the logic?
  • The syntax of a logic defines what is a “well-formed formula” (wff).
• Semantics: What do the symbols and sentences in the logic mean?
• Proof Theory: How do we construct valid proofs in the logic?

$|-$ → Proof Theory, pronounced “proves”

• proof theory = “proof” $\models$ → Semantics, pronounced “entails” / “valid” / “semantic entailment”
• Semantics = “truth”

We relate Semantics (truth/valid, $\models$) and Proof Theories (proof and $|-$) by the concepts of Soundness and Completeness, which are qualities of the Proof Theory.

In SE212, we cover two types of logic:

• Propositional Logic
• Predicate Logic

Next

Go to Propositional Logic for the discussion about Tautology, and how we can use Tautology, and how we can use Proof Theory to prove things.

Difference between syntax and semantics?

Syntax does not have meaning without a definition of the semantics.

We are used to working in the syntax space, and we ourselves already mapped meaning of the syntax to operators on truth values.

But syntax is just symbols and rules for creating wff. The thing that gives the equation meaning is Semantics.

• Ex: If you write $P\wedge Q$, that is syntax. On its own doesn’t mean anything.
• If you want to evaluate whether that expression is true, you need Semantics, to extract “meaning”, the “truth” of what that actually means
• We can write $[P\wedge Q]$, which maps to the semantics $[P]\text{ AND }[Q]$, where
• The $[]$ brackets tells us to do a Boolean Valuation, mapping syntax to value, see the BV page