Computing philosophy
- An approach in engineering and computing philosophy: the pw server
4. Propositional logic problems
Before discussing points concerning the default predicate logic for the pwSrv, I want to give some current issues of the 2nd level problems on the client side. These are not new ones, but perhaps new is that it is addressing 'real live' sentences over a wide area of natural language and scientific topics.
When we try to use the propositional logic of the natural language (in pw SEs) on upgrade a pw session to the second level, or inside the second level, we face some problems of which some are now outlined.
Natural language isn't transferable directly or automatically into a logical form. Natural language as it evolved, has many qualities for its usage as it is, but this doesn't match 100% with a formal language focused on logic. Examples for some of these problems of natural language vs. logics(1) are:
1: in natural language we say 'if x then y' and this closure holds in classical formal logic true in any cases, except if x is true and y is false. But in natural language we use the implication normally in another way. If the antecedence shows up false, then the whole implication will be obsolete. We normally take back the whole argument 'if x then y', if we know x is false. But this would lead in formal logics to non-truth-functionality, e.g., transferred this behavior to a formal logic, the result of any evaluation of a logical formula including a material implication will any more lead necessarily to a certain truth value, because the formula x -> y in some cases would vanish. What should be done with that? There are many possibilities and there is a whole special direction in logics (relevance logics) addressing this and other problems with the material implication. But solving some of these they are running into new problems (more below).
2: some natural language sentences have to be rewritten for formal logics. 'The bus has an accident because the bus driver was drunken' cannot be formalized as b -> a (when the bus driver is drunken -> the bus has an accident) as this must not be every time the case, so has to be rewritten another way. Perhaps you rewrite the closure using probabilities like 'if a driver is drunken then the probability to have an accident is far (or 90%) bigger than...' and so... 'the bus had an accident...'. But can we state exact figures? If not, would that still be a 'correct' closure? On which base can we give probabilities, if we don't know the causal chain leading to the accident? Shell we make empirical investigations? Are there better ways of rewriting the closure? ...
3: the 'paradoxes of implication':
some logics tried to overcome some strange results of the standard propositional 2valued logic, mainly connected with implication and negation, like (a -> (b ->a) being a tautology. If You try to resolve it with many valued logics it seems inevitable, that You change the behavior of some formulas as You need, e.g. this example not be a tautology any more, but You get other changes inside your logic that are even worse than what You wanted to prevent....
The problem is thus, that everyone has the decision which logic(s) to choose in pw. pw assumes for these problems that the logics rules are set for the upgrade to the 2nd level, but even assuming that these rules can be given in a necessary general way, either non-standard logic version will produce some problems in the long run. But on the other hand, to define a default logic to be used for pw users, isn't a philosophically possible solution ,as this topic is part of the whole discussion.
We have then to face further problems with contexts, ambiguous words and other natural language problems, which come really into play with the predicate logic (on the server). The problem, not only with many valued logics is, that they solve one problem but introduce new ones: intuitive valid tautologies are no longer valid, others occur, the system might get inconsistent according the natural 'interpretation' and so on. One further example for this.
4. Resolution of problems using many-valued logics generates new ones:
Given a third truth value like 'undecidable' with the truth table value definition for negating an undecidable sentence leading still to undecidability, which seems reasonable. You may want to use this third value to resolve example 1, e.g. False -> x leads to undecidability (x may be any truth value). The formula gets true in case of True -> True and False in case of True -> False.
Normally we assume that p u ~p should lead always to False. But with p being undecidable, this is not a classical negation of a tautology any more as the resulting truth-value is 'undecidable' when p is evaluated as undecidable. It seems that there is some inherent trade of between a 'pure' logic, representing and abstracting only the logical part of natural language and a 'natural' logic, which tries to go close to natural language rules, but loses then reasonable parts of logic. If this must be the case, is one important point of evaluation in the pw project. For these topics see the links below to Rescher and Bremer.
Recently I'm more convinced to go back to 2 valued logics. On many issues on classical propositional logics versus natural language there may be interpretive solutions so we need not to give up 2nd order logic basics. I don’t want to discuss these topics in depth here, but the examples 1 or 3 are topics that should be resolved in some way, perhaps not with a new truth-value but otherwise. But how ? ...
It seems that finding at least one good logic will be hard work (if possible). And then we have further face the problem, that some areas of scientific discussion might afford another logic and then we have the possibility in pw to have sentences that cross these boundaries of logics(2). Which truth values can such sentences have?
pw allows already in the first level to cross the boundaries of logical 'types', e.g. for example between definitions and assertions (e.g. DW and WW). This makes the stuff discussed above even more complicated as for the second level these types remain, vanish or there will be new defined types by the user. In level1 computation you can implement and evaluate such closures by intuition. For the next they should be formally defined (if possible, or not, if You for example adhere to Mr. Hume to not be able to make a closure from something existing to something that should be the case...).
In the last part we will discuss these language issues along with new possibilities of NLP(natural language processing ). But already here I would like to mention, that we cannot assume to get more than a support by NLP on solving these problems. NLP will perhaps partly automate translations of natural language into logic but not fully.
My standpoint is, that natural language is (or will show up in the future to be, more) an empirical problem. But hard natural science on this topic is still future (and will be perhaps for the next x0 years or so ...). So we cannot want pw to solve this for us, but we can await some enlightenment by trying out some session versions with different logics defined. Hey, doing some investigation is still fun...I'm working on that issue...
One can also present this discussion from the philosophical point of view: is there a middle way between early and late Wittgenstein?
A connection to predicate logics is the point of sentences on a meta-level(3), e.g. senteces refering to parts/words of other sentences not in the object-level of the part, but in a level of this part beeing a sign (there were seven dwarfs vs. the word 'seven' has four distinct signs). Do we have with Tarski to introduce for every such level a separate logical language? What about the idea of semantically closed languages as in paraconsistent logics (see Bremer below)? Isn't pw itself necessarily semantically closed as some of its sentences can revise the computation ‘algorithms’ of all sentences in the next step? S317 starts to discuss this topic in a more formal way and it seems, as such proceeding is in simple cases formally possible. The discussion of the concept of semantic closure has still to be done in S317!
In natural language the (meta)levels of sentences have no indexes. They cannot, as we don't even know or think about, what should be the level1 objects to talk about. On the other hand, assertions transferred from natural language to propositional logic doesn't target this problem as this logic excludes the inner part (the meanings of sentences) and focuses only on logical operators. So how can you translate natural language into propositional logic dealing with sentences on meta-levels? And you have to, as propositional logic serves as the base for predicate logic translations!
For now, pw handles such meta-sentences by a short categorization on level1 computing (the MTx) and a semi-formal definition inside the TS files choosing an approach to define a meta level sentence TS just relative (!) to another TS, e.g. there are no defined meta-levels beforehand. The top meta-language will be always the English natural language.
Finally, the propositional logic is the base (logic) for the behavior of some or many predicate logics laws or features (in case also on a meta-level language by arguing for or define a special behavior of a logics base !). So if we'll argue in the next chapter for or against some characteristics of a standard or 'default' predicate logic to use on pwSrv side, we have to keep in mind the propositional logics basics a user might choose in his session on client side. In short: we need to create a predicate logic general enough, to be able to handle as many propositional logics variants, as we think it should be able to.
Links:
N. Rescher: 'Many valued logic', 1969, McGraw-Hill, USA
M. Bremer: 'An introduction to Paraconsistent Logics', Europäischer Verlag der Wissenschaften, Frankfurt am Main, 2005
PWR56 and 59 of pw projects rules (not in English yet, only German...)
5. Predicate logic
Now it is assumed to have for level 3 a FOL version(1) (first order logic), presumably with equality, optionally axiomatized. (NB: a plain axiomatized logic is not helpful for our purposes as we always will need the truth table definitions to compute the consistency of the sentences. Otherwise we would need to reconstruct the truth tables first from the axiomatization, and it is not sure that this can be always done ...). FOL is simpler than higher order logics (HOL) and thus its features are better computable or provable. Many terms in HOL can be rewritten in FOL.
On the other hand there might be limitations in the expressiveness of FOL(2), so some natural language reasoning possibly cannot be correctly encoded into FOL. An example is the reachability in directed graphs, that has to be expressed in existential second order logic (quantifying over predicate symbols) as discussed in Huth/Ryan on page 138f. (see Links below).
The question concerning a/the model theory to use is still open for discussion. Other topics, as the usage of lambda calculus and semantic representation are discussed in the last chapter NLP.
As discussed above also the predicated logic(s) can be 2valued and/or many valued, as the pw users decides to use for his session. We have to keep this in mind for further discussion. In general the user will be able to choose his logic(s) properties, as the PWR will allow him to. The default pwSrv predicate logic will not be a special one, but one which can handle all or most of the cases chosen, will be expandable to special cases by the users and if not expandable, replaced by another Predicate logic as the user needs. So we have to give a syntax for such a generic Predicate logic and for possible variants (see more requirements below).
So the next question will be concerning the general syntax of our Predicate logic.
First we give some more requirements(3). These are not fixed yet but part of further discussion. Further on it might be, that not all requirements are possible to fulfill the same time, e.g. there might be trade offs. So we should provide a final selection procedure with some measures and weighting. Here we go:
1 easy readability, e.g. it should not deviate much from classical logics syntaxes
2 the default logic should be given in only one format, e.g. human and machine readability should be given both in one format (in case we can do internal transformations if it will be easier to process..)
3 define the entities to be able to represent our sentences and choose such appropriate logics (individual constants, logical const., arity of predicates, ...)
4 use existing standards as possible, and extent or combine them as needed
5 are there existing interfaces to other standards (logical formats) and tools that can be used for translations?
6 the extendibility of the FOL for variants
7 the default Predicate logic should adhere or be close to the default pw propositional logics
8 many valued logics variants (non-truth functional, ...too) must be possible, but which variants?
9 is support of ontologies needed?
10 build in objects or types needed or desirable?
11 which syntax type of logic we prefer?: classical Gentzen format isn't good for computers, also classical quantifier signs normally aren't available ...
12 is there also an axiomatization available for the given logic (if needed)?
13 are there easy formatings supported, like capital/lower letters distinctions?
14 is there a meta-language defined?
15 are extensions for 4th level possible?: modal operators, higher order logics,...
16 languages, tools and grammars to define the logics for a program?: EBNF, context free grammars, ...
17 ...other?
The list should not be seen as final. Point 16 will be discussed now a little bit:
In linguistics and computer science, languages are classified into different types, which is done by the grammar that can define them (Chomsky grammars). The languages are of different complexity. We'll need (presumably) the so-called context free grammars (to be able to handle bracketing and to be able to use a parser generator....). The standard syntax to define formal languages is the so-called Extended Backus-Naur Form (EBNF), also standardized in the meantime (ISO). Given such a language definition in EBNF there are parser generators (like AntLR) that can verify the correctness of a language expression by generating a language parser for us.
It is highly advisable to be able to use those techniques than building all from scratch. If we can handle our Predicate logics this way, has to be evaluated. They can have features that make them parsable only with context sensitive grammars...In case, are there ways out?: Predicate logic Prenex Normal form, Polish notation (in case internal conversion of given formulas before parsing?), 'Mildly Context-Sensitive Grammar Formalisms' with NLP,...to generate Parse trees. In short: is there a proved generic EBNF for 'any' FOL(4) or a prove that such EBNF cannot exist? More on those topics also in the NLP chapter.
Horn-Schema / Normalization(5) Syntax:
Normal logical programs process the formulas in a so-called normalized form; the 'optimal' one for performance is a Horn Schema. We can use this only when the user chooses only one classical 2valued logic. A generic Horn-schema for 'any' many-valued logic doesn't exist (indeed, as far as I could get information on this topic, there isn't even a known way to transfer propositional mvLogics into a normal form if You don't know beforehand the resulting truth tables for each formula given).
There are lots of logics outside there. Some buzz words are RDF, Conceptual Graphs (CG), Common Logic, linear logics, relevance logics, epistemic logics, paraconsistent logics and so on. Some might be interesting but will lack some essential features for us or are focused on different features than our targets. In the next section I'll present a first starting discussion of some candidate logics.
A) KIF
The Knowledge Interchange Format invented by Mike Genereseth, is readable for both humans and computers. It has features to fulfill point 15, e.g. its syntax is fit for computing. It lacks some ontology 'overhead' as conceptual graphs (CG) but it get never standardized (how far from a standard, is a point of discussion by the specialists). My favorite until now.
B) RDF
The current Internet standard. But it is build on XML, which is not really readable for human readers. There are different variants of different expressiveness to choose from. One can assume that there are a lots of tools for this logic. There is also an ontologies extension (OWL) that is targeted on classifying web pages (if we decide to use or suppport such extension to ontologies or types).
C) Logic with NLP
There are approaches of combinations of NLP with logics. The idea is that NLP first parses the sentences, build an internal tree representation according it's grammar rules and from this converts the tree into a given logic notation like KIF. This is an interesting alternative to a plain logical approach. More on this in the NLP chapter.
D) a standard classical logic - manual approach
Take one of the classical 2valued logics that is common known, axiomatized and investigated. Take one that is not too bad to be moved to a computer representable format (e.g., if the negation sign is some crude one take the ~ if not used otherwise) and go on manually if there are no appropriate tools out there for this.
Links:
John Truss: 'Discrete mathematics for computer scientists', Addison-Wesley, 1999
JTP and KIF
http://www.ksl.stanford.edu/software/JTP/#intro
EBNF of predicate logics
Conceptual graphs
search for 'Tistle': a Cat. Grammar deductions engine (belongs more to the chapter NLP below)
M. Huth, M.Ryan: 'Logic in Computing science', Cambridge University Press, 2004, UK
search for related projects: 'sneps3', ...
previous page
next page (4)