0

I'm considering the following problem from Elliott Mendelson's book "Introduction to Mathematical Logic".

enter image description here

The proof of (b) he gives is as follows: A conjunction $\mathscr{E}$ of the form $B_1^{*}\wedge B_2^{*}\dots\wedge B_n^{*},$ where each $B_i^{*}$ is either $B_i$ or $\neg B_i,$ is said to be eligible if some assignment of truth values to the statement letters of $\mathscr{B}$ that makes $\mathscr{B}$ true also makes $\mathscr{E}$ true. Let $\mathscr{C}$ be the disjunction of all eligible conjunctions. $\square$

In the particular case of (c), this leads us to the statement form $\mathscr{C}=(B_1\Rightarrow B_2),$ and I agree both $\mathscr{B}\Rightarrow\mathscr{C}$ and $\mathscr{C}\Rightarrow\mathscr{D}$ are tautologies.

However, I'm concerned about what happens if we change $\mathscr{D}$ to be $$((B_1\wedge C)\Rightarrow(B_2\wedge C))\wedge(B_1\vee B_2\vee \neg C)$$

Essentially this changes the truth table of $\mathscr{D}$ to give $F$ when $B_1,B_2$ are $F$ and $C$ is $T$.

It's certainly still true that $\mathscr{B}\Rightarrow\mathscr{D}$ is a tautology, and applying the algorithm in the solution still suggests that $\mathscr{C}=(B_1\Rightarrow B_2)$ should do the job.

However, note that we now have a case where $\mathscr{C}$ is $T$ yet $\mathscr{D}$ is $F$ - namely when $B_1,B_2$ are $F$ and $C$ is $T$. Thus we no longer have that $\mathscr{C}\Rightarrow \mathscr{D}$ is a tautology.

In fact, for the altered example, I'm fairly confident no suitable $\mathscr{C}$ exists, as its value when $B_1,B_2$ are $F$ has to both be $T$ (since $\mathscr{B}\Rightarrow\mathscr{C}$) and $F$ (since $\mathscr{C}\Rightarrow\mathscr{D}$).

Where exactly am I going wrong?

Zerkoff
  • 489

1 Answers1

2

It is not the case that $\mathscr{B}\implies\mathscr{D}'$ is a tautology (where $\mathscr{D}'$ is your modified version of $\mathscr{D}$). We can see this by finding a truth assignment making $\mathscr{B}$ true but $\mathscr{D}'$ false.

Specifically, consider the valuation making $A,B_1,$ and $B_2$ false and making $C$ true. Then the conjunct $B_1\vee B_2\vee\neg C$ in $\mathscr{D}'$ is false, so $\mathscr{D}'$ as a whole is false, but $\mathscr{B}$ is trivially true.

Noah Schweber
  • 245,398
  • Oh, that makes sense. I was mislead by how I'd written my truth tables (I was only comparing cases where $A$ and $C$ agreed. ) Thanks! – Zerkoff Jun 23 '21 at 18:59