Are the structure of logical expression based on formative constructions like sequences or trees ?

Recently, I get confused when reading the book Principles of Mathematical Logic written by D. Hilbert. How to define the term 'logical expression'?

I just envisage that it might be defined as anyone who occur in a sequence , for whose element, one of the following conditions is satisfied.

A. it is an elementary expression, denoted $X, Y, Z$, ...

B. Constructed by two preceding elements with function notation & (and) $\lor$ (or).

C. constructed by one preceding element with function notation $一$ (negation).

This definition is similar to that of formative construction given by Bourbaki in his Theory of Sets, Chapter 1 : Description of formal mathematics.

Another idea is the tree model, the source of leaves just can be elementary expressions, and the tree constructed by &, $\lor$, $一$.

The point is that the two methods can't tell me the precise procedure even when we solve the simple question like : How a general logical expression cab be brought into a certain normal form (conjunction of disjunction ...).

I beg someone could tell me how I find the precise and constructive proof method with manipulation , like computer procedure. I may bewitched by my intelligence, like Wittgenstein said. Could I find some safe proof methods, please recommend some books, I get confused for so long a time.

• I'm confused why would anyone read these books (this and the Bourbaki set theory book)? Is it to try and learn these topics? There are newer, better, much cleaner expositions which also take into consideration the decades between Hilbert and us. Is it for historical value, in that case you should probably be proficient with the current introductory approaches to logic, and probably somewhat familiar with the history of development of logic and mathematics in the early 20th century. – Asaf Karagila Jan 27 '14 at 17:36
• @Asaf Karagila - I partially disagree with you. You are right in saying that they are not the good "textbooks" to start with, by I like (trying) to understand how current "mainstream" science (i.e. normal science - ref.T.Kuhn, The Structure of Scientific Revolutions) became what is today (and which blind avenues were lost in this process) ... But I confirm again that I will read your future bestselling textbook with great attention. – Mauro ALLEGRANZA Jan 27 '14 at 20:41
• @Mauro: If you want to learn about the development of science to what it is today, then you should definitely know what science is today. This way you can "foresee" the past mistakes or the preludes to great revolutions and discoveries. You're only making my point stronger. Learning logic from Hilbert (or god forbid, set theory from Bourbaki) is not wise. There are newer, better, cleaner treatments of logic that will help you understand today's jargon while you're at it. Learning about the history of the development of logic and set theory, you should know logic and set theory first. – Asaf Karagila Jan 27 '14 at 20:50
• @Asaf - You are right, of course. I'm "projecting" my interests on the OP's questions, and this is a mistake. – Mauro ALLEGRANZA Jan 28 '14 at 7:22

I think that you must take into account that David Hilbert's Principles of Mathematical Logic is an old book (the first edition was : David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik (1928)).

I think also that Bourbaki's text is not a good point to start with math log.

So said, your idea that the definition of well-formed logical expression can be best presented as a formation tree is perfectly sound; see Herbert Enderton, A Mathematical Introduction to Logic (2n ed - 2001) : page 17.

About "the precise procedure : how a general logical expression cab be brought into a certain normal form (conjunction of disjunction)", in propositional logic you can use truth-tables :

each line of the table which comes out $T$ will yield one of the basic conjunctions of the disjunctive normal form, where a basic conjunction is a conjunction with no repetition of a propositional letter (if that letter has $T$ in that line) or of the negation of propositional letters (if that letter has $F$ in that line).

This is an effective procedure (of course, with formulae with more than few propositional letters, the number of rows in the truth-table becomes practically intractable).

• ：Recently I have consulted some books about first-order logic , especially，two books : Herbert Enderton, A Mathematical Introduction to Logic you have suggested; Raymond M smullyan ,first-order logic .I refered to chapters about propositional logic of the two books.I found that the presenation of the former book was very friendly.However,the book written bu Raymond was a little difficult to read but written with rigorous and elegant presenation. the definition of notion formula (or wff) satisfied me but some other questions raised when reading the book of smullyan – Russell Thomas Feb 19 '14 at 5:35
• ：Raymond M smullyan, frist-order logic .page9: – Russell Thomas Feb 19 '14 at 5:38
• :(when defining the formation tree for formula X ): the points of unorder dyadic tree are occurences of formulas such that the origin point be (occurence of)X..... could we define the term "occurence" ? I tried to understand the "occurence" like that, formation tree defined as a collection of one unordered dyadic tree together with a mapping from the set S of points in tree into the set of all subformulas of X ,more precisely, "collection" means ordered pair (set of tree,mapping).I do not know whether the understanding will be fine. – Russell Thomas Feb 19 '14 at 5:50
• :Raymond M smullyan, frist-order logic .page 10 ......when proving that an interpretation V0 can be extended unique boolean valuation ,I do not know the specific process about "It is easily verified by induction on the degree of X that there exists one and only one way....." Dear Mauro, how the induction proof works? – Russell Thomas Feb 19 '14 at 5:59
• @Russell Thomas - I like Smullyan's book! Dyadic tree because each nodes that branches has exactly two successors [page 4 : but we must read "at most", see page 9 : the case of "negation"]. Occurrence because a single formula may occur more than one time in the tree. Unordered, but then [page 3] we order it, because we have "levels" and each level can be "inspected" from (e.g) left to right [page 4]: this is useful for induction. Finally : YES, you map the subformula on the nodes of the tree, starting from prop letetrs in the leafs and ending with the complete formula in the root. – Mauro ALLEGRANZA Feb 19 '14 at 8:41