逻辑、计算和博弈 (12).pdf

《逻辑、计算和博弈 (12).pdf》由会员分享，可在线阅读，更多相关《逻辑、计算和博弈 (12).pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Against All Odds:When Logic Meets ProbabilityAbstract.This paper is a light walk along interfaces between logic andprobability,triggered by a chance encounter with Ed Brinksma.It is nota research paper,or a literature survey,but a pointer to issues.I discussboth direct combinations of logic and prob

2、ability and structured ways inwhich logic can be seen as a qualitative version of probability theory.Iend by sketching a concrete program for classifying qualitative scenariosthat would lend themselves to simple logical reasoning methods,but Ialso acknowledge a challenge:the unreasonable effective o

3、f probability.1IntroductionWhen I met Ed Brinksma recently in the“Glazen Zaal”in Den Haag,old mem-ories came back of a very special student in Groningen,clearly a cut above thecrowd,who wrote a pioneering thesis on interpolation in dynamic logic(still alive topic even today),and who turned my lectur

4、e notes on mathematical logicinto a highly effective didactic manual that attracted many students over theyears.I have followed Eds career ever since,and find traces of encounters in myarchive,such as our contributions printed side by side in a volume of the popularmagazine“De Automatiseringsgids”in

5、 1993,when,to some,computer scienceseemed to be in crisis,just as it was making a giant leap toward transformingour world.And there is of course his blazing trajectory as a Rector at the Uni-versity of Twente,which I followed in the press,with,I confess,a tinge of pridein having contributed my bit t

6、o this higher flight.But our conversation was about something else,namely,Eds ideas on reso-nance as a basis for communication,rather than elaborate logical models.Thisstruck me since I had been thinking on similar lines,inspired by an introductionto cognitive science,32,that made a distinction betw

7、een two aspects of com-munication:transfer of message content,and resonance between the actors.The latter seems a precondition for the former to succeed.I have thought a lot about this distinction,which seems real to me.I alwaystell my students who get a job interview that now is not the time to do

8、still moretransfer of information about how clever they are.It is not about touting theirlatest papers,and their brilliant new projects,but rather,about establishingresonance with a committee trying to decide whether this(perhaps too)cleveryoung person is someone they would like to have as a colleag

9、ue.2Johan van BenthemBut how to model resonance,real as it is?I can list many topics in my environ-ment of logics of agency and philosophy of action that go a bit in this direction,such as common knowledge,opinion aggregation,or network dynamics,but theynever seem to jell into one coherent picture,s

10、o all I have are accumulated notesin closed drawers.Now Ed seemed to think(it was a noisy reception,resonanceby eye contact was easier than transfer)that all this presented a challenge tologic,and that we would need probabilistic models.So,here is my topic.2Logic and probabilityThese are days of ten

11、sion,or armed neutrality,between logical and statisticalapproaches to communication,language,and cognition.On the classical logicalmodel of deliberative agents that communicate or interact,reasoning plays animportant role,including complex theory of mind:what I believe about yourbeliefs about my bel

12、iefs,and upward.Much of my own work has been in thisline,34,36,and the resulting logics of agency also those by colleagues incomputer science are ever more sophisticated,but also,I am unhappy to say:ever more complex.It becomes a miracle that human interaction works at all.So,here is an alternative

13、approach.We look for simple statistical patterns in humanlanguage and interaction,and explain observed behavior in terms of these.Thiscontrast is sometimes cast in terms of high rationality versus low rationality,30.Simple statistical models often explain emergent stable patterns in behaviorjust as

14、well as complex logical theories with highly baroque sets of notions.This is not just the usual sniping between competing academic disciplines.These issues are also potentially radical in their consequences for our daily lives.Take ethics and how we should behave.Classical ethical theory is reason-b

15、ased,and the reasons why we engage in moral behavior toward others are cementedby complex logical and game-theoretic scenarios,a form of high rationality inthe normative realm bequeathed to us by great minds like Immanuel Kant orJohn Rawls.Of course,there are people who do not play by the rules:crim

16、inals,or profiteers that play the system.But on the whole,society is in equilibrium.Now consider a low-rationality alternative without deep reasoning.There justhappen to be two types of humans:predators(who do not follow the rules),andprey(those who do).Then a simple biological model for their encou

