形式逻辑
形式逻辑
快速的事实
媒体
更多的

命题演算

PC机的基本特点

的最简单和最基本的分支逻辑是命题演算它以后称为PC，之所以这样命名是因为它只处理完整的、未经分析的命题以及它们所进入的某些组合。文献中使用了不同的PC符号。这里使用的符号首先在PC中使用组成变量(其中字母p，问，r，…被使用，带或不带数字下标);第二,运营商(使用符号∼、·、∨、⊃和≡);第三，括号或圆括号。构造公式的规则讨论如下(见下文PC的形成规则)，但这些符号的意图解释，即。，the meanings to be given to them—are indicated here immediately: the variables are to be viewed as representing unspecified propositions or as marking the places in formulas into which sentences, and only sentences, may be inserted. (This is sometimes expressed by saying that variables range over propositions, or that they take propositions as their values.) Hence they are often called命题变量。它假定每个命题不是真就是假，没有命题既真又假。真理而且虚伪据说是真值的命题。算子的功能是由一个或多个给定命题形成一个新的命题，称为操作符的参数。算子∼、·、∨、⊃和≡分别对应于英文表达式“not”、“and”、“or”、“if…，then”(或“implies”)和“is equivalent to”，在以下情况下使用:

  1. 给定一个命题p，然后∼p(“不p，当p真真假假是什么时候p是假的;“∼”(当这样解释时)被称为 否定Sign，和~p作为…的否定p．
  2. 给定任意两个命题p而且问,然后p·问(“p而且问，当p而且问在所有其他情况下(即，当p是真的问假的,当p是假的问真的，当p而且问都是假的);p·问据说是 结合的p而且问；“·”被称为结合符号及其参数(p，问)作为连词。
  3. 给定任意两个命题p而且问,然后p∨问(“p或问，当p而且问在所有其他情况下都是假的和真的;因此，它表示至少有一个的断言p而且问是真的。P∨问被称为 析取的p而且问；“∨”是析离符号，其参数(p，问)被称为析取词。
  4. 给定任意两个命题p而且问,然后p⊃问(“如果p(然后)问或"p［ 物质上)意味着问，当p是真的问为假，在所有其他情况下均为真;因此它与“either not-”有相同的意思p或问或“两者皆非”p而不是,问符号“⊃”被称为(材料)含义第一个符号论点随着 先行词，第二为 顺向；问⊃p被称为匡威的p⊃问．
  5. 最后,p≡问(“p(物质) 等效来问或"p当且仅当问，当p而且问具有相同的真值(即当两者都为真或都为假时)，当它们具有不同的真值时为假;“≡”([material]等价符号)的参数称为等价。

括号用来表示分组;例如，它们使得区分p·(问∨r)(“两p和- - - - - -问或者,r”)及(p·问)∨r(“要么-p- - - - - - -问或r”)。精确的规则夹叉射击如下所示。

所有PC运算符都以命题为参数，应用命题的结果在每种情况下也是命题。由于这个原因，它们有时被称为命题上的命题形成算子，或者更简单地说，命题连接词．像∼这样只需要一个参数的操作符称为a一元操作符；与列出的所有其他操作符一样，需要两个实参的操作符称为二元。

所有PC操作符也有以下重要的特点:给定真值在各种情况下，由它们和算子构成的命题的真值是确定的。一个有这个的算子特征被称为truth-functional运营商，由这样一个算子构成的命题称为a运算符参数的真值函数。通过对计算机操作员的上述描述的总结，清楚地揭示了计算机操作员的真实功能点击这里查看全尺寸表格大多数常用运算符的真值表表1。其中，“true”缩写为“1”，“false”缩写为“0”，垂直线左侧列出了运算符参数真值的所有可能组合。各种真值函数下的1和0列表示每种情况下的真值;这些列被称为真值表相关的运算符。应该注意的是，任何4个1或0或两者都有的列将指定一个二元真函数运算符。因为正好有2个4(即16种)构成由4个符号组成的字符串的方法，每个符号都是1或0(11111,1110,1101，…，0000)，总共有16种这样的运算符;这里列出的四种只是最常用的四种。

形成的规则个人电脑

在任何逻辑系统中，都有必要指定哪些符号序列可以算作可接受的公式，或者，正如它们通常被称为，格式良好的公式(wffs)。指定这一点的规则称为形成规则。从一个直观的从这个角度来看，PC的wff应该是PC符号的序列，根据上面给出的解释，这些序列是有意义的并且是明确的;这可以通过规定PC的wff是根据以下PC形成规则构造的所有表达式来保证，并且只有这些表达式:

  • FR1。单独存在的变量是wff。
  • FR2。如果α是wff，那么∼α也是wff。
  • FR3。如果wffsα和β,(α·β),(α,β),(α∨β),(α⊃β),和(α≡β)wffs。

在这些规则中α和β是变量表示任意的PC公式。它们本身并不是PC的符号，而是用来讨论PC的。这样的变量被称为元逻辑变量。应该指出的是，虽然这些规则的设计是为了确保在预期的解释下对PC的wffs有明确的意义，但它们本身并没有提到任何解释，并且以这样一种方式存在在没有任何解释的情况下，确定任意符号串是否是WFF的有效程序。有效的程序本质上是“机械的”，总是可以依靠它在工作中给出明确的结果有限的步骤数。有效性的概念在形式逻辑中起着重要的作用。

wffs的例子有:p；∼问；∼(p·问),即:，“not bothp而且问”;和[∼p∨(问≡p)即:，“either notp否则问等于p．”

为了更方便地书写或阅读公式，通常会放宽构成规则。以下是常见的松弛形式:(1)括住完整公式的括号可以省略。(2)方括号的排版风格可以在公式中有所变化，以使方括号的搭配更明显。（3）连词析取可以有两个以上的参数，例如，p·(问⊃r)·∼r可以写成[p·(问⊃r·∼r．(结合p·问·r那么是这样解释的吗p，问,r都是真的，p∨问∨r意思是至少有一个p，问,r是真的，等等。)

有效性在个人电脑

根据标准的解释，PC的wff变成了一个句子，无论是真还是假，当它的所有变量都被实际的句子取代时。这样的wff因此是上述意义上的命题形式，因此当且仅当它的所有实例都表达了真命题时才有效。一个所有实例都为假的wff是不能满足的，一个既有一些真实例又有一些假实例的wff是不能满足的或有．

对于任何逻辑系统来说，一个重要的问题是决策问题对于该系统的有效WFFS的类别(有时简单地称为系统的决策问题)。这是一个寻找有效程序的问题，在上一节解释的意义上，用于测试系统的任何wff的有效性。这样的过程称为决策过程。对于某些系统，可以找到一个决策程序;这样一个系统的决策问题就被称为是可解的，这个系统就被称为可决定的一个。对于其他系统，可以证明没有决策程序是可能的;这样一个系统的决策问题就被称为不可解的，而这个系统就被称为不可定的。

PC是一个可决定的系统。事实上，有几种决策程序是已知的。在这些方法中，理论上最简单和最重要的(尽管在实践中并不总是最容易应用的)是方法真值表，现在将作简要解释。由于PC的wff中的所有操作符都是真函数，为了发现真值对于任何这样的例子，除了事实之外，没有必要考虑其他事情值替换变量的句子。换句话说，给wff中的每个变量赋一个真值唯一地决定了整个wff的真值。由于只有两个真值，每个wff只包含有限个变量，所以只有有限个真实价值要考虑的变量的赋值(如果有的话)nwff中有2个不同的变量n这样的作业);这些可以很容易地系统地制成表格。对于每一种赋值，运算符的真值表可以计算出结果的真值价值整个wff的;当且仅当该真值在每种情况下为真时，WFF是有效的。例如，[(p⊃问)·r]⊃[(∼r∨p)⊃问]可以测试其有效性。这个公式指出:“如果一个命题包含了第二个命题，并且某个第三个命题为真，那么如果第三个命题为假，或者第一个命题为真，那么第二个命题为真。”

计算结果如点击这里查看全尺寸表格用真值表检验有效性表2。和前面一样，1代表真实，0代表虚假。由于wff包含三个变量，所以有2个3.(即，8)对要考虑的变量的不同赋值，因此生成表的8行。这些作业是列表在垂直线的左边。末尾括号中的数字表示在确定要输入到表中的真值(1或0)时所采取的步骤(从1到6)的顺序。因此，第1列(位于符号⊃之下)设置了的值p⊃问对于每个作业，从下面的列中获得p而且问由真值表⊃;第2列，用于(p⊃问)·r，则将第1列的值与下一列的值结合得到r利用真值表对·;直到最后第6列，它给出了整个wff的值，是从第2列和第5列获得的。这一列叫做整个wff的真值表。由于它完全由1组成，它表明wff对变量的每个赋值都是正确的，因此是有效的。真值表完全由0组成的wff是不满足的，真值表包含至少一个1和至少一个0的wff是不满足的或有．根据形成规则和为每个运算符指定了初始真值表的事实，可以为PC的任何给定wff构造真值表。

在PC中更重要的有效wffs是那些点击这里查看全尺寸表格命题演算的一些有效公式表3，所有这些都可以通过机械地应用真值表方法来证明是有效的。它们也可以直观地表达关于命题的合理的一般原则。例如，因为“not(…or…)”可以被改写为“neither…nor…”，第一个德摩根法律可以理解为“两者皆有”p而且问当且仅当两者都不-p也不是,问”;因此，它表达了这样一个原则:当且仅当两个命题都不为假时，它们合为真。无论何时，就像在给出的大多数例子中一样，形式为α≡β的wff是有效的，相应的wff α⊃β和β⊃α也是有效的。例如，因为(p·问≡∼(∼。p∨∼问)有效，(也是有效的。p·问)⊃∼(∼p∨∼问)和∼(∼p∨∼问)⊃(p·问)．

此外,尽管p⊃问并不意味着问可以从p，但只要α⊃β形式的WFF是有效的，则推理形式“α，因此β”同样有效。这一事实很容易从α⊃β意味着“不是两者:α和不是-β”这一事实看出;因为，如上所述，只要后者是一个有效的命题形式，“α，因此β”是有效的推理的形式。

设α为任意wff。如果其中的任何变量现在被某个wff均匀地替换，则生成的wff称为asubstitution-instanceα。因此,(p⊃(问∨∼r)]≡[∼(问∨∼r)⊃∼p是(的替换实例)p⊃问≡(∼)问⊃∼p)，由替换而得问统一由(问∨∼r)．这是一个重要的原则，只要wff是有效的，那么它的每个替换实例也是有效的([uniform]的规则替换)．

另一个重要的原则是等价物代换法则．两个wffs， α和β，被称为等价物当α≡β有效时。(wffs α和β当且仅当它们具有相同的真值表时是等价的。)该规则规定，如果wff的任何部分被该部分的等价物替换，则生成的wff与原始wff也是等价的。这种替换不需要是统一的。这条规则的应用被认为是一个等效变换。