Semantics final definitions

Question 1

Formulae of CPL (syncategorematic version)

Answer 1

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.

Question 2

Formulae of CPL (categorematic version)

Answer 2

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.

Question 3

Immediate subformulae of CPL

Answer 3

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 (β ↔ α) = γ.

Question 4

Proper subformulae of CPL

Answer 4

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 β

Question 5

Subformulae of CPL

Answer 5

Let α and β be members of FM. α is a subformula of β iff either α is β or α is a proper subformula of β.

Question 6

Scope of a propositional connective of CPL

Answer 6

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.

Question 7

Formula being within the scope of CPL

Answer 7

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 β.

Question 8

Propositional connective’s occurrence being within the scope of CPL

Answer 8

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.

Question 9

Formula’s main propositional connective of CPL

Answer 9

A formula’s main propositional connective is that propositional connective whose occurrence in the formula has the formula for its scope

Question 10

Classical valuation for CPL

Answer 10

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(β).

Question 11

Extension to a classical valuation for CPL (syncategorematic version)

Answer 11

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(β).

Question 12

Extension to a classical valuation for CPL (categorematic version)

Answer 12

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(β)).

Question 13

Satisfaction for CPL

Answer 13

(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.

Question 14

Facts about satisfaction (CPL)

Answer 14

(1) For each bivalent assignment a, and for each formula α, a satisfies α iff a satisfies {α};
(2) Each bivalent assignment satisfies the empty set.

Question 15

Tautology of CPL

Answer 15

(properties of formulae) A formula is a tautology iff each bivalent assignment satisfies it.

Question 16

Contradiction of CPL

Answer 16

(properties of formulae) A formula is a contradiction iff each bivalent assignment does not satisfy it.

Question 17

Contingency of CPL

Answer 17

(properties of formulae) A formula is a contingency iff some bivalent assignment satisfies it and some other does not.

Question 18

Satisfiability for CPL

Answer 18

(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.

Question 19

Facts about satisfiability (CPL)

Answer 19

(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.

Question 20

Unsatisfiability for CPL

Answer 20

(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.

Question 21

Facts about unsatisfiability (CPL)

Answer 21

(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.

Question 22

Semantic equivalence for CPL

Answer 22

(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.

Question 23

Facts about semantic equivalence (CPL)

Answer 23

(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.

Question 24

Entailment for CPL

Answer 24

(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 α.

Question 25

Facts about entailment (CPL)

Answer 25

Let α and β be formulae. Let Γ and Δ be sets of formulae. (1) If α ∈ Γ, then Γ ⊨ α. (2) If Γ ⊆ Δ and Γ ⊨ α, then Δ ⊨ α. (3) Γ ∪{α} ⊨ β iff Γ ⊨ α → β. (4) Γ ⊨ α ∧ β iff Γ ⊨ α and Γ ⊨ β.

Question 26

Facts about entailment and tautologies (CPL)

Answer 26

Let α be a formula. (1) α is a tautology iff ∅ ⊨ α. (2) α is a tautology iff, for each Γ, a subset of FM, Γ ⊨ α.

Question 27

Facts about entailment and unsatisfiability (CPL)

Answer 27

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, Γ ⊨ α.

Question 28

Signature (CPDL)

Answer 28

Let ⟨IS, RS, ad⟩ be a signature iff IS and RS are disjoint sets and ad is a function from RS into ℤ+

Question 29

Atomic formulae of CPDL

Answer 29

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.

Question 30

Formulae of CPDL (categorematic version)

Answer 30

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.

Question 31

Structure for a signature

Answer 31

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).

Question 32

Classical valuation for CPDL

Answer 32

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)

Question 33

Satisfaction for CPDL

Answer 33

(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.

Question 34

Facts about satisfaction (CPDL)

Answer 34

(1) For each structure M, and for each formula α, M satisfies α iff M satisfies {α}. (2) Each structure satisfies the empty set.

Question 35

Tautology of CPDL

Answer 35

A formula is a tautology iff each structure satisfies it.

Question 36

Contradiction of CPDL

Answer 36

A formula is a contradiction iff each structure does not satisfy it.

Question 37

Contingency of CPDL

Answer 37

A formula is a contingency iff some structure satisfies it and some other does not.

Question 38

Satisfiability for CPDL

Answer 38

(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.

Question 39

Facts about satisfiability (CPDL)

Answer 39

(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.

Question 40

Unsatisfiability for CPDL

Answer 40

(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.

Question 41

Facts about unsatisfiability (CPDL)

Answer 41

(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.

Question 42

Semantic equivalence for CPDL

Answer 42

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.

Question 43

Facts about semantic equivalence (CPDL)

Answer 43

(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.

Question 44

Entailment for CPDL

Answer 44

A set of formulae entails a formula, or Γ ⊨ α, iff each structure that satisfies the set Γ satisfies the formula α.

Question 45

Facts about entailment (CPDL)

Answer 45

Let α and β be formulae. Let Γ and Δ be sets of formulae (1) If α ∈ Γ, then Γ ⊨ α. (2) If Γ ⊆ Δ and Γ ⊨ α, then Δ ⊨ α. (3) Γ ∪{α} ⊨ β iff Γ ⊨ α → β. (4) Γ ⊨ α ∧ β iff Γ ⊨ α and Γ ⊨ β.

Question 46

Facts about entailment and tautologies (CPDL)

Answer 46

Let α be a formulae. Let Γ be a set of formulae. (1) α is a tautology iff ∅ ⊨ α. (2) α is a tautology iff, for each Γ, Γ ⊨ α.

Question 47

Facts about entailment and unsatisfiability (CPDL)

Answer 47

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, Γ ⊨ α.

Question 48

Atomic formulae of CQL

Answer 48

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.

Question 49

Formulae of CQL (categorematic version)

Answer 49

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.

Question 50

Scope of a logical connective for CQL

Answer 50

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.

Question 51

Binding for CQL

Answer 51

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.

Question 52

Bound variable for CQL

Answer 52

(An occurrence of) a variable v is bound in a formula α iff (an occurrence of) a quantifier prefix in the formula α binds it.

Question 53

Free variable for CQL

Answer 53

(An occurrence of) a variable v is free in a formula α iff no (occurrence of a) quantifer prefix in the formula α binds it.

Question 54

Closed formula for CQL

Answer 54

A formula is closed iff it has no (occurrences of a) free variable.

Question 55

Open formula for CQL

Answer 55

A formula is open iff it has at least one (occurrence of a) free variable.

Question 56

Free variables in a formula of CQL

Answer 56

(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}.

Question 57

Substitution of an individual symbol for a free variable in CQL

Answer 57

Let c be in IS and let v be in VR. Then,

Question 58

Substitution instance for CQL

Answer 58

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.

Question 59

Medieval valuation for CQL

Answer 59

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.

Question 60

Marcus valuation for CQL

Answer 60

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.

Question 61

Fregean valuation for CQL

Answer 61

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 α.

Question 62

Tarski extension for CQL (syncategorematic version)

Answer 62

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

Question 63

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,