精华内容
下载资源
问答
  • 如果backtrader是一个人的话...作者把cerebro称做backtrader的基石,并且设计实现了下面的四个功能,我将结合自己的理解,翻译下作者的官方文档。 1 . 添加运行回测或者实盘需要的元素 ​ 在添加任何元素之前,都需要创

    如果backtrader是一个人的话?

    最近受到科学哲学的影响比较大,除了归纳和推理之外,我们还可以使用类比。如果我们把backtrader看作一个人的话,我们上一讲分享的__strategy__和__cerebro__就如同我们的左右脑、意识和潜意识一样,决定我们的大部分行动;

    cerebro能实现什么功能?

    作者把cerebro称做backtrader的基石,并且设计实现了下面的四个功能,我将结合自己的理解,翻译下作者的官方文档。

    1 . 添加运行回测或者实盘需要的元素

    ​ 在添加任何元素之前,都需要创建一个cerebro,即把cerebro类实例化。kwargs是传入的一些参数,这些参数可以查看cerebro,里面有详细的参数的讲解,在代码部分,我把这些参数翻译成大家比较容易理解的语言。

    cerebro = bt.Cerebro(**kwargs)
    # 算了,我还是把这些参数的说明放到文章的末尾吧,要不然,几百行的解释,不容易让大家把握住核心点。
    
    1. 添加数据(feed)

      # 数据有很多种,一般使用add加入进去,如下面是我常用的方式,先用pandas读取成dataframe,再加入进去,params是回测开始时间和结束时间,可以忽略
      params=dict(fromdate = datetime.datetime(2010, 1, 1),
                      todate = datetime.datetime(2020,3,21))
      df.columns=['datetime','open','close','high','low','volume','openinterest']
      df.index=pd.to_datetime(df['datetime'])
      df=df[['open','high','low','close','volume','openinterest']]
      feed =  bt.feeds.PandasDirectData(dataname=df,**params)
      cerebro.adddata(feed, name = data_name)
      
      # 还有resampledata和replaydatadata的方法,我一般很少再回测中使用,使用哪个周期的数据,直接加载就好了。
      
    2. 添加策略(strategy)

      # 添加策略
      cerebro.addstrategy(MyStrategy, myparam1=value1, myparam2=value2)
      # 实际上,参数可以使用**kwargs传入进去,如
      params = {"short_window":10,
                      "middle_window":150,
                      "long_window":250}
      cerebro.addstrategy(MyStrategy,**params)
      # 添加参数优化的策略
      cerebro.optstrategy(MyStrategy, myparam1=range(10, 20))
      
    3. 添加观察维度(Observer)

      # 添加这三个观察维度,会在画图的时候体现出来,会额外增加两个副图,并在K线图上画出买卖点,如果不用cerebro.plot()功能,可以考虑取消
      cerebro.addobserver(bt.observers.Broker)
      cerebro.addobserver(bt.observers.Trades)
      cerebro.addobserver(bt.observers.BuySell)
      
    4. 添加分析维度(Analyzer)

      # 可以添加analyser,并在分析的时候取出来回测的结果
      cerebro.addanalyzer(bt.analyzers.GrossLeverage, _name='_GrossLeverage')
      cerebro.addanalyzer(bt.analyzers.PositionsValue, _name='_PositionsValue')
      cerebro.addanalyzer(bt.analyzers.Returns, _name='_Returns')
      cerebro.addanalyzer(bt.analyzers.SharpeRatio, _name='_SharpeRatio')
      
    5. 输出数据(Writer)

      cerebro.addwriter(bt.WriterFile, csv=True)
      

      以上五个部分,除了Strategy,作为重点先分享了之外,其他的部分,在后面,还会再详细分享一下如何使用。

    2. 策略的运行(回测、模拟或者实盘)

    # kwargs传入一次就行,在cerebro实例化的时候或者再run的时候都可以
    cerebro.run(**kwargs)
    

    3. 返回运行的结果

    # 如果需要一个返回的结果进行分析,最好使用一个变量,把运行的结果保存到变量中
    result = cerebro.run(**kwargs)
    

    4. 画图

    cerebro.plot()
    
    '''Params:
    
          - ``preload`` (default: ``True``)
    
            Whether to preload the different ``data feeds`` passed to cerebro for
            the Strategies
    
            # preload这个参数默认的是True,就意味着,在回测的时候,默认是先把数据加载之后传给cerebro,在内存中调用,
            # 这个步骤导致的结果就是,加载数据会浪费一部分时间,但是,在回测的时候,速度会快一些,总体上的速度还是有所提高的
            # 所以,建议这个值,使用默认值。
    
          - ``runonce`` (default: ``True``)
    
            Run ``Indicators`` in vectorized mode to speed up the entire system.
            Strategies and Observers will always be run on an event based basis
    
            # 如果runonce设置为True,在计算指标的时候,将会按照向量的方式进行,用向量方式运行,可以加快速度,但是,容易调用未来信息,
            # 更重要的是难以实现复杂的功能,所以,量化框架,少有是用向量化的方式搭建起来的,大部分都是按照事件驱动的方式搭建的。
    
          - ``live`` (default: ``False``)
    
            If no data has reported itself as *live* (via the data's ``islive``
            method but the end user still want to run in ``live`` mode, this
            parameter can be set to true
    
            This will simultaneously deactivate ``preload`` and ``runonce``. It
            will have no effect on memory saving schemes.
    
            # 实盘模式的运行,默认情况是False,意味着,如果我们没有给数据传入"islive"这个方法,默认的就是回测了。
            # 如果把live设置成True了,那么,默认就会不使用preload 和 runonce,这样,一般回测速度就会变慢。
    
          - ``maxcpus`` (default: None -> all available cores)
    
             How many cores to use simultaneously for optimization
            # 优化参数的时候使用的参数,我一般不用这个优化功能,使用的我自己写的多进程回测的模式,优化参数这个地方有bug,有的策略正常,有的策略出错
            # 不建议使用,如果要使用的时候,建议把maxcpus设置成自己电脑的cpu数目减去一,要不然,可能容易死机。
    
          - ``stdstats`` (default: ``True``)
    
            If True default Observers will be added: Broker (Cash and Value),
            Trades and BuySell
    
            # 控制是否会加载observer的参数,默认是True,加载Broker的Cash和Value,Trades and BuySell
            # 我一般默认的都是True,画图的时候用的,我其实可以取消,因为我怎么用cerebro.plot()画出来图形来观察买卖点
    
          - ``oldbuysell`` (default: ``False``)
    
            If ``stdstats`` is ``True`` and observers are getting automatically
            added, this switch controls the main behavior of the ``BuySell``
            observer
    
            - ``False``: use the modern behavior in which the buy / sell signals
              are plotted below / above the low / high prices respectively to avoid
              cluttering the plot
    
            - ``True``: use the deprecated behavior in which the buy / sell signals
              are plotted where the average price of the order executions for the
              given moment in time is. This will of course be on top of an OHLC bar
              or on a Line on Close bar, difficulting the recognition of the plot.
    
            # 如果stdstats设置成True了,那么,oldbuysell的默认值就无关紧要了,都是使用的``BuySell``
    
            # 如果stdstats设置成True了,如果``oldbuysell``是默认值False,画图的时候,买卖点的位置就会画在K线的
            # 最高点和最低点之外,避免画到K线上
    
            # 如果stdstats设置成True了,如果``oldbuysell``是True,就会把买卖信号画在成交时候的平均价的地方,会在K线上
            # 比较难辨认。
    
    
          - ``oldtrades`` (default: ``False``)
    
            If ``stdstats`` is ``True`` and observers are getting automatically
            added, this switch controls the main behavior of the ``Trades``
            observer
    
            - ``False``: use the modern behavior in which trades for all datas are
              plotted with different markers
    
            - ``True``: use the old Trades observer which plots the trades with the
              same markers, differentiating only if they are positive or negative
    
            # 也和画图相关,oldtrades是True的时候,同一方向的交易没有区别,oldtrades是False的时候,
            # 不同的交易使用不同的标记
    
          - ``exactbars`` (default: ``False``)
    
            With the default value each and every value stored in a line is kept in
            memory
    
            Possible values:
              - ``True`` or ``1``: all "lines" objects reduce memory usage to the
                automatically calculated minimum period.
    
                If a Simple Moving Average has a period of 30, the underlying data
                will have always a running buffer of 30 bars to allow the
                calculation of the Simple Moving Average
    
                - This setting will deactivate ``preload`` and ``runonce``
                - Using this setting also deactivates **plotting**
    
              - ``-1``: datafreeds and indicators/operations at strategy level will
                keep all data in memory.
    
                For example: a ``RSI`` internally uses the indicator ``UpDay`` to
                make calculations. This subindicator will not keep all data in
                memory
    
                - This allows to keep ``plotting`` and ``preloading`` active.
    
                - ``runonce`` will be deactivated
    
              - ``-2``: data feeds and indicators kept as attributes of the
                strategy will keep all points in memory.
    
                For example: a ``RSI`` internally uses the indicator ``UpDay`` to
                make calculations. This subindicator will not keep all data in
                memory
    
                If in the ``__init__`` something like
                ``a = self.data.close - self.data.high`` is defined, then ``a``
                will not keep all data in memory
    
                - This allows to keep ``plotting`` and ``preloading`` active.
    
                - ``runonce`` will be deactivated
    
            # 储存多少个K线的数据在记忆中
    
            # 当exactbars的值是True或者是1的时候,只保存满足最小需求的K线的数据,这会取消
            #       preload,runonce,plotting
    
            # 当exactbars的值是-1的时候,数据、指标、运算结果会保存下来,但是指标运算内的中间变量
            #       不会保存,这个会取消掉runonce
    
            # 当exactbars的值是-2的时候,数据、指标、运算结果会保存下来,但是指标内的,指标间的变量,如果没有使用
            # self进行保存,就会消失
    
            # 可以验证下,-2的结果是否是对的
    
            
          - ``objcache`` (default: ``False``)
    
            Experimental option to implement a cache of lines objects and reduce
            the amount of them. Example from UltimateOscillator::
    
              bp = self.data.close - TrueLow(self.data)
              tr = TrueRange(self.data)  # -> creates another TrueLow(self.data)
    
            If this is ``True`` the 2nd ``TrueLow(self.data)`` inside ``TrueRange``
            matches the signature of the one in the ``bp`` calculation. It will be
            reused.
    
            Corner cases may happen in which this drives a line object off its
            minimum period and breaks things and it is therefore disabled.
    
            # 缓存,如果设置成True了,在指标计算的过程中,如果上面已经计算过了,形成了一个line,
            # 下面要用到指标是同样名字的,就不再计算,而是使用上面缓存中的指标
    
          - ``writer`` (default: ``False``)
    
            If set to ``True`` a default WriterFile will be created which will
            print to stdout. It will be added to the strategy (in addition to any
            other writers added by the user code)
    
            # writer 如果设置成True,输出的信息将会保存到一个默认的文件中
            # 没怎么用过这个功能,每次写策略,都是在strategy中,按照自己需求定制的信息
    
          - ``tradehistory`` (default: ``False``)
    
            If set to ``True``, it will activate update event logging in each trade
            for all strategies. This can also be accomplished on a per strategy
            basis with the strategy method ``set_tradehistory``
    
            # 如果tradehistory设置成了True,这将会激活这样一个功能,在所有策略中,每次交易的信息将会被log
            # 这个也可以在每个策略层面上,使用set_tradehistory来实现。
    
          - ``optdatas`` (default: ``True``)
    
            If ``True`` and optimizing (and the system can ``preload`` and use
            ``runonce``, data preloading will be done only once in the main process
            to save time and resources.
    
            The tests show an approximate ``20%`` speed-up moving from a sample
            execution in ``83`` seconds to ``66``
    
            # optdatas设置成True,如果preload和runonce也是True的话,数据的预加载将会只进行一次,在
            # 优化参数的时候,可以节省很多的时间
    
          - ``optreturn`` (default: ``True``)
    
            If ``True`` the optimization results will not be full ``Strategy``
            objects (and all *datas*, *indicators*, *observers* ...) but and object
            with the following attributes (same as in ``Strategy``):
    
              - ``params`` (or ``p``) the strategy had for the execution
              - ``analyzers`` the strategy has executed
    
            In most occassions, only the *analyzers* and with which *params* are
            the things needed to evaluate  the performance of a strategy. If
            detailed analysis of the generated values for (for example)
            *indicators* is needed, turn this off
    
            The tests show a ``13% - 15%`` improvement in execution time. Combined
            with ``optdatas`` the total gain increases to a total speed-up of
            ``32%`` in an optimization run.
    
            # optreturn,设置成True之后,在优化参数的时候,返回的结果中,只包含参数和analyzers,为了提高速度,
            # 舍弃了数据,指标,observers,这可以提高优化的速度。
    
          - ``oldsync`` (default: ``False``)
    
            Starting with release 1.9.0.99 the synchronization of multiple datas
            (same or different timeframes) has been changed to allow datas of
            different lengths.
    
            If the old behavior with data0 as the master of the system is wished,
            set this parameter to true
    
            # 当这个参数设置成False的时候,可以允许数据有不同的长度。如果想要返回旧版本那种,
            # 用data0作为主数据的方式,就可以把这个参数设置成True
    
          - ``tz`` (default: ``None``)
    
            Adds a global timezone for strategies. The argument ``tz`` can be
    
              - ``None``: in this case the datetime displayed by strategies will be
                in UTC, which has been always the standard behavior
    
              - ``pytz`` instance. It will be used as such to convert UTC times to
                the chosen timezone
    
              - ``string``. Instantiating a ``pytz`` instance will be attempted.
    
              - ``integer``. Use, for the strategy, the same timezone as the
                corresponding ``data`` in the ``self.datas`` iterable (``0`` would
                use the timezone from ``data0``)
            # 给策略添加时区
            # 如果忽略的话,tz就是None,就默认使用的是UTC时区
            # 如果是pytz的实例,是一个时区的话,就会把UTC时区转变为选定的新的时区
            # 如果是一个字符串,将会尝试转化为一个pytz实例
            # 如果是一个整数,将会使用某个数据的时区作为时区,如0代表第一个加载进去的数据的时区
    
          - ``cheat_on_open`` (default: ``False``)
    
            The ``next_open`` method of strategies will be called. This happens
            before ``next`` and before the broker has had a chance to evaluate
            orders. The indicators have not yet been recalculated. This allows
            issuing an orde which takes into account the indicators of the previous
            day but uses the ``open`` price for stake calculations
    
            For cheat_on_open order execution, it is also necessary to make the
            call ``cerebro.broker.set_coo(True)`` or instantite a broker with
            ``BackBroker(coo=True)`` (where *coo* stands for cheat-on-open) or set
            the ``broker_coo`` parameter to ``True``. Cerebro will do it
            automatically unless disabled below.
    
            # 为了方便使用开盘价计算手数设计的,默认是false,我们下单的时候不知道下个bar的open的开盘价,
            # 如果要下特定金额的话,只能用收盘价替代,如果下个交易日开盘之后高开或者低开,成交的金额可能离
            # 我们的目标金额很大。
            # 如果设置成True的话,我们就可以实现这个功能。在每次next之后,在next_open中进行下单,在next_open的时候
            # 还没有到next,系统还没有机会执行订单,指标还未能够重新计算,但是我们已经可以获得下个bar的开盘价了,并且可以
            # 更加精确的计算相应的手数了。
            # 使用这个功能,同时还需要设置cerebro.broker.set_coo(True),或者加载broker的时候使用BackBroker(coo=True),或者
            # cerebro的参数额外传入一个broker_coo=True
    
          - ``broker_coo`` (default: ``True``)
    
            This will automatically invoke the ``set_coo`` method of the broker
            with ``True`` to activate ``cheat_on_open`` execution. Will only do it
            if ``cheat_on_open`` is also ``True``
    
            # 这个参数是和上个参数cheat_on_open一块使用的
    
          - ``quicknotify`` (default: ``False``)
    
            Broker notifications are delivered right before the delivery of the
            *next* prices. For backtesting this has no implications, but with live
            brokers a notification can take place long before the bar is
            delivered. When set to ``True`` notifications will be delivered as soon
            as possible (see ``qcheck`` in live feeds)
    
            Set to ``False`` for compatibility. May be changed to ``True``
    
            # quicknotify,控制broker发送通知的时间,如果设置成False,那么,只有在next的时候才会发送
            # 设置成True的时候,产生就会立刻发送。
    
        '''
    
        params = (
            ('preload', True),
            ('runonce', True),
            ('maxcpus', None),
            ('stdstats', True),
            ('oldbuysell', False),
            ('oldtrades', False),
            ('lookahead', 0),
            ('exactbars', False),
            ('optdatas', True),
            ('optreturn', True),
            ('objcache', False),
            ('live', False),
            ('writer', False),
            ('tradehistory', False),
            ('oldsync', False),
            ('tz', None),
            ('cheat_on_open', False),
            ('broker_coo', True),
            ('quicknotify', False),
            ("load_my_data",False),
            ("save_my_data",False)
        )
    

    参考文献:https://www.backtrader.com/docu/cerebro/

    展开全文
  • 简单地说,所谓语义,不管是自然语言的语义还是形式语言的语义,基本上就是两系统之间的映射关系。自然语言的语义,是语言符号和我们大脑中概念之间对应;而形式语言的语义,则是符号系统和某个学科的知识体系之间...

    谓词逻辑及形式系统 (语义)【中】

     

    一、概述

    一、什么是语义
    简单地说,所谓语义,不管是自然语言的语义还是形式语言的语义,基本上就是两个系统之间的映射关系。自然语言的语义,是语言符号和我们大脑中概念之间对应;而形式语言的语义,则是符号系统和某个学科的知识体系之间建立的对应关系,现在研究最多的是符号系统与数学结构之间的映射关系,以及符号系统与哲学体系之间的对应关系。如果要用一个统一的概念表达符号系统所对应的其它学科知识体系,那么这个概念就是【模型】。
    有了模型的概念,对什么是语义的定义就可以简明扼要地表示为:
    语义:符号系统 → 模型
    模型,在我们日常生活语言中,通常称作“语境”、“上下文”、“世界”、“背景”、“客观环境”等,但是这些表达通常意义模糊,无法准确、精确地把握模型的基本概念。

    模型的概念,在数学中,又称作结构,这是对任何数学分支、数学对象的一种统称。上世纪1930年代,法国的布尔巴基学派曾经企图用“结构”这个概念统一所有的数学分支。虽然没有获得学界完全的接纳,但相当一部分数学家是认可这样的定义的,而且就算不认可的数学家迄今为止也未曾提出过比“结构”更强有力的概念作为数学研究的统一概念。结构作为一个严格的数学概念,用不太严谨的语言表述就是:一个非空集合、以及在这个集合之上所定义的集合元素间的关系和对集合元素的操作。例如,自然数可以看做是一个结构,它是由所有非负整数构成的集合、加上大小关系以及相应的加法乘法运算构成。不过在逻辑学,模型是更广泛使用的概念,故我们这里通常使用“模型”作为基本的术语。

    一个一阶谓词逻辑系统,就是这样的形式语言符号系统,它的的句法成分就是我们前面内容所介绍的常项、变项、谓词、量词和句子。它的句法规则就是我们用统一的归纳法所定义的规则程式:
    1. 设定基本概念为该语言的良形表达式(wff);
    2. 如果表达式A是wff,则操作φ(A)生成的表达式也是wff;
    3. 如果表达式A是wff且表达式B是wff,则操作ψ(A, Β)生成的表达式也是wff
    4. 本语言的任何表达式是wff当且当该表达式是由上述1-3规则生成。

    由这样的句法规则生成的句子的集合,称作一阶语言(first order language)。通常一阶语言的句法层面称作该语言的形式层面。一阶语言的形式层面就是一个由有限多、或无限多没有任何意义的符号按照上面的规则建立的字符串集合。如果要让我们的一阶语言产生意义,就必须要创建/设定一个模型,按照一定的映射规则建立该语言元素与模型对象之间的对应,或者称作绑定。这里要注意的是,这个被映射模型,并不属于一阶语言,模型只是某个特定学科、知识体系的数学化表示,或者称作‘建模’,或者称作XX理论的形式化。
    一阶语言的这个特点,或者说形式语言的这个特点,和自然语言大不相同。任何人类使用的日常语言,其词汇、特别是实词本身就带有“天然的”语义。这些词汇的语义已经作为该语言母语话者大脑认知世界的一部分。而且,对相同的词汇,不同语言体系的语义是不相同的。例如,’勉强‘在日语中,是‘学习’的意思。换句话说,同一语言符号,对应不同的模型,所产生的映射关系亦不相同。

    因此可以说,自然语言基本元素的语义,原则上说是天然的,不是人为规定的,但是许多科学新发现导致了新概念新术语的出现,这些新词,或者是旧词新用——重新定义,或者是全新的造语。伴随着网络的发达,由于网络交际的需要,交际参与者会创造许多‘经济实惠’的特殊词汇。例如在中国,由于严格的网络管制,甚至促使网民利用各种手段创造出独特的微语言体系,造成了特定语境下的网络语言。从这个意义上说,人对于自然语言词汇的语义并非被动接受,相当一部分是重新创造的。如果用我们现在的术语表述的话:
    网络语言符号→特定的概念系统

    而一阶语言,或者更广义地说,形式语言的基本元素则没有固定的(predefined)语义,或者说根本就没有语义,只有在和一个特定的模型人为‘绑定’之后才产生语义,这时我们可以说,这个语言得到了‘解释’ (interpretation)。而‘解释’,并不属于这个形式语言的一部分。为什么?因为我可以拿这个语言和其它结构建立绑定关系,这个时候语言中的元素得到新的‘解释’。换句话说,形式语言的语义论不属于相关形式系统的一部分,因为其语义解释端看和哪个模型绑定。形式语言的这种特性,使得它可以作为多种学科的基础语言,这也是为什么逻辑学是多门学科精密化基础的原因。形式语言和模型之间的这种‘解释’、‘绑定’关系,用我们的日常生活语言表示,就是‘描述’、‘描写’,例如,某部小说的作者,用一种淡淡哀愁的笔触描写了1930年代中国农村的景象。这时,‘笔触’代表的就是作者使用的语言,‘1930年代中国农村的景象’就是作家心目中的‘世界’,可看做是当时中国农村某个局部的‘模型’。
    语言和模型之间是相互独立的,这就像自然语言,既可以用来描写想象的世界,例如西游记,也可以用来写科学论文,例如关于天文学中的星体运动。这时,西游记中的人神鬼的世界、论文中的星体,和语言之间是相互独立的,因为汉语除了可以描述想象的世界、宇宙中星体,还可以干别的,例如在网上灌水。总之,语言工具、载体,和语言对应的世界相互独立的。

    由此我们可以得出结论:语义学不属于形式系统的组成部分,但仍然是理论所关注的重点,这个重点就是——语言符号和所描述世界之间的对应关系:解释、绑定、指称、描述、描写、表达、表述

     

    二、 谓词逻辑语义表达的基本工具

    既然语义的本质就是映射关系,那么熟悉中学数学的我们自然会想到,表达这种关系的最恰当工具就是函数。没错,函数就是逻辑学表达语义的基本工具。函数可以把这种映射关系形式化,可以精确地定义什么是“映射”,“映射”的各种状态和性质。但是如果要用函数表达映射关系,我们还需要一个非常重要的工具,那就是集合。因为集合可以精确表达什么是符号系统,什么是模型,而函数的本质就是两个集合之间建立的映射关系

    因此,在开始学习谓词逻辑语言的语义之前,需要熟悉函数、集合的概念。关于集合和集合论,后面的内容会介绍,也可参考任何离散数学教科书的相关内容,这里就不展开了。而对于函数,由于逻辑学所定义的函数和我们常见的数学函数相比有许多独特的性质,我们会在后面深入讨论。这里可以说的就一句话,逻辑中的函数,都是离散的,而我们中学时代熟悉的初等函数是连续的。

    在命题逻辑部分,我们已经看到了函数的作用,当时我们将命题逻辑的语义定义为从句子到逻辑真值之间的映射,亦即,
    设语义函数为V,设S是某个命题逻辑语言的所有句子的集合,设真值集合为{0,1}
    那么我们就可以将该语言所有句子的语义定义为
    V:S → {0,1}
    当时,我们将语义函数称之为‘赋值函数’(valuation)。赋值函数,使得我们可以根据真值表对该语言内每一个句子都能赋予一个唯一的真值

    命题逻辑语言的学习使我们可以看到逻辑学是如何定义和表示语义的——确定逻辑命题句的语义就是求真的过程。由于命题逻辑语言只关注复合句的语义而完全忽略原子句的语义,而复合句的语义则来自于逻辑连接符的语义定义。而逻辑连接词其语义是固定的,和具体的模型无关。因此,命题逻辑的语义相对是最简单的,只要通过真值表我们就可以知道句子的语(zhen)义(zhi)。

    而谓词逻辑虽然我们仍然使用赋值函数这个名称,但是情况有了本质的变化。首先,我们已经深入到单句的内部,要了解单句本身的结构,这样,我们要处理名称、属性,加上量词,这使得事情变得非常复杂,复杂得使我们不得不重新建立语义论,而不能以命题逻辑的语义论为基础加以改造。

    首先,谓词逻辑中的基本元素,常项、变项、谓词、量词等,不像句子,它们没有真值,因此无法用赋值函数赋予它们特定的值。因此,在赋值函数之外,我们会引进【解释函数】的概念。它的任务就是将语言中的这些非句子的基本元素和模型中的对象建立一对一的赋值关系。形式化的表示就是:
    设ƒ为解释函数,设形式语言为L,设模型/结构为D,则:
    ƒ:L → D

    这样,对于句子,我们有赋值函数,对于其它成分,我们有解释函数,这是命题逻辑语义所没有的。

    三、谓词逻辑语义论的研究方法

    有了基本概念和工具的理解,我们就会不难理解一阶语言语义学习的基本内容了。

    1. 扩充的函数概念:当我们有了一个句法上严格定义的形式语言之后,我们需要用“解释函数”对谓词逻辑语言中所有的元素,包括常项、变项、属性、命题、量词进行‘解释’,这时,常项要对应一个具体的概念或实体,变项要对应概念和实体的一个范围,属性要对应一个集合,而量词则对相应集合范围的界定。这远比我们在命题逻辑中句子对应真值这单一的情况复杂多了。

    由于一阶语言符号系统要面对各种不同的模型,因此实际的映射关系并非整齐划一,会出现各种不同情况。这些情况如果以函数作为工具表述的话就是我们在中学函数学习中出现的三个概念:函数定义域和值域之间映射的三种状态:单射、双射和满射。这个问题我们会在后面详细阐述。

    2. 确定模型的定义。由于谓词逻辑中涉及到概念、属性,而这些东西只能和特定的语境、学科、世界相关,所以我们先要确定我们的形式语言要和哪个具体语境相关。例如我们可以用一个特定的谓词逻辑语言和《西游记》绑定,这个时候,这个语言的每个常项都和《西游记》中某个具体人物产生对应关系;在此基础上我们可以建立《西游记》中的人物关系表,确定每个人物的行为举止,例如神仙可以飞天,凡人不可,但神仙凡人都可以行走。我们也可以用这个形式语言绑定代数中群的结构,这个时候,每个常项对应着某个自然数,变项则对应于某个自然数范围;然后确定确定基本关系自然数的大小关系和基本运算;最后,我们根据自然数的性质,进一步确定关于群的公理系统。因此,从某种意义上,我们的谓词逻辑语言真是一种万金油系统,它的语义是什么,你说了算。如果将谓词逻辑,包括形式语言、推理规则全面应用到某个数学理论,那这个逻辑就换了顶帽子,一个非常高大上的、非常耀眼的名称——数理逻辑。而数理逻辑对数学的应用最深入的部分就是关于算术、或者用一个让你颤抖的名词,关于数论的研究。可以说现代数理逻辑的所有内容包括非常“高大上”的哥德尔定理都是关于逻辑在算术应用方面的内容。而谓词逻辑的语义论和数学一旦挂钩,由于数学本身的确定性、可定义性,就产生了专门的研究一阶谓词逻辑语义和特定数学结构之间映射关系的数理逻辑学分支——模型论。因此可以说,谓词逻辑语义论是模型论的起点

    3. 赋值函数。和命题逻辑语言一样,谓词逻辑语言对命题逻辑句子的语义解释也是通过赋值函数进行的。由于谓词逻辑语言是命题逻辑语言的超集,所以命题逻辑语言的复合句的语义解释、亦即、它的语义赋值函数不变,仍然有效。不过在本章学习中,我们会深入研究各种句子之间的真值【等价】问题,也就是说,许多句子的句法形式不同,但是它们的真值却总是相同的。而等价关系是所有形式系统进行符号变换、或者说逻辑表达式形式变换的理论依据。这种等价关系就相当于我们在中学数学中学到的许多等式关系一样,例如 (a+b)² = a²+2ab+b²,同样,我们也会接触到类似的逻辑等式。顺便说一句,现代逻辑学研究,有两个研究路线,一个是将逻辑当做推理规则研究。另一个是将逻辑当做代数研究,这个时候,我们只关注抽象的逻辑符号和逻辑式,就像我们在中学中关于实数的代数一样,只关注抽象的代数式和代数式之间的关系一样,这就是我们在《离散数学》中所学到的逻辑知识。正因为如此,我们从一开始就呼吁、提醒要将符号逻辑的学习过程看做是学习外语和代数的过程。

    在研究赋值函数的时候,我们需要学习两个重要概念:分析真(analytical)和合成真(synthetic)。简单地说,所谓分析真,就是说命题的真值和模型、结构无关,它的真是建立在逻辑关系上的,就像上面的数学等式,和具体的数无关。而合成真,则相反,一个句子的真值和所对应的结构、模型相关。例如1+1=10,在十进制算术中是错误的,句子真值为假,但在二进制算术中,句子真值为真。换句话说,当我们对形式语言和特定的结构、模型挂钩之后,我们要区分哪些句子的真值依赖模型、哪些不依赖如果句子间的等价关系不依赖模型,那么就称作逻辑等价;逻辑等价的另一个术语就是重言式,或永真式(tautology)。而和重言式相反的句子则称为“矛盾式”(contradiction),亦即,在任何模型中真值为永假。那些依模型不同而真值不同的句子称作contingency,对此好像没有统一的译法,有的叫“偶然式”,或“适然式”,还有的叫“可满足式”、“权变式”,我这里权且翻译作“可变式”,相对于永真式、矛盾式的真值不可改变。

    4. 模型的概念

    模型的概念是全新的,我们在本文开头做了简单的介绍,基本意思就是谓词逻辑语言所对应的世界、语境,它的数学表述就是结构的概念,因此我们对模型概念的定义、性质描述等,形式化表示都将以结构概念展开。而结构概念本身又是从集合、函数、关系这三个概念定义的。有了严格的模型概念,有了严格定义的一阶语言,再加上赋值函数和解释函数,我们就可以全面定义一阶谓词逻辑的语言——一阶语言的语义了。但是不要忘了,由于【模型】概念的引入,我们的赋值函数就不再是单一的了,因为句子的真值会随着模型不同而改变。因此在确定赋值函数之前我们先要确定模型。相对于命题逻辑的单一赋值函数V,在谓词逻辑中,赋值函数会有多个,具体多少个取决于你所选择的模型数量,因此对每个模型M,我们都会有相应的赋值函数就是VM和解释函数VI。(其中字母V代表valuation,赋值函数,M代表model,模型,I代表interpretation,解释)。

    5. 语义解释中的替换问题

    在用模型的概念进行语义解释时,我们预先假定形式语言和模型之间有一种理想的对应,每个语言元素都可以对应一个模型中的对象。现在的问题是,如果在我们的谓词逻辑语义建立之后,模型发生改变,例如又添加了新的对象,或者语言和模型之间原本就不存在一对一的满射情况下,如何确定谓词逻辑句子、特别是带全称量词的句子的真值就成了问题。举个简单例子,在一次考试中,我们班所有同学都及格了。因此,这句话为真。可是有一天从别的班调来一位新同学在那次考试中不及格,这时这个句子的真值就不再为真了。这个时候,我们需要的是另一种方法,这种方法比赋值函数方法繁琐,但可以保证在上述问题出现时仍然可以确定句子的真值有效。这个方法就是在赋值函数赋值之前,对句子中所涉及的所有命题真值做一次扫描。还拿上面的例子,在给“我们班所有同学都及格了”赋予真值之前,需要对班里每个同学是否及格逐一调查,因为我们班所有同学都及格了=A同学及格且B同学及格且C同学及格……。换句话说,全称量词的一个句子真值相当于多个单一名称句子合取真值,我们需要一个评估函数,对每个这样的单一名称的句子真值进行评估,这样,当模型中的对象发生改变时,由于赋值函数在应用之前我们先对关于每个对象的命题句进行了扫描,这样在进行赋值时就不会出现语言符号和对象之间数量不匹配的情况。为了应对这种现象,当谓词逻辑语言的句子出现量词的时候,就需要将命题分拆为多个以专有名称为主词的句子,同时设定一个特殊的赋值函数获取每个这样的句子真值,这时,如果句子的一般形式为∀xφ(x),那么对这个句子的赋值函数就是
    VM(∀xφ(x)),要获得这个句子的语义,就要知道x所代表的个体范围内的元素集合{a1,a2,..an}使得句子φ(a1),φ(a2),..φ(an)的真值都为真。因此为了扫描每个这样的句子,我们将设定一个特殊的赋值函数g使得g(φ(a1))∩g(φ(a2))∩,..∩g(φ(an))为真,因此我们有 VM(∀xφ(x)) = g(φ(a1))∩g(φ(a2))∩,..∩g(φ(an))

    这样,一个通用的一阶语言的赋值函数就成为:VM,g(ψ),其中ψ代表一阶语言的任意句子。

    除了以上的内容,谓词逻辑的语义部分还要引入“同一性”的概念和相应的逻辑运算,除此之外我们还要深入‘关系’的概念在语义的作用,最后讨论几种逻辑学常用但是在数学很少看到的函数表示法。

     

    二、量词的语义

    1. 命题逻辑的最小元素是单句,也就是不包含逻辑连接符的句子,所以,命题逻辑的研究对象是复句:复句的句法和语义。而谓词逻辑则深入到单句内部,将单句分解为两部分:主词和谓词。在亚里士多德的传统逻辑中,对单句的分析是根据词项:主词词项和谓词词项进行的。而在弗雷格的一阶逻辑中,一个逻辑系统,通常是由以下部分组成:
    1. 逻辑连接符:¬、∨、∧、→、↔︎
    2. 量词:∀、∃
    3. 个体常项:a、b、c、x、y、z...(或该系统定义的特定的个体词系统),相当于亚氏逻辑中的主词
    4. 谓词常项:P、Q、R...(或该系统定义的特定的谓词系统)

    其中1-2是一个逻辑系统固有的成分,而3-4则因逻辑系统的定义不同而不同。这一点以前也说过,就和程序语言一样,前者相当于语言中的关键字和预定义运算符,例如+、-、*、/、%等,后者则相当于用户定义的常量、变量名,以及函数名;语言只规定了定义的方法和格式,因每个应用程序可根据要解决的问题种类具体定义每个常量、变量和函数名。其实,现代程序设计语言就是从逻辑语言演化而来,通过逻辑的学习,我们可以看到这种演化的痕迹。

    由于命题逻辑的基本成分是单句,定义它的语义相对就比较简单,用一个真值表基本就可以解决。不过出于形式化和精确化的需要,我们定义了称作“赋值函数”(valuation)的工具,用来给每个wff赋予一个真值。
    而谓词逻辑的成分,如上可知,比命题逻辑要多很多,语法句式相应也比较复杂,我们无法像命题逻辑那样,采用单纯的“赋值函数”、根据真值表取得真值了。其中最大的问题,正如我们前面介绍的,谓词逻辑的所有成分没有真值。
    当然,广义的谓词逻辑,包括了命题逻辑,应当是命题逻辑的超集,在这种语境下,谓词逻辑又称作“一阶逻辑” (first order logic);描述这种谓词逻辑的语言称作“一阶语言” (first order language);基于谓词逻辑系统的论证过程称作“谓词演算”或“一阶谓词演算” (predicate calculus or first order predicate calculus)。因此,命题逻辑的赋值函数仍然适用于具有复句结构的谓词逻辑句子。

    现在让我们把上面所说的符号化一番
    1. 设:L为某个有定义的一阶语言;
    2. 设:T为真值集合:{0,1}
    3. 设:V为赋值函数,这个函数的定义域是L,值域是T,则赋值函数的一般形式为:
    V:L → T(注意:这里的箭头表示函数从定义域到值域的映射关系,而不是蕴含逻辑连接符)
    这样我们就可以重复命题逻辑复句的语义了:
    (i) V(¬φ) = 1 当且当 V(φ) = 0
    (ii) V(φ ∧ ψ) = 1 当且当 V(φ) = 1 且 V(ψ) = 1
    (iii) V(φ ∨ ψ) = 1 当且当 V(φ) = 1 或 V(ψ) = 1
    (iv) V(φ → ψ) = 1 当且当 V(φ) = 0 或 V(ψ) = 1
    (v) V(φ ↔︎ ψ) = 1 当且当 V(φ) = V(ψ)
    除此之外,谓词逻辑还定义了含有量词句子的赋值函数,这一点是命题逻辑没有的:
    (vi) V(∀φ) = 1 当且当 V([c/x]φ) = 1,其中c代表L中的任意个体常项
    (vii) V(∃φ) = 1 当且当 V([c/x]φ) = 1,其中c代表L中的至少一个体常项

    这里,需要对(vi)和(vii)做进一步的说明和解释。
    一、“∀φ”代表语言L中任意一个含有量词的句子;
    二、“V(∀φ) = 1”表示∀φ这个句子的语义解释在某个特定语境中真值为“真”
    三、“V([c/x]φ) = 1,其中c代表L中的任意个体常项”,这句话是在说明全称量词的意义是:用语言L中定义的所有个体词替换x,都可以使这个命题成真:V(∀φ) = 1。
    换句话说,当含有全称量词的某个命题为真时,相当于多个个体谓词句子和合取:
    设L中个体常项的集合是: C = {c1, c2,…cn} ; V(∀φ) = V(∀φ(c1) ∧ ∀φ(c2) ∧ ∀φ(c3) ∧ … ∀φ(cn))
     

    举个例子
    1.
    a. 张晓华、李建、王立波这三个人都很聪明。
    这句话可以理解为:
    b. 在张晓华、李建、王立波这三个人组成的集合中,所有人都很聪明。

    用我们上面定义的一阶语言:
    个体常项:张晓华、李建、王立波
    谓词常项:很聪明
    量词: 都,或者 所有...都

    如果用全称量词符号∀代表“所有...都”,用φ代表“人很聪明”,那么这个句子的语义解释就是:V(∀φ) = 1 当且当 V(φ(张晓华) 且 φ(李建) 且 φ(王立波)) = 1

    翻译成自然语言就是:
    张晓华、李建、王立波这三个人都很聪明 = 张晓华很聪明且李建很聪明且王立波很聪明。

    由上面可以看出,全称量词的一个句子,相当于使用语言中所有的名词作主词加上谓词形成的多个句子的合取。这跟我们的直觉一致。再举个例子:
    他这学期的所有科目的成绩都是A。如果所有科目的意思是:{语文、数学、物理、化学、生物},那么这句话的意思就是:
    他这学期的语文成绩是A、他这学期的数学成绩是A、他这学期的物理成绩是A、他这学期的化学成绩是A、他这学期的生物成绩是A。
    上面的公式:
    (vi) V(∀φ) = 1 当且当 V([c/x]φ) = 1,其中c代表L中的任意个体常项
    表达的正是这个意思。

    如果用类似编程语言的方式表达,那含有全称量词的命题句的语义确定是这样的:
    对于 每一个个体常项ci 在{c1,c2,… cn} 其中i是从0开始的自然数
    如果V(∀φ(c[i])) = 1,那么继续考察下一个个体常项c[i+1]直到c[n]
    如果V(∀φ(c[i])) = 0,那么考察停止,该命题的真值为0
    如果V(∀φ(c[n])) = 1,那么该命题的真值为1

    这里最有意思的地方是:我们将语义解释,对全称量化句子的语义解释,变成了一个算法,通过对每个含有具体个体常项命题句真值的解释,最后得到全称量化命题句的语义解释。这一点,对于那些对逻辑与计算感兴趣的朋友可以说是非常好的启发。当然,一般意义上的符号逻辑只关心论证,不关心计算,而一旦逻辑的关注点加入计算,就产生了许许多多新的领域,例如递归论,研究函数的可计算性。什么是可计算性?假如我们把上面例子中的个体常项的集合元素的个数设为无穷,用上面的公式就无效了,为什么?我要考察集合中每个元素看关于这个元素的命题句是否为真,那么我就得永远做下去,永无尽头。也就是说,我无法在有限的步骤之内得到一个确定的结果。那么上面那个赋值函数,就不是可计算的,因为我们永远无法知道:对所有个体常项来说,含有这些个体常项的命题的合取是否为真,也就无从知道全称命题的真值。

    存在量词的语义解释和全称量词基本上一样,唯一不同的是,全称量词要求语言中所有的个体常项代入命题句中真值唯一,而前者只需要一个个体常项代入命题为真即可。如果用上面的程序语言格式,同样是对每个常项扫描,只要遇到一个常项使命题为真,就停止扫描从而获得整个命题的真值。

    小结:

    • 谓词逻辑的语义解释涉及单句内部的成分,而这些成分没有真值,故语义解释的方法和机制和命题逻辑不同;
    • 命题逻辑可以看做是谓词逻辑、或者叫一阶逻辑的子集,因此谓词逻辑中关于复句的语义解释,使用命题逻辑的方法仍然有效;
    • 量词的语义解释:相当于对语言内所有名词进行扫描,把每个名词代入句子看是否为真,如果所有这样句子的合取的真值为真,那么全称量词句子的真值为真,如果有一个或以上的名词代入句子使得命题为真,那么存在量词句子的真值为真。
    • 从量词的语义解释方法可以看出,逻辑学的方法可以转化为一系列确定的步骤产生确定的结果,这样的过程称作算法。而算法是数理逻辑的分支递归论、或者称可计算理论的核心概念。
    • 我们将讨论模型以及单句内部成分的语义问题——解释函数

     

    三、模型

    既然谓词逻辑语言中除了句子,其它成分没有真值,那么如何来确定它们的语义呢?正如我们在开篇所述,所谓语义就是符号系统其它系统(大,可以包括我们生活的现实世界或者人类的精神世界,,可以仅仅是一句话、一顿饭之间建立的对应关系
    当我们只谈论符号系统时,我们是在谈论句法,当我们只谈论符号外的任何系统,我们是在谈论哲学、或者专业知识,只有当我们谈论符号与外部系统之间关系时,我们才是谈论语义。当然,语义并非是符号与外部世界的全部,例如如果我们是在谈论特定的符号系统,如自然语言,和特定的外部系统,如人的精神,这二者之间的对应,那么这个对此进行研究的就是语言哲学。如果符号系统是我们现在正在学习的人工语言——谓词逻辑语言,而外部系统是形式化了的数学理论——数学结构,那么对此进行研究的就是数理逻辑的模型论数学哲学

    所以,谈语义,实际上是在谈论关系,符号系统和任意其它外部系统之间的关系,而不仅仅是谈论符号系统本身。那么作为入门的我们,如何把握、或者说学习、理解所谓外部系统呢?换句话说,我们该学习哪些外部系统呢?其实,就像哲学一样,我们并不是要深入某个专业知识成为该专业的专家后才能学习逻辑的语义,站在逻辑学的角度,我们只需确定这个所谓外部系统的基本框架和形式定义。这个过程是这样的:
    一、确定我们所说的外部系统的确切含义,可以用形式化的工具精确地描述出来;
    二、不管外部系统的基本内容是什么,这些系统的共同组成部分有哪些?如何表达?
    三、给这些外部系统起一个比较科学的、不会引起歧义的名字。

    现在我们就来谈谈这个问题。先从第三个问题谈起。起名字,对中国人来说是人生一件马虎不得的大事,古来早就有“名不正则言不顺”的箴言。科学也一样,科学家对新的研究、新的发现和新的理论都会起一个一般人不太熟悉名称,以示之“新”。我们现在正在谈论的“外部系统”,是为了帮助大家理解而临时起的名称。真正的术语,叫做【模型】。我们见过许多实物模型,例如地产开发商在销售楼盘时会先在售楼中心展示未建楼盘和小区的模型;除此之外,我们还见过汽车模型、时装中心展示的模特模型,等等。

    如果抽去模型的物质属性来形式化地描述的话,那就是,把建模对象按比例缩小,省略、忽略或者去除跟建模目的无关的元素和成分,只留下建模对象需要的元素和成分,然后用和实物完全不同的材料和方式仿造建模对象。这段话可以归结为几个关键词——简化、抽象、形式化

    • 这里的简化,有两个意思,第一就是我们对“简化”理解的一般意思,去繁就简,还有一个意思就是:缩小规模,降低复杂度,如果是实物模型,那么只展示建模者想展示的内容,规模控制在视觉可以容纳的范围之内。例如地图是对实际上是地理状况的简化,一般的地图不可能做得和原对象一样大必须缩小到人的视觉可以看到的范围。小地图也就一本书大小,大地图充其量也就一墙之大。同样,地图也不可能把实际地理范围内所有对象都包括在内,总会有所取舍。
    • 而“抽象”的意思是,对模型中的一些对象无法、或者不必详细一一列举或展示,而是用一个“替代物”表示即可。例如在世界地图上找北京,恐怕我们能找到的就是也就是“北京”这两个汉字和旁边一个小点。如果较真,这两个汉字和那个小点和北京城有什么关系呢?根本没有!只是地图的制作者认为不必告诉你北京是什么,只要标出位置和名称即可。这个时候名称和位置的代表——“北京”和那个小点就是对北京的抽象。“红楼梦”是一个抽象,是对曹雪芹那部73万字著作的指称。我们电脑桌面上的“快捷方式”也是抽象,一个应用程序当在电脑中运行时,需要调用许多电脑的本地资源,所以,对用户来说通过点击“快捷方式”我们启动了电脑的一个应用程序,但是在内部,实际上要调用许多程序使这些程序互相配合工作。但是,作为用户的我们关心这个吗?根本不!我们只要知道那个快捷方式代表那个应用程序就够了。这个快捷方式和后面被代表的应用程序也是抽象和被抽象的关系。有例如文学作品中有这样一种表现形式:失散多年的情侣一朝相逢,只有泪千行,沉默良久,心中的万语千言只化作三个字:你好吗?这个时候也是一种抽象,用“你好吗”代替了原本的万语千言。
    • 形式化是什么呢?好像这个词在国内被“神圣化”或者被“妖魔化”了。“神圣化”是说好像什么东西一说形式化就显得“高深”、阳春白雪;“妖魔化”是说那些所谓“形式化”的东西一定是枯燥无味符号而已。其实形式化的意思很接地气。比如对我们人类脸部进行“形式化”,就是忽略你是男的女的,忽略你的颜值,然后做出结论,所有人都是一个鼻子两个眼睛一张嘴。你觉得还有比这更简单的“形式化”吗?售楼中心那些楼盘模型其实也是形式化,它只让你看到楼盘的外表,你无法知道这个楼盘的内部结构,如,如何供电、供水、下水道系统,也无法知道这个建筑物使用的是什么材料,总之,除了对这个建筑物的外表,你不会从这个模型获得关于这个建筑物的任何知识。这就是形式化。例如a+b=b+a,就是跟楼盘模型类似的形式化:你只得到了这是加法运算以及运算形式的外表——“形式”,而不知道这里a和b是什么意思(我可没说a和b一定是数哦)。


    由此可见,所谓【模型】,就是一个简化了的、抽象化了的、形式化了的外部系统

    现在谈谈第一个问题:【模型】在我们的逻辑系统中的确切含义。如果通过上述讨论你对【模型】概念有了感性的认识,这里我们的描述就比较理性化了。
    首先,我们要确定这个模型所包含的所有基本元素,使用的工具就是集合(domain、universe of discourse 或论域、域)。即作为目标的外部系统中的所有对象,或者我们谈论话题的最大边界范围。也就是说,我跟你谈数学的时候你千万别跟我谈人生,否则,‘ideal’这个词我无法定义(懂抽象代数的人大概知道我在说什么)。

    最后谈谈第二个问题:一个模型有哪些组成部分。一个模型,大致上要规定构成这个模型的基本要素,还要规定各个元素之间有那些关系,最后,各个元素,包括基本元素和复合元素有哪些功能,换句话说,它们能干什么,在模型中起什么作用。如果用集合论的语言表述:
    1. 定义一个论域:U = {x : S(x)},其中的S(x)表示作为该模型的元素的共同性质;
    2. 定义模型中元素的关系 R = {<x,y> : x∈U 且 y∈U}
    3. 定义模型中对元素的操作 F = {f(x) : x∈U},其中f(x)是函数,F是由f(x)构成的集合。

    有了模型的概念,我们就可以定义谓词逻辑语言中那些无法赋予真值的元素的语义了,所以接下来介绍的就是——解释函数(interpretation function)了。

     

    四、解释函数

    在前面我们曾经把全称量词的语义定义为关于论域中每个元素命题的合取,把存在量词的语义定义为关于论域中每个元素命题的析取。这里,我们描述谓词逻辑语言的语义所使用的语言就是集合论的语言。现在,为了讨论方便,我们再把这些定义形式化地重复一遍:
    (vi) V(∀φ) = 1 当且当 V([c/x]φ) = 1,其中c代表L中的任意个体常项
    (vii) V(∃φ) = 1 当且当 V([c/x]φ) = 1,其中c代表L中的至少一个体常项

    (vi)相当于V(∀φ) = 1 当且当 V(φ(a1) ∧ φ(a2) ∧ … ∧ φ(an)) = 1
    (vii)相当于V(∃φ) = 1 当且当 V(φ(a1) ∨ φ(a2) ∨ … ∨ φ(an)) = 1

    在这个过程中,我们其实少了一个最重要的步骤,这个步骤就是对每个子命题句中ai的定义,这里的ai,是形式语言中的任意符号,i表示从1开头的任意自然数。现在的问题是,在没有ai确切语义的情况下,你凭什么说V(φ(ai)) = 1。换句话说,在不知道句子的主语是什么的情况下,你凭什么说这句话对还是不对?
    对这个问题的回答是:对于一套符号系统,这个符号系统的基本元素是a1,…,an,如果使这些符号能够得到相应的语义解释,我们必须要有一个【模型】。这个【模型】中的论域是该模型所包含的所有对象的集合。如何才能让符号和对象建立语义解释关系呢?说成大白话就是:某个符号ai,怎么才能让它代表某种意思?我们前面已经说过,形式语言的符号系统本身没有天然的语义,符号的语义,端看你把它“绑定”到什么【模型】上。接下来,我们就来谈论这个问题。

    首先要搞清几个术语
    形式语言的语义研究,实质上就是符号系统与【模型】之间的对应关系研究,因此我们需要熟悉几个关键词,以及表示这些关键词的拉丁字母:
    1. 【符号系统】:通常是用“L”表示,L的意思是language,语言。
    2. 【模型】:用“M”表示,M就是模型,相对应的英语是model。
    3. 【】:这里的域,是指模型中对基本元素集合的定义,通常用“D”表示,对应英语单词是domain。
    4. 符号和模型域中的元素建立对应关系的过程称作【解释】,英语是Interpretation,所以关于解释的符号通常用“I”表示。
    5. 建立解释关系后,被解释的符号称作【常项】,相当于自然语言中的专有名词或名称。这种词的特点就是一旦赋予了解释一般不会再改变,例如“孔子”、“汉武帝”等名称。如果用编程语言,相当于程序中的符号常量,例如,pi=3.1415926。这个时候,符号pi就具有了不变的的语义解释:代表圆周率的值。常项,通常用“c”表示,相当于英语的constant。
    6. 建立解释关系后,对应于符号的模型域中的对象,称作【指称】(reference),或者【指称义】(denotation)。reference多用于自然语言的语义研究,而denotation则是程序设计语言语义学的专用术语——denotation semantics。模型中的指称客体,通常用“e”表示,相当于英语的entity(【实体】)。
    7. 【解释函数】:建立符号和指称实体之间对应关系的过程,书中称作【解释】(interpretation),有些书特别是面向计算机专业的数理逻辑书籍称作【绑定】(binding),反正意思就是使符号和实体对应。如果你是程序员,那么这个对你就更好理解了,其实就是定义一个变量后给变量赋值。在谓词逻辑语义学中,这个过程通过一个称作【解释函数】的机制完成。定义一个函数“I”,设该函数的定义域为符号集合L,值域为模型域中的对象集合D,这样的函数就称作解释函数。它的定义为:
    I : L → D
    解释函数的一个实例就是:
    I (c) = e
    意思是,解释函数接受一个符号,返回一个所对应的实体。例如,上面的例子“孔子”,“孔子”是两个汉字,
    I (“孔子”) = 孔子
    这里我们用带引号的“孔子”代表符号,用不带引号的孔子代表孔子这个实体的概念。

    有了上面的术语、概念和说明,下面看一个例子:

    (93) Some are white. [1]

    这里没有任何上下文,我们无从知道这句话究竟在说什么。为了使这句话的意思更明确,我们先确定“指称”的域,D,这样我们就可以确定这句话的主题范围。假定D是雪花的集合,如果用a代表一片雪花,那么,a is white 就可以理解为:名称a所代表的实体“雪花”具有“白”这种属性。这里,我们从模型的域中,任意选取了一个指称对象,然后给它冠以“a”的名称,并以命题句“a is white”的形式陈述关于“a”的性质。如果用这种办法定义前面关于量词语义的定义,我们需要做的第一件事就是要对D中的所有实体赋予一个名称,这些名称的符号表示就是L中的符号元素。不过这种办法有一个缺陷就是,在定义符号系统L的时候,我们不知道有多少符号合适。一旦建立和特定模型的解释/绑定关系时,符号的数量和实体数量可能不匹配,如果实体数量多于符号数量就要增加符号,如果可以定义的符号用尽,就必须改变符号系统的定义。举个例子,车牌号。例如我们可以用三个拉丁字母和三个阿拉伯数字组合形成车牌号。如果规定字母和数字不能混合,只能是XXX-999的形式,那么这个车牌号系统只能对应从26个字母取3得到的排列和从0-9这10个数字取3的排列的和。所以,每当有新的车主申请车牌号,就得从这种排列和的方法中找出尚未使用的字母数字组合。但是当城市人口增加,买车的人数超过了这种组合方式最大容许量,那么只能修改组合方式,例如增加字母或数字的位数以适应新的需要。
    为此,用解释函数对指称实体冠名的办法就必须改变。当然,如果预先知道模型域的大小是固定的,不会改变,前一种办法也是一种不错的办法。而面对不断膨胀或收缩的模型域,就得有另外一种办法。后面便会分别介绍这两种方法。第一种,我们称作替换法(Interpretation by substitution),第二种,称作评估法 (Interpretation by means of assignments)。
     

    五、替换法

    上面我们讨论了一阶谓词逻辑语义中的解释函数。如果这个名词对你过于抽象难以理解的话,不妨想象一下风景画。一副写实的风景画必然是对自然界的某一部分的描述,但这个描述并非百分之百地还原自然,而是由作画者的主观感受决定取舍。这个时候画中的每个元素都对应着作画者眼中自然界中相应的元素,例如一棵树、一块石头、一株草、一朵花等。我们可以把这幅画看做是对自然界某个部分的映射,从而建立画与自然之间的“解释函数”:只要找到画中的一个元素,我们就可以找到相应自然界的对应元素,换句话说,在画板上由各种颜料组成的某个区域,可以看做是一种符号,这个符号对应着自然界中某个空间中的某个自然物,画中所有元素与所有自然物对应关系的集合,就是一种“解释函数”。当然,这个比喻不是很严谨,因为逻辑语义学中的元素必须是离散了,可数的,可枚举的,而自然物,例如,天,河流等,是连续的,是无法精确划分成离散的个体。不过这个例子可以让我们重新复习一下前面讨论过的一些概念:模型、域和符号系统。

    所谓【模型】在这里就是作画者所选取的自然空间,而且这个空间应当不是那个自然空间本身,而是作画者本人有所取舍的概念化的自然空间。这个空间可能会忽略一些作画者认为不需要表现的元素,或者,因人类视力所限无法看到或看清的元素,因此画画的对象是自然空间的“模型”而不是自然空间本身。

    所谓【】,就是在这个模型中出现的所有元素的集合。就像上面所说,元素必须离散、可数的,这个只有在【模型】中才办得到。比如“天”,自然界中的天应当是不可数的,但是在作画者看来,所谓的“天”无非就是在画布上由其它元素隔开的几块不同区域,因此是“可数的”。

    所谓【符号系统】这里就是风景画中的所有元素的集合。所以,这幅风景画的“语义”就是:作画者根据自己的视觉可及和主观感受在大脑中对某个自然空间景色“建模”,形成【模型】;在这个模型中,确定要画的所有元素,这就是【域】;而完成的作品,用颜料组成一个【符号系统】。当熟悉画中自然景观的观画者看到这幅画时就会联想实际的自然景观,从而形成从画到景观的【映射】关系。

    理解了【模型】、【域】、【符号系统】、【解释】、【解释函数】,我们就可以进入正题,谈谈【替换法】和【评估法】。

    替换法又称作替换解释(interpretation by substitution)。这种方法其实在前面的量词的语义处已经说明,主要是用来说明量词的语义。前面我们已经给出了精确的一阶谓词逻辑语言的描述,这里再用比较通俗的语言重复一遍:【全称量词】的语义就是:当我们说:“所有的人都会死”时,存在一个模型,这个模型中的元素都具有“人”的性质。同时,存在一个【符号系统】使得模型中的每个元素都对应着该符号系统中至少一个符号,说白了,就是每个人至少都有一个名字。所以,“所有的人都会死”的语义就是用每个人的名字【替换】“所有人都”出现的位置,例如,“张三会死”、“李四会死”,…同时用“合取”连接符将对应【域】所有元素的名称都替换一遍,这样,量化句就转化为N个个体名称+谓词句的合取操作。此时,解释函数的任务就是保证域中的所有元素都被赋予了至少一个名称。这个说明如果用一阶语言表述的话就是

                                              


    类似地,我们还可以建立一般谓词的“语义”:在【域】中存在一个子集合,这个子集合与【符号系统】中的某个符号具有对应关系。所以,“张三很聪明”的意思就是:在人这个【域】中,存在一个子集合,这个子集合与汉语这个符号系统中“很聪明”具有对应关系,而张三是这个子集合的成员,使得“张三很聪明”这个句子为真。
    这样,我们就可以为“谓词”建立解释函数:
                                                  

    其中,I是解释函数,A是谓词,a是名称,I(A)是域中的子集,I(a)是域中的个体元素,Aa相当于A(a),是逻辑句子的一般表示法。所以上面公式的通俗解读就是:
    等号左面:A的解释函数I(A)的意思是:
    等号右面:由名称a所对应的个体集合,使得“a是A”这个句子为真。
    上面的公式还可以写成:
                                                   

    意思是:名称为a的个体是名称为A的谓词所对应个体子集的成员

    无论用什么样的方式表示,用域中子集合的方式表示谓词语义通常称作“外延语义”。这种语义最常见的应用就是,当我们无法用“语言”说明某个事物或事件时,通常用是“举例”方法。例如,到外地或国外旅游,品尝到一种美味小吃,但是这种食品叫什么或者是一种方言或者是外语单词,我们无法从自己熟悉的语言中找到相应名词。要向自己的亲友解释,最好的办法就是把实物放在他们面前,“眼见为实”、“百闻不如一见”。这实际上就是用概念的外延在解释概念。
    这种解释法的核心,就是替换,将全称量词句替换成个体名称的合取运算,将个体名称+谓词句替换成是这个句子为真的域元素的集合。
    如果谓词是二元的,亦即,有两个个体词,那么其语义就成为所对应域元素有序对的集合
                                           
    或者,
                                             


    这里要注意的是,I(a)和I(b)可能分属两个不同,或者两个相同的域。如果是不同的域,例如D1和D2,就会写作D1xD2;如果是相同的域, 在多域的情况下,通常会用D^n
    的方式表示,其中n是D的指数,例如上面的例子两个相同的域,故写作是D²。

    有了上面的讨论,我们就可以给出谓词逻辑语言中关于【模型】的形式定义,以及谓词逻辑句子语义的赋值函数的定义
    模型
    相对于谓词逻辑某个语言的模型是由【域】和解释函数构成;域是一个非空集合;而解释函数有两种:个体名称的解释函数和谓词的解释函数
    如果c是语言L中的一个个体符号,那么I(c)的意思就是c所对应域中的个体元素;
    如果B是语言L中的一个n元谓词符号,那么I(B)的意思就是域中的某个子集合,满足
                                                        


    赋值函数
    如果M是对应语言L的模型,其解释函数I是语言L中个体名称到域D的映射,那么,

                                                                              
    就是基于M的赋值函数。这样,关于一阶谓词逻辑语义的赋值函数就成为

                         

    好了,现在小结一下:

    谓词逻辑语言的语义是基于模型的映射关系。
    1. 模型:由域和解释函数构成;解释函数的任务是为域中的元素起名字;
    2. 赋值函数:对谓词逻辑中的每个句子分配真值
    3. 谓词逻辑的语义称作外延语义,这种语义的实质不是定义,而是举例,用实例说明概念。
    4. 所谓替换法就是利用赋值函数对句子赋予真值一种方法,它将量化句子中的变量用符号系统(亦称语言)中的名称一一替换,如果是全称量词则进行合取运算,若是存在量词则进行析取运算,从而获得该量化句子的真值。如果是谓词,则取域中的某个子集,并赋予名称,这样,像P(A)这样句子语义解释酒可以看作是域中某元素是该子集合的成员。判断这类一阶谓词句子的真值,就可以利用解释函数看看当前给定的名称所对应的域中个体是否是谓词所对应的子集合的成员,如果是该句子为真,如果不是则真值为假。
    解释函数赋值函数的基本过程是将单句转化成含有所有域元素名称的个体名称句子的合取操作

     

    六、评估法

    当我们面对一个一阶谓词逻辑系统,设语言(符号系统)为L、域为D、解释函数为I,那么解释函数定义为:
    I:L → D
    其中L是I的定义域,D是I的值域。前面讨论的替换法有一个前提,解释函数I是满射函数,亦即,对于值域D的任何𝑦元素,都可以找到L的元素𝑥使得
    I(x) = y
    这时,当我们对句子∃𝑥Φ和∀𝑥Φ进行语义解释时,就可以利用常量c替换束缚变量𝑥得到关于c的句子的语义解释,然后利用析取或合取公式得到∃𝑥Φ或∀𝑥Φ的语义解释。为此,我们再来复习一下量化表达式语义赋值函数的定义:

                                     
    其中,“for all”意思是要通过合取运算对域中所有的元素进行替换,如果合取句子的真值为真,则对整个量化句子的语义解释也为真;类似地,“for at least one”意思是,析取句子的真值为真,则对整个量化句子的语义解释也为真。

    而我们这里所要介绍的“评估法”(Interpretation by means of assignments)是假定解释函数并非满射,换句话说,值域中的元素未必可以找到可对应的定义域元素,再通俗点说就是现实生活中有些物体在我们所选择的语言中找不到相应的名称(例如以前举例外地外国小吃找不到合适的名称形容); 此时用替换法就不可行了,因为我们的语言符号无法“覆盖”所对应的域元素,句子∃xΦ和∀xΦ的真值无法归结为[c/x]Φ的形式。如果我们仍然记得语义的“组合性原则”的话,那么知道这个原则是说:一个表达式的语义是由组成这个表达式各个部分的语义决定的。前面我们用了替换法,用c替换x,得到句子Φ(c)的真值。这里的问题是Φ(c)并非是∃xΦ或∀xΦ的一部分,因此我们无法通过“组合性原则”获得语义。这种量化句子是由量词∃x或∀x加Φ构成,所以严格地说Φ是这个量化表达式的一部分。如果Φ中含有变量x,那么这个x脱离了量化的束缚,就成为自由变量,因此可以写成Φ(x),和量化表达式不同,这种形态不再是句子,而只能是具有自由变量的命题函数。我们知道命题函数和命题的区别就在于后者有确定的真值而前者没有。束缚变量,从某种意义上说是指在一个确定了范围内的确定的量,但是自由变量却只是没有任何意义的占位符。那么如何对含有自由变量的句子赋予语义解释呢?还是拿个例子说明吧。前面我们有个英语句子,如下:

            (96) Some are white
     
    如果域模型设定是由所有“雪花”构成,那么作为含有自由变量的句子“x is white”的语义解释自然可以以这个域模型作为其指称对象。其中的 𝑥 当然没有指称对象,不过,此时如果我们将𝑥看做是类似自然语言中的代词,而且我们已经设定了域模型就是雪花的集合,那么,就可以认定在特定语境中,𝑥可以作为一个名称的“代词”而具有和那个名称相同的指称对象,使得“x is white”获得真值。这样我们就可以以这种方式使得(96)获得真值,亦即,(96)为真当且当域模型中某个元素与𝑥建立了指称关系尽管此时的指称关系是间接的。

    下面再看一个例子:  ∃x∃y(Hxy ∧ Hyx)
    这个句子含有两个变量,如果依照上面的分析,可知这个句子子句Hxy ∧ Hyx有两个自由变量。很明显,我们可以造出包含三个、四个甚至更多变量的句子,那么如何对每个自由变量赋予指称对象呢?上面我们用的的是代词法,假定有一个名称a指称对象绑定,而x是作为a的一个别名,类似代词一样的作用;但现在自由变量一多这个方法就不再有效。为此,我们可以建立一个评估函数g,这个函数以句子中所有自由变量为定义域,以相应的域模型D为值域。有些朋友可能要问,这个评估函数和前面的解释函数之间是什么关系?这个关系是这样的:
    <g(x1), g(x2), ..g(xn)> ∈I(A)
    换句话说,每个评估函数值都是域模型子集合A的成员。这时,我们对多变量句子的语义赋值函数就写成了

                                                 

    这里的区别就是,评估函数的参数是句子中出现的自由变量,而前面解释函数的参数是语言中的常量——名称。但是如果句子中出现变量、常量混合的情况怎么办?为此,我们将引入另一个术语——【】(term)作为常量或变量的统称(collective name),【项】通常用字母 t 表示,而对 t 在模型 M 的语义解释则定义为

                                              

    这样,我们对一阶谓词逻辑句子的语义解释函数定义可以修改为:

                                                 

    在这个解释框架下,一个句子的语义既取决于所选的模型也取决于对每个【项】的语义评估。

    现在有个问题,当句子出现多个变量既有自由变量又有束缚变量时该如何处理:
    例如:
    x loves someone        翻译成一阶语言是              ∃yLxy
    其中,x是自由变量,而y则是束缚变量。那么如何定义

                                                            


    由于x是自由变量,我们可以用g(x)表示,也就是g(x)喜欢某人的意思。这时,我们无法简单地,直接将量词分离得到Lxy,因为这样一来,xy都变成自由变量了,不符合原句的意思。因此,我们必须在分离之前,将束缚变量的指称对象看做是未具名的个体,用d ∈ H表示,那么,模型中对L(love)的解释则成为:<g(x), d> ∈ I(L),其中,someone在模型中并没有相应的名称项表示,而直接用实体d表示。有人会问,那为什么不用g(y)表示?如果要用g(y)表示,那就意味着x和y的评估函数是一个,但这并不符合事实,因为前者是自由变量后者是束缚变量。作为权宜之计,我们可以设一个和g(y)类似的函数:g’(y),这样我们就得到:
    <g(x), g’(y)> ∈ I(L)
    使得

                                          

    不过,我们知道g’(y)实际上指的就是d,因此可以用g[y/d]表示g’(y),意思是用d取代对y的评估函数。这里值得注意的是,不要把g[y/d]和前面的[c/x]Φ混淆,后者是句法层次的符号替换,而前者则是对域对象的替换。这样,对于∃yLxy语义赋值函数的最后版本就是:

                            

    第一次使用这样真值定义的学者是波兰数学家阿尔弗莱德·塔尔斯基。这样,我们的一阶谓词逻辑的语义真值定义为:

                                           

    小结

    本次讨论了赋值函数的另一种形式:评估法,这种方法的实质是对句子中的自由变量独立赋值,因为变量是语言中没有固定名称的符号。当句子中即含有变量又含有常量,既含有自由变量又含有束缚变量时,情况变得更加复杂,因此我们的处理办法就是无论是常量还是变量、无论是自由变量还是束缚变量,统称作【项】,然后统一对【项】进行处理。在处理过程中,将变量的指称对象在解释函数中统一用评估函数替换确定,使得整个句子得到真值。

     

    本文大部分内容整理与豆瓣逻辑小站,对逻辑学感兴趣的朋友可以关注:逻辑小站

     

    展开全文
  • 册涵盖了文化、经济、哲学、艺术、体育、政治、美学、心理学、社会学、伦理学、教育学、天文学等三十多学科门类,句型结构复杂多变。同时诸多文章里蕴含着深厚的哲思、美学及西方文化中独特的思维方式。同时将...
  • 操作系统概念第六版翻译版

    热门讨论 2012-08-05 13:11:37
    本书讨论了操作系统中的基本概念和算法,并对大量实例(如Linux系统)进行了研究。全书内容共分七部分。第一部分概要解释了操作系统是什么、做什么、是怎样设计与构造的,也解释了操作系统概念是如何发展起来的,操作...
  • 《操作系统概念》讨论了操作系统中的基本概念和算法,并对大量实例(如Linux系统)进行了研究。全书内容共分七部分。第一部分概要解释了操作系统是什么、做什么、是怎样设计与构造的,也解释了操作系统概念是如何发展...
  • 1 基本概念  6. 1. 1 CPU-I/O xE间周期  6. 1. 2 CPU调度程序  6. 1. 3 可抢占式调度  6. 1. 4 分派程序  6. 2 调度准则  6. 3 调度算法  6. 3. 1 先到先服务调度  6. 3. 2 最短作业优先调度  6. 3. 3 ...
  • 死锁基础原理

    2019-03-13 21:42:01
    2、死锁的定义3、死锁的必要条件二、鸵鸟策略三、死锁检测与死锁恢复1、每种类型一资源的死锁检测2、每种类型多资源的死锁检测3、死锁恢复、死锁预防(在程序运行之前预防发生死锁)五、死锁避免(在程序运行...

    一、死锁的基本概念

    1、为何会发生死锁?

      死锁的发生归根结底是因为对资源的竞争。因为大家都想要某种资源,但又不能随心所欲地得到所有资源,在争夺的僵局中,导致任何人无法继续推进。

    2、死锁的定义

      如果有一组线程,每个线程都在等待一个事件的发生,而这个事件只能有该线程里面的另一线程发出,则称这组线程发生了死锁。这里的事件主要是资源的释放,在死锁状态中,没有线程可以执行、释放资源或被叫醒。
    在这里插入图片描述
      如果线程A和线程B交替执行,那么线程A和线程B均会因为无法获得对应的资源而无法继续执行也不能释放锁,从而造成死锁,如下图所示:
    在这里插入图片描述

    3、死锁的必要条件

    • 互斥条件:每个资源要么已经分配给了一个进程,要么就是可用的。

    • 持有等待:即一个线程在请求新的资源时,其已经获得的资源并不释放,而是继续持有。

    • 不可抢占已经分配给一个进程的资源不能强制性地被抢占,即如果可以抢占一个资源,则也不会发生死锁。(凡是可以抢占的资源,均不会称为死锁的原因)。

    • 循环等待:有两个或者两个以上的进程组成一条环路,该环路中的每个进程都在等待下一个进程所占有的资源。即如果你等我、我等你,大家都这样等着对方,就产生了死锁。
      在这里插入图片描述

    二、鸵鸟策略

      把头埋在沙子里,假装根本没发生问题。因为解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响,或发生死锁的概率很低,可以采用鸵鸟策略。

    三、死锁检测与死锁恢复

      不试图阻止死锁,而是当检测到死锁发生时,采取措施进行恢复。

    1、每种类型一个资源的死锁检测

    在这里插入图片描述

      每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现,从一个节点出发进行深度优先搜索,对访问过的节点进行标记,如果访问了已经标记的节点,就表示有向图存在环,也就是检测到死锁的发生。

    2、每种类型多个资源的死锁检测

    在这里插入图片描述

    • E 向量:资源总量;
    • A 向量:资源剩余量;
    • C 矩阵:每个进程所拥有的资源数量,每一行都代表一个进程拥有资源的数量;
    • R 矩阵:每个进程请求的资源数量。

    算法总结如下:

    1. 寻找一个没有标记的进程 Pi,它所请求的资源小于等于 A(比如R中的第二行 )。
    2. 如果找到了这样一个进程,那么将 C 矩阵的第 i 行向量加到 A 中,标记该进程,并转回 1。
    3. 如果没有这样一个进程,算法终止。

    3、死锁恢复

    • 利用抢占恢复;

    • 利用回滚恢复;

    • 通过杀死进程恢复

    四、死锁预防(在程序运行之前预防发生死锁)

    • 破坏互斥条件:例如假脱机打印机技术允许若干个进程同时输出,唯一真正请求物理打印机的进程是打印机守护进程。

    • 破坏占有和等待条件:一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

    • 破坏不可抢占条件;

    • 破坏环路等待:给资源统一编号,进程只能按编号顺序来请求资源

    五、死锁避免(在程序运行时避免发生死锁)

    1、安全状态

    在这里插入图片描述
      图 a 的第二列Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数。从图 a 开始出发,先让 B 拥有所需的所有资源(图 b),运行结束后释放 B,此时 Free 变为 5(图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的。

    2、单个资源的银行家算法

      一个小城镇的银行家,他向一群客户分别承诺了一定的贷款额度,算法要做的是判断对请求的满足是否会进入不安全状态,如果是,就拒绝请求;否则予以分配。
    在这里插入图片描述
    上图 c 为不安全状态,因此算法会拒绝之前的请求,从而避免进入图 c 中的状态。

    3、多个资源的银行家算法

    在这里插入图片描述
    上图中有五个进程,四个资源。左边的图表示已经分配的资源,右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示:总资源、已分配资源以及可用资源,注意这三个为向量,而不是具体数值,例如 A=(1020),表示 4 个资源分别还剩下 1/0/2/0。

    【检查一个状态是否安全的算法如下】:

    • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行,那么系统将会发生死锁,状态是不安全的。
    • 假若找到这样一行,将该进程标记为终止,并将其已分配资源加到 A 中
    • 重复以上两步,直到所有进程都标记为终止,则状态时安全的

    如果一个状态不是安全的,需要拒绝进入这个状态。

    六、哲学家就餐问题

      五个哲学家围着一张圆桌,每个哲学家面前放着食物。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃饭时,需要先拿起自己左右两边的两根筷子(只有在他拿到两只筷子时才能进餐),并且一次只能拿起一根筷子
    在这里插入图片描述
      经分析可知:放在桌子上的筷子是临界资源,在一段时间内只允许一位哲学家使用,为了实现对筷子的互斥访问,可以用一个信号量表示筷子,由这五个信号量构成信号量数组。

    semaphore cpst[5] = {1, 1, 1, 1, 1};
    while(true)
    {
    	/*当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子*/
    	p(cpst[i]);
    	p(cpst[(i+1)%5]);
     
    	eat();
     
    	/*当哲学家进餐完成后,总是先放下左边的筷子,再放下右边的筷子*/
    	v(cpst[i]);
    	v(cpst[(i+1)%5]);
    }
    

      假如五位哲学家同时饥饿而都拿起的左边的筷子,就会使五个信号量chopstick都为0,当他们试图去拿右手边的筷子时,都将无筷子而陷入无限期的等待。

    1、策略一

      至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。定义信号量count,只允许4个哲学家同时进餐,这样就能保证至少有一个哲学家可以就餐。

    semaphore cpst[5]={1,1,1,1,1};
    semaphore count=4; // 设置一个count,最多有四个哲学家可以进来
    void ph(int i)
    {
    	while(true)
    	{
    		think();
    		P(count); //请求进入房间进餐 当count为0时 不能允许哲学家再进来了
    		P(cpst[i]); //请求左手边的筷子
    		P(cpst[(i+1)%5]); //请求右手边的筷子
    		eat();
    		V(cpst[i]); //释放左手边的筷子
    		V(cpst[(i+1)%5]); //释放右手边的筷子
    		V(count); //退出房间释放信号量
    	}
    }
    

    2、策略二

      仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。

    semaphore cpst[5]={1,1,1,1,1};
    semaphore mutex=1; // 这个过程需要判断两根筷子是否可用,并保护起来
    void ph(int i)
    {
    	while(true)
    	{
    		think();
    		P(mutex); // 保护信号量
    		P(cpst[i]); // 请求左手边的筷子
    		P(cpst[(i+1)%5]); // 请求右手边的筷子
    		V(mutex);
    		eat();
    		V(cpst[i]); // 释放左手边的筷子
    		V(cpst[(i+1)%5]); // 释放右手边的筷子
    	}
    }
    

    3、策略三

      规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则先拿起他右边的筷子,然后再去拿他左边的筷子。按此规定,将是1、2号哲学家竞争1号筷子,3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。

    semaphore cpst[5]={1,1,1,1,1};
    void ph(int i)
    {
    	while(true)
    	{
    		think();
    		if(i%2 == 0) //偶数哲学家,先右后左。
    		{
    			P(cpst[(i + 1)%5]) ;
    			P(cpst[i]) ;
    			eat();
    			V(cpst[(i + 1)%5]) ;
    			V(cpst[i]) ;
    		}
    		else //奇数哲学家,先左后右。
    		{
    			P(cpst[i]) ;
    			P(cpst[(i + 1)%5]) ;
    			eat();
    			V(cpst[i]) ;
    			V(cpst[(i + 1)%5]) ;
    		}
    	}
    }
    

    参考:https://blog.csdn.net/fuziwang/article/details/79809994
    https://www.cnblogs.com/edisonchou/p/5061886.html

    展开全文
  • 正如爱因斯坦所说:“从希腊哲学到现代物理学的整个科学史中,不断有人力图把表面极为复杂的自然现象归结为几简单的基本概念和关系。这就是整个自然哲学的基本原理。”这原理也贯穿了《数学之美》本身。 WWW的...

    以下内容摘录自:《数学之美》—吴军 第二版

    第一版序言
    牛顿是伟大的物理学家和数学家,他在《自然哲学的数学原理》中叙述了四条法则。其中有“法则1:除那些真实而已足够说明其现象者外,不必去寻找自然界事物的其他原因。”这条法则后来被人们称作为“简单性原则”。正如爱因斯坦所说:“从希腊哲学到现代物理学的整个科学史中,不断有人力图把表面极为复杂的自然现象归结为几个简单的基本概念和关系。这就是整个自然哲学的基本原理。”这个原理也贯穿了《数学之美》本身。
    WWW的发明人蒂姆•伯纳斯•李谈到设计原理时说过:“简单性和模块化是软件工程的基石;分布式和容错性是互联网的生命。

    P5
    随着文明的融合与冲突,不同文明下的人们需要进行交流,或者说通信,那么翻译的需求便产生了。翻译这件事之所以能达成,仅仅是因为不同的文字系统在记录信息上的能力是等价的。(这个结论很重要。)进一步讲,文字只是信息的载体而非信息本身。那么不用文字,而用其他的载体(比如数字)是否可以存储同样意义的信息呢?这个答案是肯定的,这也是现代通信的基础。

    P36
    一般来说,出现一次的词的数量比出现两次的多,出现两次的比出现三次的多。这种规律称为Zipf定律(Zipf’s Law)。

    P60
    一条信息的信息量与其不确定性有着直接的关系。比如说,我们要搞清楚一件非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。相反,如果对某件事了解较多,则不需要太多的信息就能把它搞清楚。所以,从这个角度来看,可以认为,信息量就等于不确定的多少。

    P62
    自古以来,信息和消除不确定性是相联系的。

    信息是消除系统不确定性的唯一办法(在没有获得任何信息前,一个系统就像是一个黑盒子,引入信息,就可以了解黑盒子系统的内部结构)
    信息是消除系统不确定性的唯一办法(在没有获得任何信息前,一个系统就像是一个黑盒子,引入信息,就可以了解黑盒子系统的内部结构)

    P71
    信息熵不仅是对信息的量化度量,而且是整个信息论的基础。它对于通信、数据压缩、自然语言处理都有很大的指导意义。信息熵的物理含义是对一个信息系统不确定性的度量,在这一点上,它和热力学中熵的概念有相似之处,因为后者就是一个系统无序的度量,从另一个角度讲也是对一种不确定性的度量。这说明科学上很多看似不同的学科之间会有很强的相似性。

    P74
    …首先,小学生和中学生其实没有必要花那么多时间读书,而他们的社会经验、生活能力以及那时树立起的志向将帮助他们的一生。第二,中学阶段花很多时间比同伴多读的课程,上大学以后用很短时间就能读完,因为在大学阶段,人的理解力要强得多。举个例子,在中学需要花 500 小时才能学会的内容,在大学可能花 100 小时就够了。因此,一个学生在中小学建立的那一点点优势在大学很快就会丧失殆尽。第三,学习(和教育)是持续一辈子的过程,很多中学成绩优异的亚裔学生进入名校后表现明显不如那些出于兴趣而读书的美国同伴,因为前者持续学习的动力不足。第四,书本的内容可以早学,也可以晚学,但是错过了成长阶段却是无法补回来的。…

    P92
    网络爬虫
    …图论的遍历算法和搜索引擎的关系。互联网虽然很复杂,但是说穿了其实就是一张大图而已 —— 可以把每一个网页当作一个节点,把那些超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注意到,网页中那些带下划线的蓝色文字背后其实藏着对应的网址,当你点击时,浏览器通过这些隐含的网址跳转到相应的网页。这些隐含在文字背后的网址成为“超链接”。有了“超链接”,我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫(Web Crawlers)。…

    展开全文
  • SDN到底是什么

    千次阅读 2014-02-14 16:48:22
    SDN到底是什么?虽然这个概念已经被炒到了,但还没有人对其给出一明确的...SDN的概念从提出到现在已经过了4年多了,但是关于SDN最基本的问题,“什么是SDN”的争论和探讨从来都没停止过,就像一些哲学家经常思考的
  • SDN到底是什么?虽然这个概念已经被炒到了,但还没有人对其给出一明确的...SDN的概念从提出到现在已经过了4年多了,但是关于SDN最基本的问题,“什么是SDN”的争论和探讨从来都没停止过,就像一些哲学家经常思考的
  • [Scala]001-初识

    2019-05-07 17:13:47
    01、基本概念 1)多范式:多种编程方法。目前有种程序设计方法:面向过程、面向对象、函数式、泛型。 编程范式(programming paradigm(范例、样式、典范)),是指计算机编程的基本风格或典范模式。借用哲学术语...
  • 架构设计方法学

    2019-02-22 16:33:06
    架构设计的方法学 约公元前25年,古罗马建筑师维特鲁威说:“理想...一、与构架有关的几个基本概念;  二、构架设计应考虑的因素概揽;  三、程序的运行时结构方面的考虑;  、源代码的组织结构方面的考虑; ...
  • 本文的主要目的是通过介绍人工智能伦理中的基本概念和草图方法以及中心主题,提供对该领域的高级概述。 第一部分介绍术语的基本定义,即定义“人工智能”和“伦理”等; 第二部分探讨了人工智能伦理学的一些前身,...
  • 约公元前25年,古罗马建筑师维特鲁威说:...) 本文目录 一、与构架有关的几个基本概念; 二、构架设计应考虑的因素概揽; 三、程序的运行时结构方面的考虑; 、源代码的组织结构方面的考虑; 五、写系统构架设计...
  • windows下TCP的socket编程

    2020-11-28 14:31:14
    socket起源于Unix,而Unix/Linux基本哲学之一就是“一切皆文件”,都可以用“打开open –> 读写write/read –> 关闭close”模式来操作。我的理解就是Socket就是该模式的一实现,socket即是一种特殊的文件,...
  • 如果你是敏捷的新手,你可能充斥着大量的信息:相互竞争的解释; 矛盾的建议; 各种方法/方法的提案...由17位希望提出轻量级软件开发新方法的软件开发人员撰写,“敏捷软件开发宣言”简单地阐述了新哲学四个价值观...
  • 本书共分四大部分,第一部分分析了建筑是什么这个基本哲学问题,批驳了建筑和城市理论过于注重规范而忽视了分析;第二部分基于空间句法理论,提出了一个城市建筑的科学范式;第三部分详细地阐述了建筑和城市空间...
  • 重点: 发生死锁的四个条件,死锁预防、避免和检测方法 难点:银行家算法 第7章内存管理 详细解释内存管理的基本机制,介绍内存分区的方法,以及内存管理系统中基本构造块的两种技术:分页和分段。 重点: 内存分区...
  • 新奇之路-研究论文

    2021-06-10 05:14:31
    为了便于特定学科的材料访问以及结果的分析,在通往新颖之路的第三、第和第五部分中,我们将 CoIn关于哲学和语言理论以及计算机科学/人工智能,最后是逻辑/数学中的承认的讨论的思想史方法。 除了已经提到的命题...
  • 虽然超人类主义的立场可能看起来很激进,但本文认为应该认真对待超人类主义医学项目,因为它的基本哲学已经融入北美主流健康研究议程,导致最近转向“增强”医学。 在第一部分,作者简要概述了超人类主义的核心原则...
  • 步:基本原理:生成正确的电压电平 现在我们已经发现了什么样的电压水平,我们的VFD管需要正常工作,现在是时候确保我们从基本电源电压产生他们,比如5V。(5V是电子爱好者最常用的电压)。这想法:降压和升压...
  • 跟老齐学Python-最新版

    2017-12-25 09:54:50
    8.3.2 一个基本架势 337 8.3.3 连接数据库 340 8.3.4 登录界面 340 8.3.5 数据传输 345 8.3.6 数据处理 347 8.3.7 模板 350 8.3.8 转义字符 355 8.3.9 模板继承 357 8.3.10 CSS 358 8.3.11 cookie和安全 359 8.3.12 ...
  • 一般说来 建立一研究领域 指的是一种系统分析,或多或少地建立 其最基本的或基础的概念、其概念的一致性、以及其概念的本性顺序或层次结构;这可以有助于 将其与其它人类知识 联系起来。但是在一领域的历史上,...
  • 这两章的目的是促使你在基础性概念基本语言特征上用一些时间,在这里展示了利用完整的C++语言可以描述些什么。即使没有其他内容,这两章也会使你确信C++并不(只)是C,而且,在本书的第1版和第2版之后,C++已经走过了很...
  • 讲解Linux网络编程知识,分以下四个篇章。 Linux网络编程之TCP/IP基础篇 Linux网络编程之socket编程篇 Linux网络编程之进程间通信篇 Linux网络编程之线程篇 Linux网络编程之TCP/IP基础篇 01TCPIP基础(一) ...
  • 讲解Linux网络编程知识,分以下四个篇章。 Linux网络编程之TCP/IP基础篇 Linux网络编程之socket编程篇 Linux网络编程之进程间通信篇 Linux网络编程之线程篇 Linux网络编程之TCP/IP基础篇 01TCPIP基础(一) ...

空空如也

空空如也

1 2 3
收藏数 46
精华内容 18
关键字:

哲学四个基本概念