Semantics final definitions Flashcards
lol Chap 6 and 9 and then 11
Formulae of CPL (syncategorematic version)
Let PV be a set of propositional variables. Then, FM, the formulae of CPL based on PV, is the set defined as follows:
(1) PV⊆ FM;
(2.1) if α ∈ FM, then ¬α ∈ FM;
(2.2.1) if α, β ∈ FM, then (α ∧ β) ∈ FM;
(2.2.2) if α, β ∈ FM, then (α ∨ β) ∈ FM;
(2.2.3) if α, β ∈ FM, then (α → β) ∈ FM;
(2.2.4) if α, β ∈ FM, then (α ↔ β) ∈ FM;
(3) nothing else is.
Formulae of CPL (categorematic version)
Let PV be a set of propositional variables. Then, FM, the formulae of CPL based on PV, is the set defined as follows:
(1) PV⊆ FM;
(2.1) if α ∈ FM and *∈ UC, then * α ∈ FM;
(2.2) if α, β ∈ FM and ° ∈ BC, then (α°β) ∈ FM;
(3) nothing else is.
Immediate subformulae of CPL
Let α and γ be members of FM. α is an immediate subformula of γ iff either ¬α = γ or there is a formula β such that one of the following obtains: (α∧β) = γ, (β ∧ α) = γ, (α ∨ β) = γ, (β ∨ α) = γ, (α → β) = γ, (β → α) = γ, (α ↔ β) = γ, or (β ↔ α) = γ.
Proper subformulae of CPL
Let α and γ be members of FM. α is a proper subformula of γ iff one of the following holds:
(1) α is an immediate subformula of γ;
(2) there is a formula β such that β is an immediate subformula of γ and α is a proper subformula of β
Subformulae of CPL
Let α and β be members of FM. α is a subformula of β iff either α is β or α is a proper subformula of β.
Scope of a propositional connective of CPL
The scope of an occurrence of a propositional connective in a formula α is the subformula of α that contains the propositional connective’s occurrence but whose immediate subformulae
do not.
Formula being within the scope of CPL
A formula α occurs within the scope of a propositional connective’s occurrence in a formula β iff α is a subformula of the scope of the propositional connective’s occurrence in formula β.
Propositional connective’s occurrence being within the scope of CPL
One propositional connective’s occurrence in a formula occurs within the scope of another’s iff the first occurs within a formula that is within the scope of the second.
Formula’s main propositional connective of CPL
A formula’s main propositional connective is that propositional connective whose occurrence in the formula has the formula for its scope
Classical valuation for CPL
A valuation v is classical iff v is bivalent and complies with these conditions: for each α, β ∈ FM,
(1) v(¬α) = T iff v(α) = F;
(2.1) v(α ∧ β) = T iff v(α) = v(β) = T;
(2.2) v(α ∨ β) = T iff v(α) = T or v(β) = T;
(2.3) v(α → β) = T iff v(α) = F or v(β) = T;
(2.4) v(α ↔ β) = T iff v(α) = v(β).
Extension to a classical valuation for CPL (syncategorematic version)
Let a be a bivalent assignment for PV. Then va classically extends a, if and only if va is a
function of FM conforming to the following conditions:
(1) for each α ∈ AF, va(α) = a(α);
(2) for each α, β ∈ FM,
(2.1) va(¬α) = T iff va(α) = F;
(2.2.1) va(α ∧ β) = T iff va(α) = va(β) = T;
(2.2.2) va(α ∨ β) = T iff va(α) = T or va(β) = T;
(2.2.3) va(α → β) = T iff va(α) = F or va(β) = T;
(2.2.4) va(α ↔ β) = T iff va(α) = va(β).
Extension to a classical valuation for CPL (categorematic version)
Let a be a bivalent assignment for PV. Then va classically extends a, if and only if va is a
function of FM conforming to the following conditions:
(1) for each α ∈ AF, va(α) = a(α);
(2) for each α, β ∈ FM,
(2.1) va(¬α) = o¬(va(α));
(2.2.1) va(α ∧ β) = o∧(va(α), va(β));
(2.2.2) va(α ∨ β) = o∨(va(α), va(β));
(2.2.3) va(α → β) = o → (va(α), va(β));
(2.2.4) va(α ↔ β) = o↔(va(α), va(β)).
Satisfaction for CPL
(Single formula to a set of single formula) (1) For bivalent assignment a, and for each formula α, a satisfies α iff va(α) = T;
(2) For bivalent assignment a, and for each set of formulae Γ, a satisfies Γ iff, for each α ∈ Γ, va(α) = T.
Facts about satisfaction (CPL)
(1) For each bivalent assignment a, and for each formula α, a satisfies α iff a satisfies {α};
(2) Each bivalent assignment satisfies the empty set.
Tautology of CPL
(properties of formulae) A formula is a tautology iff each bivalent assignment satisfies it.
Contradiction of CPL
(properties of formulae) A formula is a contradiction iff each bivalent assignment does not satisfy it.
Contingency of CPL
(properties of formulae) A formula is a contingency iff some bivalent assignment satisfies it and some other does not.
Satisfiability for CPL
(PROPERTIES OF FORMULAE AND OF SETS OF FORMULAE) (1) A formula is satisfiable iff some bivalent assignment satisfies it;
(2) a set of formulae is satisfiable iff some bivalent assignment satisfies it.
Facts about satisfiability (CPL)
(1) For each formula α, α is satisfiable iff {α} is satisfiable.
(2) Each subset of a satisfiable set of formulae is satisfiable.
(3) The empty set is satisfiable.
Unsatisfiability for CPL
(1) A formula is unsatisfiable iff no bivalent assignment satisfies it;
(2) a set of formulae is unsatisfiable iff no bivalent assignment satisfies all the set’s
formulae.
Facts about unsatisfiability (CPL)
(1) For each formula α, α is unsatisfiable iff {α} is unsatisfiable.
(2) Each superset of an unsatisfiable set of formulae is unsatisfiable.
(3) FM, or the set of all formulae, is unsatisfiable.
Semantic equivalence for CPL
(RELATIONS BETWEEN FORMULAE AND SETS OF FORMULAE) A set of formulae or a formula, on the one hand, and a set of formulae or a formula, on the other, are semantically equivalent iff (1) each bivalent assignment satisfying the former satisfies the latter and (2) each bivalent assignment satisfying the latter satisfies the former.
Facts about semantic equivalence (CPL)
(1) All tautologies and sets of tautologies are semantically equivalent.
(2) All tautologies and all sets of tautologies are semantically equivalent to the empty set.
(3) All contradictions and all sets of contradictions are semantically equivalent.
(4) All contradictions and all sets of contradictions are semantically equivalent to FM, or the set of all formulae.
Entailment for CPL
(RELATIONS BETWEEN FORMULAE AND SETS OF FORMULAE) The set of formulae Γ entails a formula α, or Γ ⊨ α, iff each bivalent assignment that satisfies the set Γ, satisfies the formula α.
Facts about entailment (CPL)
Let α and β be formulae. Let Γ and Δ be sets of formulae.
(1) If α ∈ Γ, then Γ ⊨ α.
(2) If Γ ⊆ Δ and Γ ⊨ α, then Δ ⊨ α.
(3) Γ ∪{α} ⊨ β iff Γ ⊨ α → β.
(4) Γ ⊨ α ∧ β iff Γ ⊨ α and Γ ⊨ β.
Facts about entailment and tautologies (CPL)
Let α be a formula.
(1) α is a tautology iff ∅ ⊨ α.
(2) α is a tautology iff, for each Γ, a subset of FM, Γ ⊨ α.
Facts about entailment and unsatisfiability (CPL)
Let α be a formula. Let Γ be a set of formulae.
(1) Γ ⊨ α iff Γ ∪{¬α} is unsatisfiable.
(2) Γ is unsatisfiable iff, for any α, Γ ⊨ α.
(3) Γ is unsatisfiable iff, for at least one α, a contradiction, Γ ⊨ α.
Signature (CPDL)
Let ⟨IS, RS, ad⟩ be a signature iff IS and RS are disjoint sets and ad is a function from RS into ℤ+
Atomic formulae of CPDL
Let ⟨IS, RS, ad⟩ be a signature. α is an atomic formula (of CPDL), that is, α ∈ AF, iff Π ∈ RS, ad(Π) = n and there are n occurrences of individual symbols from IS — c1, …, cn — such that α = Πc1…cn.
Formulae of CPDL (categorematic version)
FM, the formulae of CPDL, is the set defined as follows:
(1) AF ⊆ FM;
(2.1) if α ∈ FM and *∈ UC, then * α ∈ FM;
(2.2) if α, β ∈ FM and ° ∈ BC, then (α°β) ∈ FM;
(3) nothing else is.
Structure for a signature
M, or ⟨U, i⟩, is a structure for a signature, ⟨IS, RS, ad⟩ iff
(1) U is a nonempty set;
(2) i is a function where
(2.1) its domain is IS ∪ RS,
(2.2) for each c ∈ IS, i(c) ∈ U, and
(2.3) for each Π ∈ RS such that ad(Π) = n, i(Π) ∈ Pow(Un).
Classical valuation for CPDL
Let M, or ⟨U, i⟩, be a structure for a signature, ⟨IS, RS, ad⟩. vM is a classical valuation (for
CPDL) if and only if it is a function whose domain is IS∪RS∪FM and which meets the
following conditions:
(0) NONLOGICAL SYMBOLS
If c is a member of IS, then vM(c) = i(c).
If Π be a member of RS, then vM(Π) = i(Π).
(1) ATOMIC FORMULAE
Let Π be a member of RS, let ad(Π) = 1 and let c be a member of IS. Then,
(1.1) vM(Πc) = T iff vM(c) ∈ vM(Π).
Let Π be a member of RS, let ad(Π) = n (where n > 1) and let c1, …, cn be occurrences of
members of IS. Then,
(1.2) vM(Πc1…cn) = T iff ⟨vM(c1), …, vM(cn)⟩∈ vM(Π).
(2) COMPOSITE FORMULAE
Then, for each α and for each β in FM,
(2.1) vM(¬α) = o¬(vM(α));
(2.2) vM (.. for all vM alpha and beta stuff)
Satisfaction for CPDL
(1) For each structure M, and for each formula α,
M satisfies α iff vM(α) = T.
(2) For each structure M, and for each set of formulae, Γ,
M satisfies Γ iff, for each α ∈ Γ, vM(α) = T.
Facts about satisfaction (CPDL)
(1) For each structure M, and for each formula α,
M satisfies α iff M satisfies {α}.
(2) Each structure satisfies the empty set.
Tautology of CPDL
A formula is a tautology iff each structure satisfies it.
Contradiction of CPDL
A formula is a contradiction iff each structure does not satisfy it.
Contingency of CPDL
A formula is a contingency iff some structure satisfies it and some other does not.
Satisfiability for CPDL
(1) A formula is satisfiable iff some structure satisfies it;
(2) a set of formulae is satisfiable iff some structure satisfies each formula in the set.
Facts about satisfiability (CPDL)
(1) For each formula α, α is satisfiable iff {α} is satisfiable.
(2) Each subset of a satisfiable set of formulae is satisfiable.
(3) The empty set is satisfiable.
Unsatisfiability for CPDL
(1) A formula is unsatisfiable iff no structure satisfies it;
(2) a set of formulae is unsatisfiable iff no structure satisfies all of the set’s formulae.
Facts about unsatisfiability (CPDL)
(1) For each formula α, α is unsatisfiable iff {α} is unsatisfiable.
(2) Each superset of an unsatisfiable set of formulae is unsatisfiable.
(3) FM, or the set of all formulae, is unsatisfiable.
Semantic equivalence for CPDL
A set of formulae or a formula, on the one hand, and a set of formula or a formula, on the other, are semantically equivalent iff (1) each structure satisfying the former satisfies the latter and (2) each structure satisfying the latter satisfies the former.
Facts about semantic equivalence (CPDL)
(1) All tautologies and sets of tautologies are semantically equivalent.
(2) All tautologies and all sets of tautologies are semantically equivalent to the empty set.
(3) All contradictions and all sets of contradictions are semantically equivalent.
(4) All contradictions and all sets of contradictions is semantically equivalent to FM, or the set of all formulae.
Entailment for CPDL
A set of formulae entails a formula, or Γ ⊨ α, iff each structure that satisfies the set Γ satisfies the formula α.
Facts about entailment (CPDL)
Let α and β be formulae. Let Γ and Δ be sets of formulae
(1) If α ∈ Γ, then Γ ⊨ α.
(2) If Γ ⊆ Δ and Γ ⊨ α, then Δ ⊨ α.
(3) Γ ∪{α} ⊨ β iff Γ ⊨ α → β.
(4) Γ ⊨ α ∧ β iff Γ ⊨ α and Γ ⊨ β.
Facts about entailment and tautologies (CPDL)
Let α be a formulae. Let Γ be a set of formulae.
(1) α is a tautology iff ∅ ⊨ α.
(2) α is a tautology iff, for each Γ, Γ ⊨ α.
Facts about entailment and unsatisfiability (CPDL)
Let α be a formulae. Let Γ be a set of formulae.
(1) Γ ⊨ α iff Γ ∪{¬α} is unsatisfiable.
(2) Γ is unsatisfiable iff, for any α, Γ ⊨ α.
(3) Γ is unsatisfiable iff, for at least one α, there is a contradiction, Γ ⊨ α.
Atomic formulae of CQL
Let ⟨IS, RS, ad⟩ be a signature. Let VR be a nonempty set of variables. Let TM be IS∪VR. α is an atomic formula of CQL (α ∈ AF) iff Π ∈ RS, ad(Π) = n and there are n occurrences of terms from TM—t1, …, tn—such that α = Πt1…tn.
Formulae of CQL (categorematic version)
FM, the set of formulae of CQL, is defined as follows:
(1) AF ⊆ FM;
(2.1) if α ∈ FM and *∈ UC, then * α ∈ FM;
(2.2) if α, β ∈ FM and ° ∈ BC, then (α°β) ∈ FM;
(3) if Q ∈ QC, v ∈ VR and α ∈ FM, then Qvα ∈ FM;
(4) nothing else is.
Scope of a logical connective for CQL
The scope of an occurrence of a logical connective in a formula α is the subformula of α that
contains the logical connective’s occurrence but whose immediate subformulae do not.
Binding for CQL
Let α be in FM. Let Qv be a quantifier prefix that occurs in α and let w be a variable in α. (An
occurrence of) the quantifier prefix Qv binds (an occurrence of) the variable w iff
(1) v = w (i.e., v and w are the same variable);
(2) (the occurrence of) w is within the scope of (the occurrence of) the quantifier prefix Qv;
and
(3) no occurrence of either ∃v or ∀v, distinct from (the occurrence of) the quantifier prefix
Qv, has the relevant occcurrence of w within its scope and is itself within the scope of
the relevant occurrence of Qv.
Bound variable for CQL
(An occurrence of) a variable v is bound in a formula α iff (an occurrence of) a quantifier prefix in the formula α binds it.
Free variable for CQL
(An occurrence of) a variable v is free in a formula α iff no (occurrence of a) quantifer prefix in the formula α binds it.
Closed formula for CQL
A formula is closed iff it has no (occurrences of a) free variable.
Open formula for CQL
A formula is open iff it has at least one (occurrence of a) free variable.
Free variables in a formula of CQL
(1) ATOMIC FORMULAE
Let α be an atomic formula of the form Πt1…tn.
Fvr(α) = {v: v ∈ VR and, for some , ti is an instance of v}.
(2) COMPOSITE FORMULAE
(2.1) Let α be a composite formula of the form * β, where *∈ UC;
that is, let α be a formula of the ¬β. Then, Fvr(α) = Fvr(β).
(2.2) Let α be a composite formula of the form (β°γ), where ° ∈ BC is a binary connective.
Then, Fvr(α) = Fvr(β) ∪ Fvr(γ).
(2.3) Let α be a composite formula of the form Qvβ, where Q ∈ QC and v ∈ VR. Then,
Fvr(α) = Fvr(β) −{v}.
Substitution of an individual symbol for a free variable in CQL
Let c be in IS and let v be in VR. Then,
Substitution instance for CQL
A formula α is a substitution instance of a formula β iff, for some quantifier prefix Qv, some formula γ, and some individual symbol c, β = Qvγ and [c/v]γ = α.
(0.1) [c/v]t = t, if t ∈ IS;
(0.2) [c/v]t = t, if t ∈ VR and t ≠ v;
(0.3) [c/v]t = c, if t ∈ VR and t = v;
(1.1) [c/v]Πt₁…tₙ = Π[c/v]t₁…[c/v]tₙ;
(2.1) [c/v]*α = *[c/v]α;
(2.2) c/v = ([c/v]α ○ [c/v]β);
(2.3.1) [c/v]Qwα = Qw[c/v]α, if v ≠ w;
(2.3.2) [c/v]Qwα = Qwα, if v = w.
Medieval valuation for CQL
Let M, or ⟨U, i⟩, be a structure for a signature, ⟨IS, RS, ad⟩, where U is a finite set and i,
restricted to IS, is a surjection onto U. Then, vM is a function from the set of closed formulae
(FMc) to the set of truth values {T, F}, satisfying the following clauses.
(1) ATOMIC FORMULAE
Let Π be a member of RS, let ad(Π) be 1 and let c be a member of IS. Then,
(1.1) vM(Πc) = T iff i(c) ∈ i(Π).
Let Π be a member of RS, let ad(Π) be n (where n > 1) and let c1, …, cn be occurrences of
members from IS. Then,
(1.2) vM(Πc1…cn) = T iff ⟨i(c1), …, i(cn)⟩∈ i(Π).
(2) COMPOSITE FORMULAE
Then, for each α and for each β in FM,
(2.1) vM(¬α) = T iff vM(α) = F;
(2.2.1) vM(α ∧ β) = T iff vM(α) = T and vM(β) = T;
(2.2.2) vM(α ∨ β) = T iff either vM(α) = T or vM(β) = T;
(2.2.3) vM(α → β) = T iff either vM(α) = F or vM(β) = T;
(2.2.4) vM(α ↔ β) = T iff vM(α) = vM(β).
(3) QUANTIFIED COMPOSITE FORMULAE
Let v be a member of VR, let α be a member of FM and let c1, …, cn be occurrences of
members from IS such that each member of U is assigned to some ci ( ).
(3.1) vM(∀v α) = T iff vM([c1/v]α ∧… ∧ [cn/v]α) = T;
(3.2) vM(∃v α) = T iff vM([c1/v]α ∨… ∨ [cn/v]α) = T.
Marcus valuation for CQL
Let M, or ⟨U, i⟩, be a structure for a signature ⟨IS, RS, ad⟩, where i, restricted to IS, is a
surjection onto U. Then, vM is a function from the set of closed formula (FMc) to the set of
truth values {T, F}, satisfying the following clauses:
(3) QUANTIFIED COMPOSITE FORMULAE
Let v be a member of VR and let α be a member of FM.
(3.1) vM(∀v α) = T iff for each c ∈ IS, vM([c/v]α) = T;
(3.2) vM(∃v α) = T iff for some c ∈ IS, vM([c/v]α) = T.
Fregean valuation for CQL
Let M, or ⟨U, i⟩, be a structure for a signature ⟨IS, RS, ad⟩. Then, vM is a function from the set
of closed formula (FMc) to the set of truth values {T, F}, satisfying the following clauses.
(3) QUANTIFIED COMPOSITE FORMULAE
Let v be a member of VR and let α be a member of FM.
(3.1) v_M(∀v α) = T iff for each e in U, v_M_C→e([c/v]α) = T,
where c is an individual symbol not occurring in α;
(3.2) v_M(∃v α) = T iff for some e in U, v_M_C→e([c/v]α) = T,
where c is an individual symbol not occurring in α.
Tarski extension for CQL (syncategorematic version)
Let M, or ⟨U, i⟩, be a structure for a signature ⟨IS, RS, ad⟩. Let VR be a set of variables. Let
TM be IS ∪ VR. And let g be a variable assignment from VR into U. Then, , a Tarski
extension for CQL, is a function satisfying the following conditions.
(0) SYMBOLS
Let v be a member of VR, let c be a member of IS and let Π be a member of RS.
(1) ATOMIC FORMULAE
Let Π be a member of RS, let ad(Π) be 1 and let t be a member of TM. Then,
Let Π be a member of RS, let ad(Π) be n (where n > 1) and let t1, …, tn be occurrences of
members of TM.
2) COMPOSITE FORMULAE
Let α and β be members of FM.
(3) QUANTIFIED COMPOSITE FORMULAE
Let v be a member of VR and let α be a member of FM.
whatver is on + there are facts about it
Tarski valuation for CQL
Let M, or ⟨U, i⟩, be a structure for a signature ⟨IS, RS, ad⟩. Let VR be a set of variables.
Then, a Tarski valuation is the function [ ]M from FMc into {T, F} such that for each α ∈
FMc,
