Untitled

• Artificial Intelligence, A Course About Foundations, Propositional Logic by Marco Piastra.

Boolean Algebra(s) - Prologue

• Boolean algebras are examined through examples, considering a finite set of objects W.
• A collection ∑ of all possible subsets of W is constructed in a bottom-up fashion.
• Example 1) W = {a}.
• Example 2) W = {a, b}.
• Example 3) W = {a , b, c}.
• Each arrow represents set inclusion.
• Example) {a} ⊆ {a, b}.
• Collections like above are also called the power set of W.
• It’s the collection of all possible subsets of W, denoted as 2^W.
• Boolean algebra is defined as any non-empty collection of subsets ∑ of a set W.
• Empty set (Ø) is an element of ∑.
• If A and B are elements of ∑, then A ∪ B is also an element of ∑.
• If A is an element of ∑, then A' (complement of A with respect to W) is also an element of ∑.
• The set W always belongs to any Boolean algebra generated on it.
• ∑ is closed under intersection (∩).
• Properties of a Boolean algebra can be verified exhaustively for any of the structures.
• De Morgan's laws.
• (A ∪ B)^c = A^c ∩ B^c
• (A ∩ B)^c = A^c ∪ B^c
• Given that all boolean algebras share the same properties.
• The simplest one is adopted as ∑ := {W, Ø}
• It is a two-valued algebra ({nothing, everything}, {false, true}, {⊥, ⊤} or {0, 1}).
• Algebraic structure is defined as < {0,1}, OR, AND, NOT >.
• Boolean functions and truth tables: the most generic type of functions are f: {0, 1}^n → {0, 1}.
• AND, OR and NOT are boolean functions defined extensionally via truth tables.
• Truth tables can be defined for composite functions to verify logical laws.
• Formula to abide by: De Morgan's laws

Adequate Basis

• Defines the number of boolean functions needed to define any boolean function.
• Other function can be expressed as composite function.

The generic truth table consists of:

• For each row j, (where f_j = 1) create a Boolean expression composing by AND the n input variables.
• Take A_i when the i-th value is 1, or NOT A_i when i-th value is 0.
• Compose all expressions obtained above with OR.
• {OR, NOT} or {AND, NOT} are adequate bases.
• An adequate basis can be obtained by NOR or NAND.
• Two remarkable functions: implication and eequivalence are defined by truth tables.
• Logicians prefer the adequate basis {IMP, NOT}.

Language and Semantics, Possible Worlds

• Propositional logic is the simplest of 'classical' logics.
• Simple propositions state something that could be either true or false.
• ex) "Today is Friday", "Turkeys are birds with feathers".
• Formal semantics are a class of formal structures.
• Each representing a possible world, or a possible 'state of things;
• ex) <This classroom right now>, <Ancient Greece at the time of Aristotle's birth>.
• Possible world is a structure <{0,1}, Σ, v>

Structure Properties

• {0,1} gives the truth values.
• Σ is the signature of the formal language: a set of propositional symbols.
• v is a function : Σ → {0,1} assigning a truth value to every symbol in ∑.
• Each symbol in ∑ represents an actual proposition. By convention, symbols A, B, C, D, ... are used.
• The class of structures contains all possible worlds.
• All structures in a class share the same Σ and {0,1}.
• The functions v are different because, the assignment of truth values varies, depending on the possible world.

Formal language propositional

Propositional Language Lp

• A set ∑ of propositional symbols: Σ = {A, B, C, ...}
• Has two (primary) logical connectives: →, ¬
• And three (derived) logical connectives: ∧, ∨, ↔
• Has parenthesis: (,) (there are no precedence rules in its language)
• Well-formed formulae (wff) are defined via a set of syntactic rules:

The set of all the wff of Lp is denoted as wff(Lp)

