lull.gif

Logic

Language Ontological Commitment Epistemological Commitment
PL fact true|false|unknown
FOL facts, objects, relations true|false|unknown
TL facts, objects, relations, times true|false|unknown
Probability Theory facts degree of beliefe
Fuzzy Logic facts + degree of truth known interval value

Truth Table

A tabulation of the value of a proposition for all possible values of its variables.

Syntax

Symbol Meaning Read
α ⋀ β Logical AND α and β
α ⋁ β Logical OR (inclusive-or) α or β
α ⊕/⊻ β Logical XOR (exclusive-or) No english word for it, in latin it is aut
¬α Logical NOT not α
α ⊢i β Inference i derives β from α
α ⊨ β Entailment α entails β (Identical to α ⇒ β in propositional logic only)
α ⇒ β ?Logical? Implication α implies that β; if α then β; β is necessary for α, but α is sufficient for β
α ⇔/iff β Logical Bi-Conditional If and only if
α ≡ β Logical Equivalence is equivalent to (Same as ⇔ in Propositional Logic)
∀β For All for all β...
∃β Exists there exists some β such that...
∃!β Uniquely Exists ...there exists 1 (unique) β such that...
  • conjunction
    • A sentence whose main connective is ⋀ is called a conjunction; its parts being the conjuncts.
  • disjunction
    • A sentence using ⋁ is a (inclusive) disjunction of its disjuncts (components padding the ⋁). It is inclusive because to be true either of, or both of its components must be true.
    • A sentence using ⊕, or ⊻, is an exclusive disjunction similarly.
    • As an example, when a menu says cream or sugar, it is using an implied inclusive-or, because you may take one, the other, or both. On the other hand if it says coffee or tea, it is using an exclusive-or, because you are not invited to take both or some kind of a cocktail mix - you'll notice lame or occasionally-funny comedy lines in movies are derived by manipulating the the inclusive-or to an exclusive-or and vise versa.
  • inference
    • KB ⊢i α - i derives α from KB
    • Think of the needle (α) in a haystack(all consequences of KB).
    • An inference algorithm that derives only entailed sentences is called sound or truth-preserving.
      • Soundness is a highly desired property.
  • entailment
    • α ⊨ β - Sentence α entails sentence β, iff in every model in which α is true, β is true.
    • KB ⊨ q - q is true in every model of KB, including m, where m is a model of KB
  • In LHS ⇒ RHS, the premise or antecedent(logically preceding element) is the LHS, and its conclusion or consequent is the RHS.

Logical Equivalence

(α ⋀ β) (β ⋀ α) Commutativity
((α ⋀ β) ⋀ γ) (α ⋀ (β ⋀ γ)) Associativity
(α ⇒ β) (¬α ⋁ β) Implication Elimination
(α ⇔ β) ((α ⇒ β) ⋀ (β ⇒ α)) Bi-Directional Elimination
(α ⇔ β) ¬(α ⊕ β) Elimination
Double-Negation
(α ⇒ β) (¬β ⇒ ¬α) Contraposition
¬(α ⋁ β) (¬α) ⋀ (¬β) De Morgan's Law - Negation of Disjunction
¬(α ⋀ β) (¬α) ⋁ (¬β) De Morgan's Law - Negation of Conjunction
(α ⋀ (β ⋁ γ)) (α ⋀ β) ⋁ (α ⋀ γ)) Distribution of ⋀ over ⋁
(α ⋁ (β ⋀ γ)) (α ⋁ β) ⋀ (α ⋁ γ)) Distribution of ⋁ over ⋀

Key Concepts

  • Equivalence
    • (α ≡ β) ⇔ ((α ⊨ β) ⋀ (β ⊨ α))
  • Validity
    • A sentence is only valid if it is true in all models.
  • Satisfiability
    • A sentence is satisfiable as long as it is true in some model.
    • "m is a model of α" (or "m satisfies α") means that sentence α is true in model m.
  • Monotonicity
    • if KB ⊨ α then KB ⋀ β ⊨ α

Proof by Contradiction

Here we try and prove that KB ⊨ α, by showing that KB ⋀ ¬α is unsatisfiable.

Semantics

A logic must define the semantics of the language; i.e. semantics has to do with the meaning of sentences.

Axioms, Postulate

Among the ancient Greek philosophers an axiom was a claim which could be seen to be true without any need for proof. In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be self-evident. Therefore, its truth is taken for granted, and serves as a starting point for deducing and inferring other (theory dependent) truths. In short, an axiom is a proposition that is assumed to be true.

As an example, the following is as good an example as any axiom...

if a = b and b = c then a = c

For those with a background in chemistry, you'd notice a similarity between this axiom and the 0th law of thermodynamics which states If a thermodynamic system A is in thermal equilibrium with a thermodynamic system C, and a thermodynamic system B is in thermal equilibrium with a thermodynamic system C, then A and B are also in thermal equilibrium with each other.

For further reading, see the MIT material referenced at the bottom of this page.

References

Ancstors ☣ ..
Other ☣ Agent/Logical ☣ Mathematics