实验二-命题公式的等值演算与真值表

第二节 命题公式及其真值表在上节中，用,,p q r L 表示确定的简单命题。

简单命题又称为命题常项或命题常元。

命题常项有确定的真值。

在数理逻辑中，不仅要研究具体的逻辑关系，还要研究抽象的逻辑关系，因而不仅要有命题常项，还要有命题变项。

称真值可以变化的简单陈述句为命题变项或命题变元，仍然用,,p q r L 表示命题的变项。

命题常项、命题变项及联结词可按下述定义合式的公式。

定义2.1 （1）单个的命题变项（或常项）是合式公式；（2）若A 是合式公式，则（¬A ）也是合式公式；（3）若A ，B 是合式公式，则（A ∧B ），（A ∨B ），（A →B ），（A ↔B ）也是合式公式；（4）有限次地应用（1）～（3）形成的符号串都是合式公式。

这样定义的合式公式也称为命题公式，简称公式。

单独使用（¬A ），（A ∧B ），（A ∨B ），（A →B ），（A ↔B ）时，外层括号可以省去，即可写成¬A ，A ∧B ，A ∨B ，A →B ，A ↔B 。

在定义 2.1.中出现的A ，B L 是用来表示任意的合式公式的。

在以下的论述中出现的A ，B ，C 等也同样是用来表示任意公式的。

定义2.2 设1p ，2p L ，n p 是出现在公式A 中的全部的命题变项，给1p ，2p L ，np 各指定一个真值，称为A 的一个赋值或解释。

若指定的一组真值使A 的真值为1，则称这组真值为A 的成真赋值（或成真解释）。

若指定的一组真值使A 的真值为0，则称这组真值为A 的成假赋值（或成假解释）。

本书中对含n 个命题变项的公式的赋值形式做如下规定：（1）设A 中含的命题变项为1p ，2p L ，n p ，赋值12n a a a L （i a 为0或1）是指11p a =，22p a =，L ，n n p a =。

（2）若出现在A 中的命题变项为p ，q ，r ，L ，赋值12n a a a L 是指1p a =，2q a =，L ，即按字典顺序赋值。

命题的逻辑运算与真值表逻辑运算是数理逻辑中的一个重要概念，它描述了命题之间的关系和推理规则。

命题是一个陈述句，可以被判断为真或假。

本文将介绍命题的逻辑运算及其真值表。

一、基本逻辑运算基本逻辑运算包括与运算（∧）、或运算（∨）和非运算（¬）。

1.1 与运算（∧）与运算表示两个命题同时为真时，整个逻辑表达式才为真。

符号为"∧"。

例如，命题P为"我喜欢游泳"，命题Q为"今天是晴天"，则"我喜欢游泳∧今天是晴天"表示我只有在今天是晴天的时候才喜欢游泳。

1.2 或运算（∨）或运算表示两个命题中至少有一个为真时，整个逻辑表达式才为真。

符号为"∨"。

例如，命题P为"我喜欢游泳"，命题Q为"今天是晴天"，则"我喜欢游泳∨今天是晴天"表示我不管今天是不是晴天，只要我喜欢游泳就为真。

1.3 非运算（¬）非运算表示对命题的否定。

如果一个命题为真，则其否定为假；如果一个命题为假，则其否定为真。

符号为"¬"。

例如，命题P为"我喜欢游泳"，则"¬我喜欢游泳"表示我不喜欢游泳。

二、复合逻辑运算在基本逻辑运算的基础上，可以进行复合逻辑运算，包括蕴含（→）、等价（↔）和异或（⊕）。

2.1 蕴含运算（→）蕴含运算表示如果前提为真，则结论也为真。

符号为"→"。

例如，命题P为"如果下雨，那么我会带雨伞"，命题Q为"下雨了"，则"P→Q"表示如果下雨了，那么我会带雨伞。

2.2 等价运算（↔）等价运算表示两个命题具有相同的真值，当且仅当两个命题的真假相同时，整个逻辑表达式为真。

符号为"↔"。

离散逻辑学实验班级：10电信实验班学号：Q10600132 姓名：王彬彬一、实验目的熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

二、实验内容1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。

（A）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C））三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）1.实验原理（1）合取：二元命题联结词。

将两个命题P、Q联结起来，构成一个新的命题P∧Q, 读作P、Q的合取, 也可读作P与Q。

这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可P∧Q =T, 而P、Q只要有一为F则P∧Q = F。

这样看来，P∧Q可用来表示日常用语P与Q, 或P并且Q。

（2）析取：二元命题联结词。

将两个命题P、Q联结起来，构成一个新的命题P∨Q, 读作P、Q的析取, 也可读作P或Q。

这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可P∨Q =F, 而P、Q只要有一为T则P∨Q = T。

这样看来，P∨Q可用来表示日常用语P或者Q。

（3）条件：二元命题联结词。

将两个命题P、Q联结起来，构成一个新的命题P→Q, 读作P条件Q, 也可读作如果P，那么Q。

这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = F时方可P→Q =F, 其余均为T。

（4）双条件：二元命题联结词。

将两个命题P、Q联结起来，构成一个新的命题P←→Q, 读作P双条件于Q。

这个新命题的真值与构成它的命题P、Q的真值间的关系为当两个命题变项P = T, Q =T时方可P←→Q =T, 其余均为F。

（5）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。

列出命题公式真假值的表。

