Semantic

Model

• The set of the truth values (or Boolean values) is $\mathbb{B}=\{\mathsf{T},\mathsf{F}\}$

• $\mathcal{L}$ is the set of the propositions recursively defined by the set $\mathcal{P}$ of a proposition variables

• A truth assignment is a function $\nu :\mathcal{P}\to \mathbb{B}$, which assigns a truth value to each proposition in $\mathcal{S}$

• A truth valuation (or model) is a function $\mathcal{V}:\mathcal{L}\to \mathbb{B}$, which assigns a truth value to each proposition in $\mathcal{L}$

  • By structural induction the truth valuation $\mathcal{V}$ is uniquely defined by the truth assignment $\nu$:
    • For each $P\in \mathcal{P}$, $\mathcal{V}(P)=\nu (P)$
    • For each $\phi \in \mathcal{L}$
      • If $\phi =\neg \psi$ then $\mathcal{V}(\phi )=\{\begin{array}{ll}\mathsf{T}& \mathcal{V}(\psi )=\mathsf{F}\\ \mathsf{F}& \mathcal{V}(\psi )=\mathsf{T}\end{array}$
      • If $\phi =(\psi \vee \theta )$ then $\mathcal{V}(\phi )=\{\begin{array}{ll}\mathsf{T}& \mathcal{V}(\psi )=\mathsf{T}\text{ or }\mathcal{V}(\theta )=\mathsf{T}\\ \mathsf{F}& \text{otherwise}\end{array}$
      • If $\phi =(\psi \wedge \theta )$ then $\mathcal{V}(\phi )=\{\begin{array}{ll}\mathsf{T}& \mathcal{V}(\psi )=\mathsf{T}\text{ and }\mathcal{V}(\theta )=\mathsf{T}\\ \mathsf{F}& \text{otherwise}\end{array}$
      • If $\phi =(\psi \to \theta )$ then $\mathcal{V}(\phi )=\{\begin{array}{ll}\mathsf{T}& \mathcal{V}(\psi )=\mathsf{F}\text{ or }\mathcal{V}(\theta )=\mathsf{T}\\ \mathsf{F}& \text{otherwise}\end{array}$
      • If $\phi =(\psi \leftrightarrow \theta )$ then $\mathcal{V}(\phi )=\{\begin{array}{ll}\mathsf{T}& (\mathcal{V}(\psi )=\mathsf{T}\text{ and }\mathcal{V}(\theta )=\mathsf{T})\text{ or }(\mathcal{V}(\psi )=\mathsf{F}\text{ and }\mathcal{V}(\theta )=\mathsf{F})\\ \mathsf{F}& \text{otherwise}\end{array}$

• In a language with $n$ elementary propositions there are $2^n$ models

Truth Value

Given a model $M$,

• Model of a proposition
  • if $M(\phi )=\mathsf{T}$ we say that $\phi$ is true in the model $M$, and denote $M\models \phi$
  • if $M(\phi )=\mathsf{F}$ we say that $\phi$ is false in the model $M$, and denote $M/\models \phi$
• (Model of a propositions Set) Let $K$ a set of propositions,
  • $M$ is a model of $K$ (and denote $M\models K$) if every proposition in $K$ is true in $M$
    • If $K=\{{\phi }_1,\dots ,{\phi }_n\}$ then $M\models K$ if and only if $M\models {\phi }_1\wedge \cdots \wedge {\phi }_n$

Terminology: (Model of a proposition) $M(\phi )=\mathsf{T}$; $\phi$ is true in the model $M$; the truth value of $\phi$ is $\mathsf{T}$; $M$ satisfies $\phi$; $M$ is a model of $\phi$. (Model of a propositions Set) $M\models K$; $M$ is a model of $K$; $M$ satisfies $K$; $M$ is a model of $K$; For every $\phi \in K$, $M$ is a model of $\phi$. (satisfiable set) $K$ is satisfiable; there exists a model of $K$; $K$ has a model;

Substitution

• (3.1, special-case of 2.4) Let $L_1$ and $L_2$ be proportional languages (possibly $L_1=L_2$), and let $\phi$ be a proposition in both (and therefore the elementary propositions in $\phi$ are in both languages). And let $M_1$ be a model of $L_1$ and $M_2$ be a model of $L_2$ such that for each elementary proposition $Q$ in $\phi$ we have $M_1(Q)=M_2(Q)$ then $M_1(\phi )=M_2(\phi )$
• (3.2a) A substitution of other proposition in subproposition with the the same truth value does not change the truth value of the proposition
• If $\theta$ is a subproposition of $\phi$ and $\theta \equiv {\theta }^{\prime }$ then
  • $\phi \equiv \phi \left[{\theta }^{\prime }/\theta \right]$ (#todo)
  • (3.2a) For every model $M$, if $M(\theta )=M({\theta }^{\prime })$ then $M(\phi )=M(\phi \left[{\theta }^{\prime }/\theta \right])$
• (3.2b) If $\phi$ and $\psi$ and ${\psi }^{\prime }$ are propositions, and $Q$ elementary proposition, then, for every model $M$, if $M(\psi )=M({\psi }^{\prime })$ then $M(\phi \left[\psi /Q\right])=M(\phi \left[{\psi }^{\prime }/Q\right])$

Satisfiability

• A proposition $\phi$ is unsatisfiable if for every model $M$ we have $M/\models \phi$.
• A proposition $\phi$ is satisfiable if there exists a model $M$ and an assignment $S$ such that $M{\models }_S\phi$.
• A set of propositions $K$ is said to be satisfiable if there exists a model of $K$

Logical Validity

• A proposition $\phi$ is a tautology (or logically valid) (and denoted by $\models \phi$) if for every model $M$ we have $M\models \phi$. (טאוטולוגיה, פסוק אמיתי לוגית)
  • Examples: Logical Axioms (q4.6)
• A proposition is a contradiction if and only if it is false in every model in the language of the proposition. (סתירה לוגית, פסוק שקרי לוגית)
• $\phi$ is a tautology if and only if $\neg \phi$ is a contradiction
• $\phi$ is a contradiction if and only if $\neg \phi$ is a tautology

Logical Equivalence

• Propositions $\phi$ and $\psi$ are logically equivalent (and denoted $\phi \equiv \psi$ (or $\phi ⟺\psi$)) if and only if they are true in the same models exactly
  • If two propositions $\phi$ and $\psi$ have the same elementary propositions, then:
    • $\phi \equiv \psi$ if and only if $(\phi \leftrightarrow \psi )$ is a tautology
  • Propositions are logically equivalent if and only if they always have the same truth values
  • Examples: Rules of Replacement
• $\phi \equiv \psi$ if and only if $\phi \models \psi$ and $\psi \models \phi$todo
• $\phi \equiv \psi$ if and only if for every model $M$ for $\phi$ and $\psi$, we have $M(\phi )=M(\psi )$todo

is the term tautologically equivalent (Cunningham) equivalent to logically equivalenttodo

Logical Implication

• A proposition $\phi$ logically implies a proposition $\psi$ (or $\psi$ logically implied by $\phi$), and denoted by $\phi ⟹\psi$ (or more common $\phi \models \psi$), if and only if, in every model $M$, if $M\models \phi$ then $M\models \psi$.
  • $\phi$ logically implies a proposition $\psi$ if and only if $\phi \to \psi$ is a tautology. In other words, $\phi ⟹\psi$ if and only if $\models (\phi \to \psi )$
• A set propositions $K$ logically implies a proposition $\psi$ (and $\psi$ logically implied by $K$), and denoted by $K⟹\psi$ (or more common $K\models \psi$), if and only if, in every model in which all proposition in $K$ are true, also $\psi$ is true
  • If $K=\{{\phi }_1,\dots ,{\phi }_n\}$ is a finite set of propositions, then, $K⟹\psi$ if and only if ${\phi }_1\wedge \cdots \wedge {\phi }_n⟹\psi$.
    • Hence, $\{{\phi }_1,\dots ,{\phi }_n\}⟹\psi$ if and only if $\models (({\phi }_1\wedge \cdots \wedge {\phi }_n)\to \psi )$
  • (4.8, 3.6) Compactness theorem - Let $K$ be a propositions set,
    • if every finite subset of $K$ has at least one model, then there exist a model of $K$
    • if $K⟹\psi$ then there exists a finite subset $\{{\phi }_1,\dots ,{\phi }_n\}\subseteq K$ such that $\{{\phi }_1,\dots ,{\phi }_n\}⟹\psi$

is the term tautologically implies (Cunningham) equivalent to logically impliestodo

Note: If $\varnothing \models \phi$ then $\phi$ is a tautology which is denoted by $\models \phi$

$\phi ⟹\psi$ and $K⟹\phi$ in this course are more commonly denoted by notations $\phi \models \psi$ and $K\models \phi$

Definabllty

(from Sarai Sheinvald)

• Let be $\Sigma$ be a set of propositions, and $M(\Sigma )$ be the set of all models of $\Sigma$. Where $M(\Sigma )=\{M\mid M\models \Sigma \}$
• Given a set of models $X$.
  • If there exists a set of propositions $\Sigma$ such that $X=M(\Sigma )$ then we say that the set $X$ is definable (גדירה) by $\Sigma$