Given the following task: (Given a single specification)
Use truth tables to check if the specification is consistent, and if it is - provide a model of the specification. If not, provide a counter model.
I know that a specification is consistent if there is at least one line in the truth table which has all true values for all the propositions. And I know that a model of a specification is essentially the set of interpretations for the prop.symbols, which give out those 'all-true' rows.
However, what is a counter model? How can I construct a counter model, if I have an inconsistent formula? What purpose do they serve?
$\endgroup$2 Answers
$\begingroup$In propositional logic, the analogous of models are the assignments of truth values.
This assignments are as follows: if $P$ is the set of propositional variables and $\cal F$ is the set of propositional formulas, given an assignment of truth values $\delta\in\{0,1\}^P$ (that is a function from $P$ to $\{0,1\}$), there exists a unique map $\bar\delta:{\cal F}\to \{0,1\}$, which agrees with $\delta$ on $P$ and behaves as we would expect on the formulas (that is, $\bar\delta(A\wedge B)$ is 1 iff $\delta(A)$ and $\delta(B)$ are both 1 and all that stuff).
Now, in propositional calculus we say that a formula $F$ (or a theory (set of formulas)) is consistent (i.e. has a model) if there exist a truth values assignment $\delta$ in which $\bar\delta(F)=1$.
Counter-models are about inferences. Inferences in the following sense: let $F$ and $G$ be two propositional formulas. If for all truth values assignments $\delta$ such that $\bar\delta(F)=1$, we have $\bar\delta(G)=1$ as well, we say that we can infer $G$ from $F$. In other words, we can infer $G$ from $F$ if for all assignments of truth values $\delta$, $\bar\delta(F)=1$ implies $\bar\delta(G)=1$.
But if you can find an assignment of truth values $\delta$ such that $\bar\delta(F)=1$ but $\bar\delta(G)=0$ then we can't infer $G$ from $F$. One such a $\delta$ is called counter-model.
$\endgroup$ $\begingroup$If the specification (say $\Gamma$) is consistent, then, as you rightly said, there will be a row of the truth table that assigns 'true' to all $\phi \in \Gamma$. If, however, $\Gamma$ is not consistent, then some formulas $\phi, \psi \in \Gamma$ are such that $\phi \not\equiv \psi$. This means that no row in the truth-table can satisfy both $\phi$ and $\psi$. But since $\phi$ and $\psi$ are members of $\Gamma$, any row of the truth-table will then be a counter-model of $\Gamma$.
For example, suppose $\Gamma = \{P, \lnot P\}$. Since $\Gamma$ contains an inconsistent pair, it's not satisfiable. Therefore, both assignments of truth-values to P will be counter-models for $\Gamma$, so you could just give the following assignment as an answer: 'true' $\mapsto$ 'P'.
$\endgroup$