通常以1表示真，0 表示假。

离散结构命题公式及真值表教学目标基本要求（1）会判断命题公式及其层次；（2）真值表；（3）公式类型；重点难点真值表的应用。

命题中的符号命题中的符号：(1) 命题常元：真值唯一确定。

例如：T、F(2) 命题变元：真值可变化。

例如：P、Q、R(3) 联接词：优先级按¬, ∧, ∨, →, ↔递减(4) 辅助符号如括号（）。

命题中的符号任意组成的符号串是否都有意义？例：(∧p ¬q) pq →(思考：按什么规律组成的符号串才有意义？合式公式合式公式：合法的命题公式。

（简称公式）（1）命题常元或变元是合式公式（2）若A, B是合式公式，(¬A),(A∧B),(A∨B),(A→B),(A↔B)也是合式公式（3）只有有限次地应用(1)、(2)形成的符号串才是合式公式注意这个定义是递归的。

(1)是递归的基础，由(1)开始，使用规则(2)，可以得到任意的合式公式。

公式简写的约定1) 最外层括号可以省略；2) 省略括号后, 运算顺序与联结词的优先级一致，则可以省略；3) 相同联结词按从左到右的顺序计算，则可以省略。

公式的层次定义：（1）若公式A 是单个的命题变项，则称A 为0层公式。

（3）若公式的层次为k ，则称A 是k 层公式。

（2）若有下面情况之一的，称A 为n+1层公式:A 是¬B ，B ∧C ，B ∨C ，B→C ，B↔C ，其中B 、C 分别是i 层、j 层公式，且n=max(i,j)； 例：((¬p ∧q)∨(p ∧ ¬q))→r1层 2层 3层 4层公式的解释命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定值，成为命题。

解释（I）：给公式A（ P1，P2，…,Pn ）中的命题变元P1，P2，…,Pn指定一组真值称为对A的一个解释（赋值）。

成真赋值: 使公式为真的赋值。

成假赋值: 使公式为假的赋值。

用真值表法判断命题公式真值表法是一种常用的推理方法，用于判断命题公式的真假。

它通过列出所有可能的真假组合来确定命题公式的真值。

在进行真值表法判断时，首先需要确定命题公式中所有的命题变量。

命题变量是命题公式中可以取真或假的变量。

然后，列出所有可能的真假组合，并依次代入命题公式，以确定每种组合下命题公式的真值。

举个例子，假设我们有一个命题公式为p∨(¬q∧r)，其中p、q和r是命题变量。

那么我们可以列出如下的真假组合：p，q，r，¬q，(¬q∧r)，p∨(¬q∧r):-----:，:-----:，:-----:，:--:，:------:，:----------:真，真，真，假，假，真真，真，假，假，假，真真，假，真，真，真，真真，假，假，真，假，真假，真，真，假，假，假假，真，假，假，假，假假，假，真，真，真，真假，假，假，真，假，假通过代入每种组合，我们可以得出该命题公式的真值表。

从真值表中可以看出，该命题公式在p为真，或(¬q∧r)为真时，整个命题公式为真。

因此，该命题公式可以表示为p∨(¬q∧r)。

这就是真值表法判断命题公式的基本过程。

在进行真值表法判断时，我们还可以利用真值表的特点来推导命题公式的等价关系、重言式、矛盾式等。

例如，如果我们得出一个真值表中的其中一列的值全为真，那么可以得出该命题公式是一个重言式。

如果其中一列值全为假，那么命题公式是一个矛盾式。

真值表法的优点是能够准确地判断命题公式的真假，而不受语义混淆的干扰。

然而，对于较复杂的命题公式而言，真值表法的计算量可能非常庞大，因为需要列出所有可能的真假组合。

在这种情况下，可以考虑使用其他推理方法，如逻辑推理、等价转换、命题演算等来简化问题。

综上所述，真值表法是一种能够准确判断命题公式真假的常用推理方法。

它通过列出所有可能的真假组合，代入命题公式，来确定命题公式的真值。

真值表法可以用于推导命题公式的等价关系、重言式和矛盾式，并且可以用于简化复杂的命题公式。

实验报告实验名称：任意命题公式的真值表实验目的与要求：通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，包括联结词、真值表、运算的优先级等，提高学生编写实验报告、总结实验结果的能力，培养学生的逻辑思维能力和算法设计的思想，能够独立完成简单的算法设计和分析，进一步用它们来解决实际问题，帮助学生学习掌握C/C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。

实验内容提要：求任意一个命题公式的真值表实验步骤：（一）、关于命题公式的形式和运算符（即联结词）的运算首先根据离散数学的相关知识，命题公式由命题变元和运算符（即联结词）组成，命题变元用大写字母英文表示（本次试验没有定义命题常元T和F，即T、F都表示命题变元），每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。

目前离散数学里用到的包括扩充联结词总共有九种，即析取（或）、合取（与）、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。

所以本次实验设计时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“>”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。

以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元：1．非，用“/”表示2．合取（与），用“*”表示3．析取（或），用“+”表示4.蕴含，用“>”表示5.等值，用“:”表示（二）、命题公式真值的计算对于人来说，计算数学表达式时习惯于中缀表达式，例如a*b+c，a*（b+c）等等，而对于计算机来说，计算a*b+c还好，计算a*（b+c）则困难，因为括号的作用改变了运算的顺序，让计算机识别括号而改变计算顺序显得麻烦。