• A ∈ Σ ⇒ A ∈ wff(Lp)
• φ ∈ wff(Lp) ⇒ (¬φ) ∈ wff(Lp)
• φ, ψ ∈ wff(Lp) ⇒ (φ → ψ) ∈ wff(Lp)
• φ, ψ ∈ wff(Lp) ⇒ (φ ∨ ψ) ∈ wff(Lp)
• φ, ψ ∈ wff(Lp) ⇒ (φ ∧ ψ) ∈ wff(Lp)
• φ, ψ ∈ wff(Lp) ⇒ (φ ↔ ψ) ∈ wff(Lp)

Formal semantics: interpretations

• Given a possible world <{0,1}, Σ, v>, the function v: Σ → {0,1} can be extended.
• Boolean functions are associated to each connective:
  • ν(¬φ) = NOT(ν(φ))
  • ν(φ ∧ ψ) = AND(ν(φ), ν(ψ))
  • ν(φ ∨ ψ) = OR(ν(φ), ν(ψ))
  • ν(φ → ψ) = OR(NOT(ν(φ)), ν(ψ)) (also IMP(ν(φ), ν(ψ)) )
  • ν(φ ↔ ψ) = AND(OR(NOT(ν(φ)), ν(ψ)), OR(NOT(v(ψ)), ν(φ)))
• Function v assigns a truth value to each φ ∈ wff(Lp).
• v: wff(Lp) → {0,1}
• Then v is said to be an interpretation of Lp.
• The truth value of any wff φ is univocally determined by the values assigned to each symbol in the signature Σ (compositionality).

Object Language and Metalanguage

• Object language is Lp. It is the formal language of logic.
• It only contains the defined items which are Σ, →, ¬, ∧, ∨, ↔, (, ), plus syntactic rules (wff)

Meta-Language

• It is the formalism for defining the properties of the object language and the logic.
• Small Greek letters (α, β, χ, φ, ψ, ...) denote a generic formula (wff).
• Capital Greek letters (Γ, Δ, ...) denote a set of formulae.
• Symbols:
  • |= is for satisfaction, logical consequence.
  • ⊢ is for derivability.
  • "iff" is for "if and only if".
  • =>, <=> are for implication, equivalence.

Entailment

• Entailment examines formulae and thier hidden relationships
• Hypothesis:
• φ1 = B ∨ D ∨ ¬(A ∧ C) represents "Sally likes Harry" OR "Harry is happy" OR NOT ("Harry is human" AND "Harry is a featherless biped")
• φ2 = B ∨ C represents "Sally likes Harry” OR “Harry is a featherless biped"
• φ3 = A ∨ D represents "Harry is human” OR “Harry is happy"
• φ4 = ¬B represents NOT "Sally likes Harry"
• Thesis:
• ψ = D represents "Harry is happy"

Entailment Truth Table

• {φ1, φ2, φ3, φ4} ⊨ ψ
• Entailment occurs when all the possible worlds that satisfy {φ1, φ2, φ3, φ4} also satisfy ψ.

Diagramatic Display of Entailment

• Γ ⊨ φ
• There is entailment iff every world that satisfies Γ also satisfies φ.
• Possible worlds and truth tables are constructed.

Examples

• φ = (A ∨ B) ∧ C
• The rows in the table are not a single world are different group of worlds.
• Each ε wff(Lp) has a truth value.
• A possible world satisfies a wff φ iff ν(φ) = 1.
• This can written as <{0,1}, Σ, ν> ⊨ φ.
• Rows in the truth table that satisfy φ are often gray..
• Such possible world w is also said to be a model of φ.
• A possible world satisfies (i.e. is model of) a set of wff
• Γ = {φ1, φ2, ..., φn} iff w satisfies (is model of) each of its wffφ1, φ2, ..., φn.
• A tautology is a propositional wff that is always satisfied which is often said to be valid. Any wff of the type ψ ∨ ¬ψ is a tautology.
• A contradiction is a propositional wff that cannot be satisfied which is often said to be valid. Any wff of the type ψ ∧ ¬ψ is a contradiction.
• Not all wff are either tautologies or contradictions.
• If φ is a tautology then ¬φ is a contradiction and vice-versa.
• Each wff φ of Lp corresponds to a subset of W
• The subset of all possible worlds that satisfies it.
• φ corresponds to {w : w |= φ}.
• Set may by empty.
• If it’s empty, corresponds
• May coincide with W.
• If it coincides, it’s tautology.