17、nters leadsto an evolutionary game with probabilistic equilibria having stable percentagesof predators and prey in the long run.Thus,stability has been explained in muchsimpler,and also less fragile,terms.And incidentally,those biological models dowork on simple resonance(whether positive or negativ

18、e)in terms of what thetwo types of beast do in their encounters.The mathematics of the low rationality approach is statistics,dynamicalsystems,and evolutionary rather than classical game theory.And so a questionarises,at least for someone like me.Is there any place left for logic?Well,theinterface o

19、f logic and dynamical systems is an exciting new topic with old rootsthat I have discussed elsewhere,37,and we are only at the beginning,20.Against All Odds:When Logic Meets Probability3But in this paper,I want to strike out in an even more general direction,focusing on just one aspect of dynamical

20、systems.The rest of this little piecewill try to paint a light picture of actual encounters between logic and probability,not in hostile or plaintive mode,but as serious paradigms treated on a par.3A shared historyQualitative deductive logic produces absolute certainty,but in a limited range,with it

21、s greatest triumphs perhaps in mathematics or automated deduction.Incontrast,quantitative probability produces less certain conclusions,but it appliesto all of life around us.But this way of phrasing the divide may create a spurioustension.It is important to realize that there is a good deal of harm

22、ony as well,and this section provides a few pointers.Clearly,in our ordinary reasoning,probabilistic and logical steps proceed intandem.One takes over where the other seems less appropriate.And indeed,this harmony can also be observed in the history of logic.Great logicians of the19th century did no

23、t make sharp distinctions here.John Stuart Mills highlyinfluential“System of Logic”presents both logical and probabilistic rules forgood reasoning,and it seems odd to say that he was confused between logic andprobability theory,or between logic and methodology.Bernard Bolzanos“Wis-senschaftslehre”,a

24、nother classical gem,even says that the task of logic is to chartall natural styles of human reasoning,which can be task-dependent,and he in-cludes probabilistic reasoning among these.Similar views occur with CharlesSaunders Peirce on the entanglement of deduction,induction(more probabilis-tic),and

25、abduction(reasoning to the best explanation).And here is a title whichsays it all:George Booles“An Investigation of the Laws of Thought on Whichare Founded the Mathematical Theories of Logic and Probabilities”.It is onlywith the birth of modern mathematical logic in Freges“Begriffsschrift”thatprobab

26、ility drops out,presumably because probability spaces live somewhereinside the set-theoretic universe,and thus have been dealt with at the strato-spheric abstraction level of the foundations of mathematics.But even in a beginning modern logic course,numbers and probability comein naturally on top of

27、 the base structure.We normally give binary judgments ofvalidity and non-validity for proposed inference patterns,say,B,A B=A(valid)versus A,A B=B(invalid)But there is more:among the non-validities,some seem worse than others.Forinstance,the inference A,A B=B gets things wrong in half of thecases,bu

28、t the invalid AB=(AB)only in one of three cases.This is notyet probability,but it is natural numerical structure right inside logic.This link continues into probability theory.A probabilistic axiom such asP(A B)=P(A)+P(B)P(A B)looks very much like propositional logic continued by other means.In fact

