Suppose $A$ is a propositional formula where precisely $n$ propositional atoms appear. For example, letting $n$ be $3$, $((p \land q) \rightarrow r)$ is an example of such a formula. My question is, what is the formal definition of a truth table for $A$? I know what it is informally, but I would like a mathematical implementation of a truth table. I guess it would be a matrix of some sort, but other than that, I have no clue how to formalize the intuitive notion of truth tables. Can someone give me a formal definition of a truth table for a formula?
Asked
Active
Viewed 57 times
1 Answers
1
I would just say the truth table is a function from $\{0,1\}^n$ to $\{0,1\}$. (Or use any set of two symbols: $\{F,T\}$, $\{\bot, \top\}$, etc.) For example, the function for your formula $((p \land q) \rightarrow r)$ maps $(0,1,1)$ to $1$, since the valuation with $p$ false, $q$ true, and $r$ true makes the overall formula true. And two formulae are logically equivalent if and only if their corresponding functions are equal.
This function doesn't by itself imply any visual layout, but it contains all the information for a typical truth table: the domain has $2^n$ elements, so we can write out $2^n$ rows with the atom values and the resulting formula value on each row.
aschepler
- 9,449
-
I was hoping for a definition in terms of matrices. Like, for a propositional formula with exactly $n$ propositional atoms, there would be a matrix with $2^n + 1$ rows, where the first row contains the subformulas, and the remaining $2^n$ rows would be filled with $1$'s and $0$'s. – user107952 Feb 02 '22 at 21:22
-
You could define something like that as a tuple of tuples or whatever, but I wouldn't call it a matrix. A matrix has all its entries from the same ring, not formulas in one row and values in others. A matrix represents a linear transformation and can be added to another matrix of the same size, multiplied by a scalar, or left-multiplied or right-multiplied with another matrix of appropriate size. – aschepler Feb 02 '22 at 21:42