Testing logical validity

Question

My understanding of a logical formula being valid is that it concludes something, for example:

$[(A \rightarrow B) \wedge (B \rightarrow C)] \rightarrow [A \rightarrow C]$ is logically valid. (I may be mixing this up with rule of inference)

I'm trying to understand if a method I found is able to determine if a formula is logically valid. Using elementary algebra it is possible to establish the following relations

$a \wedge b = ab \qquad $and $\qquad ¬a = 1-a$

From these it follows that

$a \rightarrow b = 1-a+ab$

where $+$ and $\times$ are being used in the everyday sense.

---

The method:

Using the above relations it is possible to convert the original statement into elementary algebra.

$[(A \rightarrow B) \wedge (B \rightarrow C)] \rightarrow [A \rightarrow C]$

Evaluating the 'outermost' implication yields:

$1-[(A \rightarrow B) \wedge (B \rightarrow C)] + [(A \rightarrow B) \wedge (B \rightarrow C)][A \rightarrow C]$

Evaluating the next implications yields

$1-[(1-a+ab) \wedge (1-b+bc)] + [(1-a+ab) \wedge (1-b+bc)][1-a+ac]$

Evaluating the ANDs yields

$1-[(1-a+ab)(1-b+bc)] + [(1-a+ab)(1-b+bc)][1-a+ac]$

Expanding the parentheses gives

$1-[1-a-b+ab+bc] + [1-a-b+ab+bc][1-a+ac]$

Expanding the brackets gives

$1 - [1-a-b+ab+bc] + [1-a-b+ab+bc]$

Which simplifies to

$1$

---

I am interpreting this 1 as saying that the original formula was logically valid. Is this a correct interpretation? If not, what is this $1$ telling me? I know that it means that for all possible inputs into the logical expression, the expression holds, does this imply validity?

Answer 1

I am interpreting this 1 as saying that the original formula was logically valid. Is this a correct interpretation? If not, what is this $1$ telling me? I know that it means that for all possible inputs into the logical expression, the expression holds, does this imply validity?

Yes.

A valid statement is a tautology.

That is that it is valued as true (ie $1$) for all interpretations of its literals.

Answer 2

Two comments.

First, $(1-a+ab)(1-b+bc)$ works out to $1-b+bc-a+ab-abc+ab-ab^2+ab^2c$

This only works out to $1-a-b+ab+bc$ if $ab^2 = ab$ and $ab^2c=abc$ ... which you call 'Idempotence. Which is of course fine for a boolean algebra, but you can not say that:

$+$ and $\times$ are being used in the everyday sense.

or that this is

elementary algebra

Also, when working this out, you get:

$[1-a-b+ab+bc][1-a+ac]=$

$1-a-b+ab+bc-a+a^2+ab-a^2b-abc+ac-a^2c-abc+a^2bc+abc^2$

Now, again you need the non-every-day-sense and non-elementary-algebra move of Idempotence to equate this to:

$1-a-b+ab+bc-a+a+ab-ab-abc+ac-ac-abc+abc+abc$

and only now do you get to:

$1-a-b+ab+bc$

Moreover, how is this any simpler than Boolean algebra?

Here is your solution all written out:

$[(A \rightarrow B) \wedge (B \rightarrow C)] \rightarrow [A \rightarrow C]=$

$1-[(A \rightarrow B) \wedge (B \rightarrow C)] + [(A \rightarrow B) \wedge (B \rightarrow C)][A \rightarrow C]=$

$1-[(1-a+ab) \wedge (1-b+bc)] + [(1-a+ab) \wedge (1-b+bc)][1-a+ac]=$

$1-[(1-a+ab)(1-b+bc)] + [(1-a+ab)(1-b+bc)][1-a+ac]=$

$1-[1-b+bc-a+ab-abc+ab-ab^2+ab^2c] + [1-b+bc-a+ab-abc+ab-ab^2+ab^2c)][1-a+ac]=$

$1-[1-b+bc-a+ab-abc+ab-ab+abc] + [1-b+bc-a+ab-abc+ab-ab+abc][1-a+ac]=$

$1-[1-a-b+ab+bc] + [1-a-b+ab+bc][1-a+ac]=$

$1-[1-a-b+ab+bc] + [1-a-b+ab+bc-a+a^2+ab-a^2b-abc+ac-a^2c-abc+a^2bc+abc^2]=$

$1-[1-a-b+ab+bc] + [1-a-b+ab+bc-a+a+ab-ab-abc+ac-ac-abc+abc+abc]=$

$1 - [1-a-b+ab+bc] + [1-a-b+ab+bc]=$

$1$

By contrast, here is the Boolean algebra solution:

$[(A \rightarrow B) \land (B \rightarrow C)] \rightarrow [A \rightarrow C] =$

$\neg [(\neg A \lor B) \land (\neg B \lor C)] \lor [\neg A \lor C] =$

$\neg (\neg A \lor B) \lor \neg (\neg B \lor C) \lor [\neg A \lor C] =$

$( A \land \neg B) \lor (B \land \neg C) \lor \neg A \lor C =$

$\neg B \lor B \lor \neg A \lor C =$

$\top \lor \neg A \lor C =$

$\top$

Seems to me the Boolean algebra method is a good bit more efficient.

In sum. Yes, your method works ... but you have to assume Idempotence, and it is not everyday or elementary algebra. And second, classical Boolean algebra is a good bit more efficient.