Re: Can propositions be classified into type-n?

On Apr 11, 10:31 am, Mitch <maha...@xxxxxxxxx> wrote:
On Apr 7, 2:35 pm, sip...@xxxxxxxxx wrote:

Given that propositional calculus deals with propositions, can the
propositions be classified into any in Chomsky hierarchy? Aren't
propositions generative grammars?

Items that can be placed in the Chomsky hierarchy are languages (which
are sets of strings, usually defined using a grammar or machine).

Propositional calculus is a computational mechanism for determining
truth. It is usually presented with a syntax (a grammar) that is
fairly simple (variables, and, or not, true false, and parens), where
the parens or implicit precedence of operators require a context-free
grammar.

The language (syntax rules) of PC is context free.

So particular propositions cannot really be placed in the Chomsky
hierarchy, but a given logic (like propositional calculus) has a
syntax that can be placed there.

The importance of PC is not in its language but in the truth functions
it can describe.

Mitch

Thanks for the helping me with so many of my confusions. Please pardon
my
muddled thoughts, (owing to my lack of understanding and sub-normal
intelligence)
which arose from the statement:
-------------------------------
A first-order theory consists of a set of axioms (usually finite or
recursively enumerable) and the statements deducible from them given
the underlying deducibility relation.
(from Wikipedia)
-------------------------------
I understood FOL to consist of
1. the axioms - which can be classified into the hierarchy
2. the rules - which allow generation of new truths

Given these, would all the statements that belong to such a set
(axioms + new truths)
fall into a particular classification?

hierarchy, but a given logic (like propositional calculus) has a
syntax that can be placed there.
Did you mean that
E#1. the computers are able parse the rules behind them (e.g., many
expert
systems are built based on propositions) and hence the rules are CFLs?
E#2. the complete language cannot be classified into hierarchy

The importance of PC is not in its language but in the truth functions
it can describe.
When I discussed the E#2 with another person, I was told I am talking
of
undecidability. Again from Wikipedia:

-------------------------------
Unlike the propositional logic, first-order logic is undecidable,
provided that the language has at least one predicate of valence at
least 2 other than equality. This means that there is no decision
procedure that correctly determines whether an arbitrary formula is
valid. Because there is a Turing machine as described above, the
undecidability is related to the unsolvability of the Halting problem:
there is no algorithm which determines after a finite number of steps
whether the Turing machine will ever halt for a given sentence as its
input, hence whether the sentence is provable. This result was
established independently by Church and Turing.
-------------------------------

Now, what about propositional logic?
From a very confused mind
-sip
.

Relevant Pages

  • Re: Godels comments about the "true reason" for incompleteness
    ... why not formally admit propositions ... arbitrary Q. Obviously there is an implied quantification over Q, ... letters of the object language). ... refutable in PA and as confirmed by the supposed undecidability of S. ...
    (sci.logic)
  • Re: Choices Choices
    ... this idea in the rather handy "hierarchy of propositions" which is ... It treat witnesses like cameras. ... the man in the red shirt stab the victim with a knife". ...
    (talk.origins)
  • Re: Multiple-Attribute Keys and 1NF
    ... propositions that state "'Green and yellow' contains 'Green'" ... name--the attribute names correspond to free variables in a predicate: ... The person named Brian speaks the language English ...
    (comp.databases.theory)
  • Re: identity...... Was: The wisdom of the object mentors
    ... // this is it's implementation/mapping from a hidden domain of {int x int} ... I'd say that the set of all propositions is language defined behavior or ... polymorphism to me is the substitution of a different ...
    (comp.object)
  • Re: Multiple-Attribute Keys and 1NF
    ... propositions that state "'Green and yellow' contains 'Green'" ... name--the attribute names correspond to free variables in a predicate: ... The person named Jim speaks the language English ...
    (comp.databases.theory)