I would like to understand more precisely the relation between the basic truth table method to test validity of formulas (and of reasonings) and the more advanced set theoretic definition of validity in terms of " interpretations".

Knowing that the truth table for a "2 atomic sentences" formula ( such as : P&Q --> P ) has only 4 rows, and suspecting that there are much more than 4 interpretations ( = functions from the infinite set of atomic formulas to the set {T,F} ), how to relate these two statements :

(1) the formula has the truth value T in each of the 4 rows of its truth-table

(2) the formula is true in all possible interpretations

In other words, how can the 4 rows of a truth table represent the infinite set of possible interpretations?

Remark. - Can this problem be solved using the concept of equivalence class: saying that interpretation 1 and interpretation 2 are equivalent just in case they attribute the same truth values to the atoms of my "4 atoms formula", and that the whole set of interpretations is therefore partitionned into 4 equivalence classes, each classe being represented by a row in the truth table?

  • $\begingroup$ Why do yoy say that in case of a two-letters formula like $(P \land Q) \to P$ there are more than four int ? with $n$ letters the possible combinations of truth-value are exactly $2^n$; thus, for $n=2$ they are $4$. $\endgroup$ – Mauro ALLEGRANZA Apr 18 at 14:24
  • $\begingroup$ @MauroAllegranza. I thought that validity ( of a formula) was defined not simply in terms of possible interpretations of its atomic sentences, but in terms of possible interpretations of the whole set of atomic sentences in the language. I thought that an interpretation was a function having as domain the whole ( infinite) set of atomic sentences. $\endgroup$ – Eleonore Saint James Apr 18 at 14:28
  • $\begingroup$ Correct........ $\endgroup$ – Mauro ALLEGRANZA Apr 18 at 14:33
  • $\begingroup$ You can review the basic def on any ML textbook; see e.g. (for free) S.Simpson, Mathematical Logic or Van Dalen, Logic and Structure. $\endgroup$ – Mauro ALLEGRANZA Apr 18 at 14:36

A row in a truth table of a propositional logic formula is a truth assignment i.e. the concept corresponding (in the Boolean world of classical propositional logic) of the more general concept of interpretation.

In classical propositional logic, every truth assignment (or valuation) define a "possible world".

Thus, the concept of tautology is the propositional counterpart of "logical truth", i.e. formula that is true in every possible world (every interpretation).

A truth assignment define a truth value for each propositional letter (or atom) of the alphabet, and there are infinite many truth assignment (being the propositional letters countable many).

But obviously, two truth assignments $v_1$ and $v_2$ such that :

$v_1(P)=v_2(P) \text { and } v_1(Q)=v_2(Q)$

will assign to the formula $(P \land Q) \to P$ the same truth value.

This is the reason why the truth table mechanism is an effective proceudre that solve the validity problem for propositional calculus.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.