29、,similar comments can be made about the simple almost propositionalreasoning leading toward something as ubiquitous as Bayes Rule:4Johan van BenthemP(A|B)=(P(B|A)P(A)/P(B)if P(B)6=0Not surprisingly then,one of my favorite textbooks as a student(not on theofficial curriculum,but not on the Index eith

30、er)was Suppes“Introduction toLogic”from the 1950s which also included quantitative topics as a matter ofcourse.It offers not just Venn Diagrams for syllogisms,but also Venn diagramswith numerical information about their regions not just deductive logic,butalso probability.And the same combinations c

31、an be seen in the creative workof major philosophical logicians.Carnap created inductive logic,4,Hintikkadeveloped numerical confirmation theory,15,and Lewis moved happily fromqualitative theories of conditionals to the principles of probabilistic update overtime,25.This combination of interests is

32、just natural,it will not go away.With this in mind,lets now explore other encounters of logic and probability.4Logical foundations of probabilityHere is an obvious first encounter that still may still need stating.One placewhere logic and probability can meet without conflict is at a meta-level,in t

33、hefoundations of probability.Theorems in probability theory have standard math-ematical proofs,and so there is a deductive logic to the theory of non-deductivereasoning.In this sense,Frege and the other founding fathers of mathematicallogic were right.But there are also more intimate foundational co

34、ntacts.Consider our national classic,Johan De Witts“Waerdije”,7,the foundingdocument of modern insurance mathematics.At the start,the author gives anexplanation of the laws of probability which he may have learnt from a pam-phlet by Christiaan Huygens in terms of rational betting behavior.The bettin

35、gconnection is standard by now,and a famous version is the Dutch Book The-orem,19.This says that obeying the standard laws of probability is the onlyguarantee against having a Dutch book made against you:that is,a system ofbets that is systematically unfavorable to you.(This link between probability

36、theory and financial gain is a pioneering instance of the valorization so prizedby our university leaders today.)There is more to be found in this line,witness18 on justifications for qualitative probability.Indeed,I believe that one canalso profitably give Dutch Book theorems for laws of logic,in t

37、erms of avoidingunsuccessful planning,but this theme would take me too far here.And there is a deeper connection with logic as well.Pioneers of modernprobability,such as De Finetti,6,believed that probability rests on a qualitativenotion,namely,a comparative binary connective between propositions:A

38、BB is more probable(more likely to be true)than ADe Finetti then proceeded to give axioms for this notion that allow for qualitativereasoning.In addition to obvious properties of a reflexive transitive order,theseinclude intuitive laws of probability such as(with for set complement)A B if and only i

39、f(A B)(B A)Against All Odds:When Logic Meets Probability5From these,other natural principles follow,such as the propositional monotonic-ity law saying that A B implies A D B C.The aim of this approach was a set of intuitive qualitative laws of reasoning thatwould force the existence of a standard pr

40、obability measure P such thatA B iffP(A)P(B),for all propositions A,BEventually,de Finettis set of principles did not work out,as was shown in afamous technical counterexample in 21,a paper which also proposed necessaryand sufficient qualitative principles for probabilistic representation.An accessi

41、blemodern explanation of these matters can be found in 16.Later on,Dana Scott gave a better-known streamlined version of necessaryand sufficient logical principles for probability,29,but still,their very complex-ity suggested by and large that this approach was a dead end.Much better tojust calculat

42、e with probability values directly,and drop logical purism!However,De Finettis paradigm is not a closed chapter at the interface oflogic and probability,and we will return to it in Sections 6 and 7 below.5Probabilistic patterns in logicInstead of looking for logical foundations for probability,we ca

43、n also turn thetables,and look for probabilistic patterns in the foundations of logic.Here area few strands that belong to this direction.By the 1960s,the properties of first-order predicate logic,the logicians toolpar excellence,had pretty much been discovered and in 1969,Lindstr omsTheorem,26,even

44、 stated a precise sense in which we had found a complete setthat captured the essence of this system.History seemed at its end.But in the 1970s,a striking discovery was the Zero-One Law,9,and inde-pendently a Soviet team,which says the following.Take any first-order formulaA,and compute the probabil

45、ity Pn(A)of its being true on finite models of sizen(there are only finitely many such models up to isomorphism).As n goes toinfinity,the probability of Pn(A)will go toward either 1 or 0.It is even decidablefrom the shape of the assertion A which of the two cases obtains.Many furthersuch results hav

46、e been discovered.In other words,underneath qualitative logicalmodel theory,deep global statistical regularities have come to light and in thatsense,we probably do not know the meta-theory of classical logic at all yet.Other examples of significant statistical behavior have been discovered astheorem

47、 provers started producing logs and outputs,making a vast store of ex-perience available in how logical systems actually perform.One striking discoverywere physical phase transitions in computation time for propositional satisfi-ability problems,27:the average time toward an answer“satisfiable”or“no

48、tsatisfiability”first increases with input size qua number of formulas,eventuallyit decreases,but the change is sharp for certain input sizes.These experimentshave been replicated,also with other measures of input complexity,and thephenomenon seems robust:complexity of performance of logical systems

49、 has6Johan van Benthemsignificant cliffs.Much progress has been made with analytical or logical expla-nations,but I am not aware of any definitive theory.Even so,we may concludethat the bulk behavior of proof systems,too,seems to hide important statisticalstructure for whose study we need to combine

50、 logic and probability.My final example goes further,but is also more speculative.The great meta-theorems of classical logic all have a limitative character.Basic problems areundefinable,non-axiomatizable,or undecidable.But how bad is this news really?The undecidability of first-order logic says tha