Mario De León Urbina

Formulas from a given Truth Table

Resumen: En el Tractatus, Ludwig Wittgenstein presenta una teoría de la lógica y su naturaleza en los aforismos 4, 5 y 6. Especialmente del 4.31 al 5.101, son presentados tablas de verdad, tautología, contradicción, número de posibilidades de verdad dadas en proposiciones elementales, funciones de verdad, etc.. La idea a la base de este artículo es exponer estos conceptos desde un punto de vista matemático, con especial atención al resultado que nos dice que dada una tabla de verdad se puede construir la fórmula correspondiente.

Palabras clave: Wittgenstein, Tractatus logico-philosophicus, Tablas de verdad, Filosofía de la lógica.

Abstract: In the Tractatus, Ludwig Wittgenstein presents a theory of logic and its nature in aphorisms 4, 5, and 6. Especially from 4.31 to 5.101, truth tables, tautology, contradiction, the number of truth possibilities given n elementary propositions, truth functions, etc., are presented. The idea of this article is to expose these concepts from a mathematical point of view, with particular attention to the result that tells us that given a truth table, a corresponding formula can be constructed.

Keywords: Wittgenstein, Tractatus logico-philosophicus, Truth Tables, Philosophy of Logic.

1. Introduction

Truth tables are one of those objects that have always caught my attention. According to certain rules for assigning truth values to propositional variables, we place V for «true» or F for «false», and then arrive at the truth value (or falsity) of a compound proposition that involves «basic» logical connectives. I always wondered why those rules worked so well, and gradually I gained access to what is called «basic propositional calculus», which is learned in a very elementary and mysterious way in the early courses of a Mathemat- ics degree. However, we never really knew the specific syntax rules for forming valid expressions, much less what a language means in the logical sense.

While taking the «Seminar on Wittgenstein I» at the University of Costa Rica and reading the Tractatus Logico-Philosophicus, I discovered that Wittgenstein was talking about propositions, truth tables, and tautologies, as well as some calculations that initially seemed very intriguing to me. Questions arose immediately: What did those calculations represent? What were these «truth functions»? And the unsettling doubt was, how is it possible that given a truth table for n atomic propositional variables, there exists a formula that represents it? All of this truly unsettled me, and it was then that I turned to the texts on mathematical logic used in advanced optional Mathematics courses. That’s when I understood what Wittgenstein had written. My intention is that the results presented here–which are not original to me, but rather an adaptation of the excellent text by Cori & Lascar titled «Mathematical Logic: A course with Exercises»– help to grasp with clarity and rigor the ideas expressed by Wittgenstein and that contain updated notation. What I do add are some examples or rearrange certain proofs (which are not many here) to provide clarity in the exposition (which I do not consider to be very clear initially).

2. Syntax, Words and Formulas

We will omit the rules for forming «well-formed formulas» regarding syntactic rules, and the reader can consult sources on that matter. We will dive directly into propositional formulas, also known as well-formed formulas. Furthermore, we will restrict ourselves to propositional calculus, that is, a zero-order logic.

Definition 1 (Propositional Formulas). Let P= ∅ be a finite or infinite set called the set of propositional variables. The elements of P are denoted by uppercase letters from the alphabet with subscripts. Additionally, we have the symbols

¬ ∨ ∧ ⇒ ⇔

