Solutions for True or False problems.

Problem 5.6.6 (a) Page 221

Any set which is truth functionally consistent is also SD-consistent.
True

Suppose that \Gamma is TF-consistent but \Gamma is not SD-consistent.  
We will derive a contradiction.

[\Gamma is TF-consistent]  translates to  
[there is a tva \tau such that \tau |= \Gamma

[\Gamma is not SD-consistent]  translates to [\Gamma is not not SD-inconsistent].
which in turn translates to:
[\Gamma is SD-inconsistent]

This means we have an SD derivation:       
	Premises            \Gamma
	   ....              .....
	justifications        wffs
	    "                   "
	justification         \beta
	justifications        wffs
	    "                     "
	justification         ¬\beta

We have assumed there is a tva \tau |= \Gamma.
By the Soundness Theorem, this  'truth'  will flow through the derivation,
so that  \tau |= \beta  and  \tau |= ¬\beta.   

If  \tau |= ¬\beta,  then  (\tau |= \beta) is false.  This contradicts  
\tau |= \beta.  With this contradiction we have completed the 
demonstration that the sentence is true.

Comments on the strategy It is valuable to restate the original sentence in as concrete terms as possible. Thus TF-consistent says a certain kind of line exists in the truth table. SD-inconsistent means there is a particular derivation with specific lines (\beta and then ¬\beta). Typically, a sentence which is keyed to a negative concept suggests one of two strategies (which are also basic in SD and SD+). (a) Argue towards a contradiction. (b) Consider the contrapositive of any conditional involving negative statements. (See the solution to (b) below, where this strategy is used.)

Problem5.6.6 (b) Page 221

Any set which is SD-consistent is also TF-consistent.
True

Suppose that  \Gamma is not TF-consistent.  

[\Gamma is not TF-consistent]  translates to  
[No tva \tau has the property  \tau |= \Gamma]

Therefore, by the usual case for empty sets, the following conditional holds:
(Comment by Ganong: Whenever \tau |= \Gamma (i.e., never), ....)

[If  \tau |= \Gamma  then  \tau|= A& ¬A].
Equivalently:  [\Gamma |= A& ¬A].

By the Completeness Theorem,  if  [\Gamma |= A& ¬A]  then  
[\Gamma |- A& ¬A].
(comment by Ganong: On a test, I would want the derivability symbol
here to have a subscript (SD, or SD+, depending on the context); it is
too hard to type this in html.)

So we now have  [\Gamma |- AA& ¬A].
Applying  ¬EL  and then  ¬EL  on this last formula, this 
guaranteed derivation becomes a demonstration that
  [\Gamma  is  SD-inconsistent].

[\Gamma is not SD-consistent]  translates to 
[\Gamma is not not SD-inconsistent].
which in turn translates to:
[\Gamma is SD-inconsistent]

This completes the argument that:
if  [\Gamma is TF-inconsistent] then  [\Gamma is SD-inconsistent].

This is the contrapositive of the original sentense.  
As such it is logically equivalent and both sentences are true.

Section 5.6.6 (c) Page 221:

If \alpha is a sentence of SL that is truth-functionally true then \alpha is an SD-theorem of \Gamma regardless of the sentences in \Gamma.
True

Suppose that \alpha is a tautology and \Gamma is a set of sentences.

Every tva \tau |= \alpha.
Therefore if \tau|= \Gamma then \tau|= \alpha.
This means that \Gamma |= \alpha.

By completeness, \Gamma |- \alpha.
This means that \alpha is a SD-theorem of \Gamma.

Section 5.6.6 (d) Page 221:

If \Gamma is SD-consistent, than all truth functionally true sentences of SL are SD-theorems of \Gamma.
True

This is just a special case of (c). The same argument works, without reference to whether \Gamma is SD-consistent.

Problem 5.6.6 (e) Page 221:

There is a set whose SD-theorems are precisely the contingent sentences of SL.
False

Consider an example with only one letter  A.  
{This a good strategy in any case where you are not even sure 
what the sentences  means .}

In terms of a single letter  A, we have the following examples of  wffs:
contingent:   {A, \not A,  A -> ¬A, ...  };
not contingent:  tautologies  {  Av¬ A,  A->A, ... };
                 contradictions  {  A&¬ A,  ... }.

The sentence proposes that some set of sentence  \Gamma  will give 
derivations of  {A, ¬A, ... }  but not  {  Av¬A,  A->A, ... }  or  
{  A&¬A,  ... }.

We now see two very real problems:

If  \Gamma|-  A  and  \Gamma|- ¬ A,  then  \Gamma|-  A&¬ A.
      because of the &I  rule.

Every set  \Gamma  gives derivations of tautoligies:   \Gamma|- Av¬A.

Each of these events is the evidence we need to conclude the statement is false.

Problem 5.6.6 (f) Page 221:

If there is a sentence which is not an SD+-theorem of \Gamma, then \Gamma is SD+-consistent.
True

This is a good example for considering the contrapositive:

If [\Gamma is not SD+-consistent] then 
     [every sentence is  an SD+-theorem of  \Gamma].
Equivalently, this says:
If [\Gamma is SD+-inconsistent] then 
   [every sentence \alpha is  an SD+-theorem of  \Gamma].

We now translate to see what this means.
Suppose  [\Gamma is SD+-inconsistent].
This means we have an SD derivation:       
	Premises            \Gamma
	   ....               .....
	justifications        wffs
	   ."                   "
	justification         \beta
	justifications        wffs
	   ."                   "
	justification         ¬\beta

With this derivation in front of us, and any wff  \alpha,  we can just
patch on the lines:
	Assumption              +-  ¬\alpha
	R                       |    \beta
	R                       +-  ¬\beta
	¬ ER                \alpha
This new longer derivation demonstrates that  [\Gamma|- \alpha].
Equivalently  [every sentence \alpha is  an SD+-theorem of  \Gamma].

This completes the demonstration of the contrapositive of the original 
sentence.


Section 5.6.6 (g) Page 222:

There is a set \Gamma with no SD+-theorems.
False

Look at the argument for (c). By the same argument applied to any \Gamma, all tautologies such as
A v ¬A are SD-theorems of \Gamma.

Section 5.6.6 (h) Page 222:

If SL is the set of SD+theorems of \Gamma then \Gamma must be SD+ inconsistent.
True

Suppose all wffs of SL are SD+-theorems of \Gamma. In particular, A & ¬A is an SD+-theorem of \Gamma. We have

	Premises            \Gamma
	   ....                     ......
	justifications        wffs
	   ."                     "
	justification      i  A & ¬A
Add the two additional lines
	&EL i              A	\alpha
	&ER i              ¬A	¬\alpha
This completes a demonstration that \Gamma is SD+-inconsistent.

Section 5.6.6 (i) Page 222:

If \Gamma |- P v (R -> ¬Q) then \Gamma |- P v (¬R v ¬Q).
True

Assume \Gamma |- P v (R -> ¬Q). We have two options.

(i) We take the guaranteed SD-derivation of P v (R -> ¬Q) and graft on the derivation (in SD) starting with P v (R -> ¬Q) and ending with P v (R -> ¬Q). [You can figure one out - using vE and ¬E etc.]

(ii) We can use soundness to get: \Gamma |= P v (R -> ¬Q).
Then use truth tables to check that [ {P v (R -> ¬Q)}|= P v (¬R v ¬Q) ]. Therefore \Gamma |= P v (¬R v ¬Q). Finally completeness gives the desired fact: \Gamma |- P v (¬R v ¬Q)

Section 5.6.6 (j) Page 222:

The rule of De Morgan is dispensible in SD+.
True

A rule is dispensible if we can prove the same theorems without this rule (we just happen to need longer derivations).

Assume that \Gamma |- \beta in SD.
By soundness \Gamma |= \beta (in SL).
By Completeness of SD \Gamma |- \beta using just rules of SD.

We conclude that every rule in SD+ is dispensible.

However the rules of SD+ sure are nice: they let us find proofs in a reasonable time!

Section 5.6.8 (b) Page 222:

If { } |= \alpha then \Gamma |= \alpha.
True

Suppose { } |= \alpha. By Completeness, { } |- \alpha.

(no premises)	
	justifications        wffs
	   ."                     "
	justification      i  \alpha

If we just graft on the set  \Gamma as premises, this is still a derivation:
	Premises            \Gamma
	justifications        wffs
	   ."                     "
	justification        \alpha
This completes the proof that  \Gamma |= \alpha.

Section 5.6.8 (c) Page 222:

If there is a tva which satisfies \Gamma but does not satisfy \alpha, then \alpha is not SD-derivable from \Gamma.
True

Suppose there is a tva which satisfies \Gamma but does not satisfy \alpha.
This means that not[ \Gamma |= \alpha].,br> By the contrapositive of soundness, not [ \Gamma |- \alpha].


Back to 2090 Home Page