2

My logic book defines a logical polynomials as follows:

To define what a tautology is, we first introduce the notion of a logical polynomial over a set of formulas $\scr{E}$. This is an element in the minimal set of formulas that contains $\scr{E}$ and is closed with respect to constructing formulas from shorter formulas using logical connectives.

Question: The book's definition implies that the set of logical polynomials is a subset of $\scr{E}$, yet the set of logical polynomials is also defined to include all the elements of $\scr{E}$. Thus, $\scr{E}$ is a subset of the set of logical polynomials. Wouldn't that mean that the set of logical polynomials is equal to $\scr{E}$ ?

Thank you

Amr
  • 20,030
  • 1
    I'd like to know why my question was downvoted so that I could improve it if needs improvement. – Amr Mar 05 '14 at 00:27
  • Doesn't the paragraph you quoted only define the notion of a logical polynomial? You'll need to give us your book's definition of a tautology too before this question is self-contained. – Joshua Pepper Mar 05 '14 at 00:28
  • @JoshuaPepper Right. The question needs editing – Amr Mar 05 '14 at 00:29
  • @joshuapepper Is it clear now – Amr Mar 05 '14 at 00:31
  • So, I still don't think you've given us quite enough information, but one of your assertions is false. The set of logical polynomials is not defined to be a subset of $\scr{E}$, but a subset of some larger set containing $\scr{E}$ that is minimal with respect to some chosen property. Your textbook doesn't seem to give this larger set a name. – Joshua Pepper Mar 05 '14 at 00:33
  • @JoshuaPepper Why? The book says: "This is an element in the minimal set of formulas ...." (This refers to logical polynomial). Thus, all logical polynomials are formulas – Amr Mar 05 '14 at 00:36
  • Actually, I think I understand the root of your mistake, it's in the parsing of the second sentence of the definition. You should read it as follows: "This is an element in (the minimal set of formulas that contains... )." – Joshua Pepper Mar 05 '14 at 00:36
  • It is the minimal set of formulas that contains $\scr{E}$, not the logical polynomial. – Joshua Pepper Mar 05 '14 at 00:37
  • @JoshuaPepper Unfortunately, I don't get it. I don't see how the book's definition (the way it is stated) doesn't imply that all logical polynomials are formulas – Amr Mar 05 '14 at 00:41
  • @JoshuaPepper Thanks for your help, anyways. – Amr Mar 05 '14 at 00:42
  • 1
    Let me see if I can make this clear. You start with a set $\scr{E}$. You define a new, larger set of formulas, denoted $B$, to contain $\scr{E}$, and to be closed w.r.t. logical connectives. You then define a logical polynomial to be a formula in $B$. Thus, your logical polynomial is not necessarily in $\scr{E}$ - it could be in $B\backslash \scr{E}$. So, your assertion that "the set of logical polynomials is a subset of $\scr{E}$" is false. – Joshua Pepper Mar 05 '14 at 00:45

1 Answers1

2

In the construction of your textbook, you will start from a set $\scr{E}$ of formulas.

Logical polynomials over $\scr{E}$ are all (finite) "combinations" of formulas in $\scr{E}$ that you can build up using logical connectives.

This means that, if $A, B \in \scr{E}$, then $\lnot A$, $A \lor B$, $\lnot (A \land \lnot B)$, and so on, are logical polynomials over $\scr{E}$.

Of course, also $A$ and $B$ are; so, trivially, $\scr{E}$ is included into the set of logical polynomials over $\scr{E}$; but, as said by @Joshua Pepper, is not necessarily true that, if $A, B \in \scr{E}$, then e.g. $A \lor B$ was already in $\scr{E}$.

In other words, it is not true that

the definition implies that the set of logical polynomials is a subset of $\scr{E}$.

Mauro ALLEGRANZA
  • 94,169