Entailment Example

• {φ1, φ2, φ3, φ4} ̸⊨ ψ
• "All possible worlds that are models of φ1 ".

The set of models for {φ1} is:

• not contained in the set of models of ψ.

• not contained in the set of models of ψ. {φ1, φ2} ̸⊨ ψ

• The intersection of the two subsets.

• not contained in the set of models of ψ. {φ1, φ2, φ3} ̸⊨ ψ

• {φ1, φ2, φ3, φ4} ⊨ ψ

• Because the set of models for {φ1, φ2, φ3, φ4} is contained in the set of models of ψ.

• All the wff φ1, φ2, φ3, φ4 are needed for the relation of entailment to hold.

• Γ ⊨ φ

• There is entailment iff every world that satisfies Γ also satisfies φ.

• Symmetric entailment is logical equivalence.

• Given φ and ψ and their wff: φ ⊨ ψ and ψ ⊨ φ.

• The two wff are said to be logically equivalent.

• Which equals φ ≡ ψ in symbols. Two equivalent wff have exactly the same models.

• Equivalent wff is substitutable.

• Example:

• {φ1, φ2, φ3, φ4} ⊨ ψ

• φ1 = B ∨ D ∨ ¬(A ∧ C)

• φ2 = B ∨ C

• φ3 = A ∨ D

• φ4 = ¬B

• ψ = D

• φ1 = B ∨ D ∨ (A → ¬C)

• φ2 = B ∨ C

• φ3 = ¬A → D

• φ4 = ¬B

• ψ = D

Implications

• rewriting of equivalent expressions is a component of the wff problem.
• wff is in terms of entailment: φ → ψ / φ / ψ

It can be verified that

• φ → ψ, φ ⊨ ψ
• φ → ψ, ¬ψ ⊨ ¬φ
• Modern formal logic is defined by its fundamentals.
• These include the formal (symbolic) language, that are a set of symbols, not necessarily finite
• Syntactic rules for composite formulae (wff)
• As well as its formal semantics (i.e. a class of possible worlds)
• For each possible world in defined, every wff receives a value in the language
• Classical propositional logic, the set of values is the simplest which is {1, 0}
• Satisfaction, entailment follows which means a wff is satisfied in a possible world if in true, in that possible world.

Satisfaction

• In classical propositional logic, iff the wff has value 1 in that world (Caution: the definition of satisfaction will become definitely more complex with first order logic).
• Entailment is a relation between a set of wff and a wff
• This relation holds when all possible worlds satisfying the set also satisfy the wff
• Properties of entailment (classical logic): compactness, monotonicity, transitivity, ex absurdo ...

Compactness

• Consider a set of wff Γ (not necessarily finite) Γ ⊨ φ there exists a finite subset ∑ ⊆ Γ  such that ∑ ⊨ φ

(This follows from compositionality, see textbook for a proof)

Monotonicity

• For any Γ and Δ, if Γ ⊨ φ then Γ ∪ Δ ⊨ φ
• Any entailment relation between φ and Γ remains valid even if Γ grows larger
• If for all φ ∈ Σ we have Γ ⊨ φ, then if ∑ ⊨ ψ  then Γ ⊨ ψ
• If Γ entails any φ in ∑, then any ψ entailed by ∑ is also entailed by Γ

Ex Absurdo

• {φ, ¬φ} ⊨ ψ
• Which is an inconsistent (i.e. contradictory) set of wff that entails anything «Ex absurdo sequitur quodlibet».