which are known as propositional connective symbols, assuming that these elements do not belong to P. ¬ is a unary symbol, and the other symbols are binary. Furthermore, we have the symbols) and (, called the closing parenthesis and opening parenthesis, respectively, which are distinct from the elements in P and the connectives.

A propositional formula refers to a word formed using the following alphabet:

Definition 2. The set F of propositional formulas constructed from P is the smallest set of words in the set of words W(A) such that

• P ⊂ F;

• If F ∈ F then ¬F ∈ F;

• If F, G ∈ F then (F α G) ∈ F, where α ∈ {∧, ∨, ⇒, ⇔}

In other words,

with W ⊆ W(A) endowed with the mentioned properties.

If there is no ambiguity, in some cases, we will omit the parentheses. Thus, (A ∧ B) will be written as A ∧ B.

The set F can be defined inductively. Let’s consider the sequence. (Fn)n∈N ⊂ W(A), such that

F0 := P ,

Fn+1 := Fn ∪ {¬F : F ∈ Fn} ∪ {(F α G) : F, G ∈ Fn, α ∈ {¬, ∨, ∧, ⇒, ⇔}} .

That sequence is increasing: ∀m ≤ n, Fm ⊆ Fn.

Theorem 3.

Definition 4 (Occurrences of propositional variables). Let F ∈ F be a formula, and let

{Ai} i = 1 ⊆ P be pairwise distinct propositional variables. The notation F [A1, A2, ..., An] emphasizes the elements of P that occur at least once in F.

Definition 5 (Replacement of variables by formulas). Let F ∈ F such that

F = F [A1, A2, ..., An, B1, B2, ..., Bm]

and let n formulas G1, ..., Gn be given. Consider the word obtained by replacing Ai with

Gi. We denote this substitution as

FG1/A1, G2/A2, ... Gn/An

Theorem 6. Given n ∈ N, formulas F, G1, G2, ..., Gn, and propositional variables A1, A2, ..., An, the word FG1/A1, G2/A2, ... Gn/An ∈ F, i.e., it is also a formula.

3. Semantics and Truth Tables

Lemma 7. Let E be a non-empty set. Let ψ0 :
P → E, f : E → E, and the mappings from E2 to E, g, h, j, k : E2 → E. Then there exists a unique mapping ψ : F → E that satisfies the following conditions:

• ψ = ψ0

• ∀F ∈ F, ψ(¬F ) = f (ψ(F))

• ∀F, G ∈ F,

ψ(F ∧ G) = g(ψ(F ) · ψ(G))

ψ(F ∨ G) = h(ψ(F ), ψ(G))

ψ(F ⇒ G) = j(ψ(F ), ψ(G))

ψ(F ⇔ G) = k(ψ(F ), ψ(G))

Definition 8. A truth valuation ν on P is a mapping ν : P → {0, 1}, i.e., ν ∈ {0, 1}.

Traditionally, the set {V, F} is used to assign truth values to well-formed formulas, but using the set {0, 1} has its advantages, although both can be identified with the finite field (Z/2Z, +, ·).

Theorem 9. For any ν ∈ {0, 1} , there exists a unique mapping ν: F → {0, 1} which is an extension of ν, with , and it satisfies the following properties:

Proof: We identify {0, 1} with Z/2Z. Let x, y ∈ Z/2Z, and consider the functions:

By the previous lemma, we set ψ0 := ν, and we define ψ: = ν. Then, for any F, G ∈ F, we have:

These equalities are known as the elementary truth tables of ¬F, F∧G, F∨G, F ⇒ G, and F ⇔ G, respectively. □

For example, if we have the formula

R ⇒ (Q ⇒ (P ⇔ (Q ⇒ R)))

and we assign ν(P) = 1, ν(Q) = 0, ν(R) = 1, we can evaluate each subformula:

• ν(Q ⇒ R) = 1 + 0 + 0 · 1 = 1

• ν(P ⇔ (Q ⇒ R)) = 1 + 1 + 1 = 1

• ν(Q ⇒ (P ⇔ (Q ⇒ R))) = 1 + 0 + 0 · 1 = 1

• ν(R ⇒ (Q ⇒ (P ⇔ (Q ⇒ R)))) = 1 + 1 + 1 · 1 = 1

In a more practical and concise way, we can visualize it as follows:

Definition 10 (Satisfaction). If F ∈ F band ν is a truth assignment (or valuation), we say that F is satisfied by ν or that ν satisfies F when ν (F) = 1.

Lemma 11. For any formula F [A1, ..., An] that only contains occurrences of A1, ..., An, and truth assignments λ, µ ∈ {0, 1}P that coincide on {Ai}, then λ (F) = µ (F).

Definition 12 (Tautology). A tautology is a formula that evaluates to 1 for every truth assignment.

• The notation ⊢ F means «F is a tautology».

• Given F, G ∈ F, we say that F is logically equivalent to G if and only if the formula F ⇔ G is a tautology. We denote this relationship as F ∼ G.

From the previous definitions, the following can be deduced:

• For all F, G ∈ F, F ∼ G if and only if for all ν ∈ {0, 1}P , ν(F) = ν(G).

• The binary relation ∼ is an equivalence relation on F.

Tautologies constitute one of the equivalence classes for the relation ∼, and we can denote it as 1. Another equivalence class is the «negation» of the class 1, which contains what is known as antilogies or contradictions. We denote this class as 0. Formulas that do not belong to these equivalence classes are referred to as contingencies. In general, the equivalence class of F is denoted as cl(F).

Simplifying the notation, let’s assume that P = {A1, A2, ..., An}. Then, any formula F ∈ F can be written as F = F [A1, ..., An]. We have the following notations:

• For each (ε1, ε2, ..., εn) ∈ {0, 1}n, we denote νε, ε2, ...,εn as the truth value assignment defined by νε1,ε2,...,εn (Ai) = εi por each i = 1, 2, ..., n.

• For each propositional variable A and for each element ε ∈ {0, 1}, we denote εA as the formula

• For each formula F, let ∆(F) be the set of truth value assignments that satisfy F:

∆(F) := {ν ∈ {0, 1} : ν(F) = 1}

• For each F ∈ F, we define the mapping
φF : {0, 1} P → {0, 1} as

φF (ε1, ε2, ..., εn) := νε1,ε2,...,εn (F)

The mapping φF can be referred to as the truth table of F.

For example, let’s consider P = {A1, A2} and F = A1 ∨ A2. We have the truth value assignments: ν0,0, ν0,1, ν1,0, and ν1,1. Then,

In summary,

Definition 13. Two formulas F and G are logically equivalent if and only if φF = φG.

This means that the mapping

Ξ : F → {0, 1}({0, 1}n)

such that Ξ (F) = φ is compatible

with the equivalence relation ∼. The mapping Ψ : F/ ∼→ {0, 1}({0, 1}n) such that Ψ(cl(F)) = φF is injective. This implies that the number of equivalence classes of the relation ∼

in F is at most equal to the number of mappings from {0, 1}n to {0, 1}, which is 22n.

By proving the surjectivity of Ψ, it is ensured that any truth table is associated with

a formula in F. In other words, given an arbitrary mapping from {0, 1}n to {0, 1}, the surjectivity of Ψ guarantees the existence of a formula for that truth table. For this, the following definitions and results are needed.

• If I = {i1, i2, ..., ik} is a non-empty set of indices and if Fi1, Fi2, ..., Fik are formulas, we define the formulas

Lemma 14. ∀(ε1, ε2, ..., εn) ∈ {0, 1}n, the formula

is satisfied by the truth value distribution νε1,ε2,...,εn and no others.

In other words,

Let’s consider an example. Let’s take the set {0, 1}2 and the pair of values (ε1 = 1, ε2 = 0). We then have the truth value distribution ν0,1 and the formula

therefore,

that is

ν0,1(¬A1 ∧ A2) = (1 + ν0,1(A1)) · ν0,1(A2) = 1 · 1 = 1

∆(¬A1 ∧ A2) = {ν0,1}

Lemma 15. Let ∅ = X ⊆ {0, 1}n and let Fx be the formula

Then the formula Fx is satisfied by the truth value assignments νε1,ε2,...,εn for which

(ε1, ε2, ..., εn) ∈ X, and only by them. In other words,

Theorem 16. For any mapping φ : {0, 1}n → {0, 1}, there exists at least one formula F

such that φF = φ. In other words, every mapping from {0, 1}n to {0, 1} is a truth table for a formula.

Proof: Let φ : {0, 1}n → {0, 1} be an arbitrary mapping:

• If φ only takes the value 0, then this is the truth table of, for example, F = A1∧¬A1.

• Otherwise, the set

X := φ−1({1}) = {(ε1, ε2, ..., εn) ∈ {0, 1}n : φ(ε1, ..., εn) = 1}

is non-empty, and by virtue of the previous lemma, the formula

is satisfied by the truth value assignments νε1,ε2,...,εn for which φ(ε1, ..., εn) =

1 and only by these assignments. In other words, ∀(ε1, ..., εn) ∈ {0, 1}n we have

νε1,...,εn (F) = 1 if and only if φ (ε1, ..., εn) = 1

This means that φ is the function φFX , the truth table of the formula F. □

The above theorem is what I consider to be very important, as it states that given a truth table, there exists a formula in F represented by that truth table.

Let’s consider an example. Suppose we have the following table:

Natural question is: which formula F = F [A1, , A2] corresponds to this truth table?

According to the theorem, it should be the following formula, where X ={(1, 0)}

(The last equivalence is given as an example to show a formula that is not expressed in disjunctive form and is known as «not implies», sometimes symbolized as ⇏.)

It can be verified that

νi,j(FX) = 0 for all (i, j) ∈ {0, 1}2\X = {(0, 0), (0, 1), (1, 1)}.

Let’s consider another example with three distinct propositional variables, simplifying the table, where blank spaces represent zeros:

Here X = {(0, 1, 0), (1, 0, 0), (1, 1, 0)}, and the formula is

You can verify the mentioned formula (or its equivalents) using an online truth table generator at the following link:

https://web.stanford.edu/class/cs103/tools/truth-table-tool/

and entering the following input:

Comparing with the table we proposed, the match is identical (except for a few minor details).

Figure 1: Screenshot using Truth Table Generator

4. In conclusion

The results presented in this document are necessary to understand the «one-to-one» rela- tionship between truth tables and well-formed formulas based on a set of n propositional variables. This relationship is very useful because calculations are often performed in the direction of compound formula → truth table, but the reverse direction is rarely seen in an introduction to basic logic. Here, we have discussed the direction of truth table → (almost one) compound formula.

References

Cori, René & Lascar, Daniel. 2000. Mathematical Logic. A course with Exercises. Part I. Oxford: Oxford University Press.

Wittgenstein, Ludwig. 2017. Tractatus Logico-philosophicus. Madrid: Gredos.

Mario Alejandro De Leon Urbina (mario.deleon@ucr.ac.cr) Licenciado en Enseñanza de la Matemática. Actualmente es profesor en la Escuela de Matemática de la Universidad de Costa Rica. Dentro de sus publicaciones recientes destaca: «Algunas reflexiones en torno a los números irracionales». (Info completa del articulo: https://repositoriotec.tec.ac.cr/handle/2238/12952?show=full )

Recibido: 29 de septiembre, 2023.

Aprobado: 6 de octubre, 2023.