1

Suppose we add $0$-place connectives $\top, \bot$ to our language. For each well-formed formula wff $, \phi$ and sentence symbol, $A,$ let $\phi^{A}_{\top}$ be the wff obtained from $\phi$ by replacing $A$ with $\top.$ Similarly for $\phi^{A}_{\bot}.$ Let $\phi^{A}_{*}= (\phi^{A}_{\top} \lor \phi^{A}_{\bot}).$

(i) Suppose $\phi \models\psi$ and $A$ does not appear in $\psi,$ could anyone advise me on how to show $\phi^{A}_{*} \models \psi$ and (ii )how to show $\phi$ is satisfiable iff $\phi^{A}_{*}$ is satisfiable?

Hints will suffice. Thank you.

Alexy Vincenzo
  • 5,400
  • 1
    The "trick" in the substitution of $\top$ and $\bot$ is to "simulate" into the formula the rows of the truth-table. The two formula in the disjunction (the top-ized and the bot-ized) are like two rows of the tt where the sentence symbol $A$ appear. – Mauro ALLEGRANZA Feb 23 '14 at 18:54
  • 1
    Thank you. What do you mean by 'two rows of the tt where $A$ appears?' – Alexy Vincenzo Feb 23 '14 at 19:03
  • 1
    All the rows of the truth-table where the sentence letter $A$ has value true are "replaced by the top-ized formula, and teh same for the rows where $A$ has value false... – Mauro ALLEGRANZA Feb 23 '14 at 19:14

2 Answers2

2

You must start with the definition of tautological implication (we may use this because we are considering only sentence letters) :

$\phi \models\psi$ iff, for every valuation $v$ such that $|\phi|_v = t$, also $|\psi|_v = t$.

Now assume that $\phi$ is built from $n$ sentence letters : $A, A_1, ... A_{n-1}$.

Consider now the truth-table (with $2^n$ rows) for $\phi$ : in these table, half of the rows have $A$ evaluated at t and half evaluated at f.

When we build the formula $\phi^{A}_{\top}$, this formula is equivalent to all the rows of the t-t for $\phi$ where $A$ is evaluated to t; the same with $\phi^{A}_{\bot}$, that is equivalent to the rows with $A$ evaluated to f.

So the formula $\phi^{A}_{*} = (\phi^{A}_{\top} \lor \phi^{A}_{\bot})$ may replace all the truth-table for $\phi$.

Now, go back to the tautological impliction :

$\phi \models\psi$ iff for every valuation $v$ such that $|\phi|_v = t$, also $|\psi|_v = t$,

i.e. for every row in the t-t for $\phi$ that evaluates to t, also $\psi$ is evaluated to f.

But the rows of the t-t for $\phi$ which evaluate to t may have $A=t$ or $A=f$; both cases are covered by the disjunction $\phi^{A}_{\top} \lor \phi^{A}_{\bot}$ (if the row has $A=t$, this row is "covered" by $\phi^{A}_{\top}$ and if the row has $A=f$, it is covered by$\phi^{A}_{\bot}$.

So the taut implication still hold : of course, $A$ must not be in $\psi$, because substituting $A$ with $\top$ or $\bot$, we have lost "the link" between the two original formuals when we use the valuation $v$.

Now I think that you can easily use this argument to show satisfiability...

Mauro ALLEGRANZA
  • 94,169
  • 1
    @ Mauro ALLEGRANZE Thank you for great advice! I have another question here: How do I make use of this result to show: If $\alpha \models \beta,$ then there exists $\gamma,$ all of whose sentence symbols occur BOTH in $\alpha$ and $\beta$ such that $\alpha \models \gamma \models \beta$ ? – Alexy Vincenzo Feb 24 '14 at 13:50
  • 1
    This is Craig'Interpolation Theorem : you can find a proof in some textbooks. Kleene's has it, but for me is difficult. You can try with George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007), page 260; or with Geoffrey Hunter, Metalogic An Introduction to the Metatheory of Standard First Order Logic (1971), page 61 for propositional logic. – Mauro ALLEGRANZA Feb 24 '14 at 13:58
-1

I'm assuming that we're talking first-order predicate logic here and that $\models$ refers to logical consequence. You could first show that $\phi_* ^{A} \models \phi$. Because $\models$ is transitive, the result you're looking for follows from that.

user130888
  • 89