Relation between propositional logic, boolean algebras and truth tables

Question

I am a bit confused with the relation between propositional logic, boolean algebras and truth tables.

Propositional logic starts with a language over a set of primitive propositions, they are called formulas. Together with inference rules, you have a notion of entailment between those formulas.

A boolean algebra is just an algebraic structure. It seems I can give a boolean algebra structure to the set of formulas of propositional logic (by taking first appropriate quotients). Also, it seems that given a valuation of primitive propositions into elements of the boolean algebra, I can extend it to the whole set of formulas.

But then, there is this notion of truth tables, which seems to be important for propositional logic. They explain how the connectives of propositional logic "work". But I do not understand their relation with boolean algebras and propositional logic. It seems that true-false form a boolean algebra, and truth tables explain how the operations for this boolean algebra works. But why is it so important? Why do we care so much about truth tables and present this particular true-false boolean algebra as "propositional logic/boolean algebra"?

Answer 1

I can't clearly make out your question, but I hope this clarifies things.

Propositional logic deals with 'propositions': statements that can either be true or false. We can apply some constructs to these statements to come up with new statements, whose truth is completely determined by the truth of its component statements.

Boolean algebra deals with variables/symbols that can either be 0 or 1 (or equivalently, 'on' or 'off', or 'red' or 'green', or whatever: just two different states). We can apply some operators to these variables and the system is such that the results are completely determined by the values of the operands.

Do you see the connection now? We can have 'boolean variables' represent the truth of statements, and we can use familiar algebra operators -- addition and multiplication -- on these variables to represent the constructs of propositional logic. Essentially, we have two ways of looking at the same thing. And then we have a third way of analyzing the situation, called 'truth tables'. There is no operator or construct involved in a truth table; rather, the truth table statically represents the value of a construct in propositional logic or an operation in boolean algebra.

Answer 2

Hopefully this helps in regards to truth-tables, propositional logic, and the connectives.

Your statements on what propositional logic starts off with is misleading/inaccurate. There are no primitive formulas that the language starts with. What is provided is a grammar, syntax, and semantics. From the first 2 you define which strings of the symbols will be considered well-formed formulas. A language may start off in the beginning saying something like "Our grammar consists of a countable set of propositional variables $P_1$,$P_2$,$P_3$,... " but even at this point those symbols would not be considered well formed formulas for the notion of a WFF hasn't been

In regards to truth-tables, it is helpful if you understand that propositions (WFFs) of a given propositional logic can be/are regarded as truth-functions/Boolean functions and the connectives are actually truth-functional-connectives.

The propositional variables of a given system will either hold the boolean value of 'true' or of 'false'. And depending on the particular connective between the two, the overall proposition will then also either have a value of either true or false.

We go from taking in inputs of Boolean values of the variables, to outputting a single Boolean value of the whole propositon.

There are then, a particular number of truth-functions one can have, given 2 variables, given 3 variables, etc...

For example, given 2 variables 'P' and 'Q', one can have 16 truth-functions. A function which outputs 'true' when P has a value of true and when Q has a value of true. This is commonly denoted as 'P$\land$Q'

A function which outputs 'true' if: P has a value of true and Q has a value of true P has a value of false and Q has a value of true P has a value of false and Q has a value of false. This is commonly denoted as 'P $\rightarrow$ Q' However, perhaps you are familiar that this can also be denoted as '~P $\lor$ Q'

There are 14 other functions here (that's simply the amount of different combinations from values of P and Q to a singe output value that we can get)

Notice, how there can be more than 1 WFF corresponding to a particular truth-function. For a WFF is any sting of symbols which the system defines as being well-formed.

Perhaps you have noticed that different propositional logics use different sets of connectives. This is acceptable as all a given system needs (in regards to the connectives) is that the connectives being employed are capable of producing all the truth-functions.

So, for example if the only connectives a system used were '$\lor$' and '$\land$', then just think of how one would present the truth-function which is defined to be such that it outputs a value of 'true' when every variable has a value of 'false'.

We wouldn't be able to have a truth function which outputs 'true' when it's sole variable (say $P$) takes a value of 'false'.

The point being, that the connectives are truth-functional and allow us to have truth-functions. We need a set of connectives which can produce all the possible truth-functions.

Where the truth-tables come into play is when we need to define, like you said, how the connectives "work". We understand how they work when we understand what output the overall function (that the connective is employed in) will be, when we are given a particular combination of truth-values of the variables in the formula.

If we did not do so, then the connectives would be useless.

Now, an easy schematic way to define the connectives (as opposed to writing down a statement that says: " '$\rightarrow$' is a binary connective. If 'P' and 'Q' are well-formed-formulas then 'P $\rightarrow$ Q' is only true when: P is true and Q is true, when P is false and Q is true, when P is false and Q is false. "

is to present the information just stated in a truth-table. And so we use truth-tables. Additionally, when we are given complex WFFs truth-tables can be an easy way to keep track of the truth-values of all the sub formuluas and thus in determining the truth (or falsity) of the overall WFF.

Answer 3

A boolean function with $n$ variables is simply a function from $\{T, F\}^n \to \{T, F\}$. Since the domain has finitely many elements ($2^n$ to be exact) we can represent the function by simply explicitly stating what the function value is for each element in the domain. A truth table is simply a systematic way of organizing this representation.