任意命题公式的真值表

第二节 命题公式及其真值表在上节中，用,,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=2”、“苹果是红色的”等都是命题。

在数理逻辑中，命题通常用字母p、q、r等来表示。

命题公式是由命题符号和逻辑符号组成的符号串。

命题符号表示命题，逻辑符号表示命题之间的关系。

逻辑符号包括非（）、合取（∧）、析取（∨）、条件（→）、双条件（）等。

例如，p∧q表示p和q都为真时，整个命题为真。

二、真值表法的基本原理真值表法是用来判断命题公式真假性的一种方法。

它的基本原理是列出所有可能的命题符号取值组合，并按照逻辑符号的运算规则计算出整个命题的真值。

真值表的每一行对应一个命题符号取值组合，最后一列为整个命题的真值。

例如，对于命题公式p∨q，可以列出如下的真值表：p q p∨q----------------T T TT F TF T TF F F其中，T表示真，F表示假。

在该真值表中，第一列和第二列分别代表p和q的取值，第三列代表整个命题的真值。

在第一行中，p 和q都为真，所以整个命题为真。

三、真值表法的应用真值表法可以用来判断任意命题公式的真假性。

下面以两个例子来说明其应用。

例一：判断(p→q)∧(q→p)是否为重言式。

首先，列出该命题公式的真值表：p q p q p→q q→p (p→q)∧(q→p)--------------------------------------------------------T T F F T T TT F F T F F FF T T F T T TF F T T T T T在该真值表中，最后一列的值都为真。

因此，该命题公式是重言式。

例二：判断(p∨q)→(p∧q)是否为永假式。

首先，列出该命题公式的真值表：p q p∨q p∧q (p∨q)→(p∧q)------------------------------------T T T T TT F T F FF T T F FF F F F T在该真值表中，最后一列的值都不为假。

求给定命题公式的真值表并根据真值表求公式的主范式(求给定命题公式的真值表并根据真值表求公式的主范式)专业网络工程班级 1202班学号 12407442姓名张敏慧2013.12.14目录一.实验目的 .......................................................3二.实验内容 (3)求任意一个命题公式的真值表 ..................................................................... ..... 3 三.实验环境 (3)四. 实验原理和实现过程(算法描述) (3)1.实验原理 ..................................................................... ...................................... 3 2.实验流程图 ..................................................................... .................................. 5 五.实验代码 (6)六. 实验结果 (14)七. 实验总结 (19)- 1 -一.实验目的本实验课程是网络工程专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算;通过实验提高学生编写实验报告、总结实验结果的能力;使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

熟悉掌握命题逻辑中的真值表、主范式等，进一步能用它们来解决实际问题。

二.实验内容求任意一个命题公式的真值表，并根据真值表求主范式详细说明:求任意一个命题公式的真值表本实验要求大家利用C/C，，语言，实现任意输入公式的真值表计算。

一般我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。

1、给出命题公式P→Q的真值表。

答：2、写出命题公式P→Q∨R的主合取范式。

3、证明下列结论的有效性。

(1) A→B，┐（B∨C）⇒┐A(2)(∀x)(C(x) →W(x) ∧R(x)) ∧(∃x)(C(x) ∧Q(x))⇒(∃x)(Q(x) ∧R(x))4、证明┐（B↑C）⇔┐B↓┐C。

5、证明对任意集合A、B、C，有(A-B)-C=(A-C)-(B-C)。

6、设偏序集为<ρ{0,1,2},⊆>，试求出其盖COV(ρ{0,1,2})并画出偏序关系的哈斯图。

7、写出ρ（ρ（φ））的幂集。

8、将下列命题用命题公式符号化。

(1)我们不能既划船又跑步。

(2)或者你没有给我写信，或者信在途中丢失了。

9、用谓词公式符合化下列命题并推证其结论的有效性。

所有有理数是实数，有些有理数是整数，因此有些实数是整数。

10、设集合A={a，b，c}，求R={<a,b>}的r(R)、s(R )与t(R)。

11、设集合A={a，b，c}，R和S为A上的二元关系：R={<a,b>,<a,c>}，S＝｛<b,b>,<b,c>}，求出：R︒S及S︒R。

（其中：︒表示两个关系的复合）12、设|A|=m，|B|=n，则A⨯B、A⨯B的幂集各有多少个元素、从A到B的关系各有多少个？13、证明集合[0，1]与集合(0，1)是等势的。

14、设A有n个不同的元素，R是A上的一个关系，则必存在i，2j使R i=R j，其中0≤i<j≤2n。

15、设集合A为可数集，证明：集合A⨯A也必为可数集。

16、不构造双射映射证明集合[0，1]与集合(4，∞)是等势的。

离散结构命题公式及真值表教学目标基本要求（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)。

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

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

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

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

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

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

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

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

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

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

用真值表法判断命题公式命题公式是数理逻辑中的基本概念，它是由命题符号和逻辑连接词组成的符号串，用于表示命题之间的逻辑关系。

在数理逻辑中，我们通常使用真值表法来判断命题公式的真假性。

本文将介绍真值表法的基本概念和应用。

一、真值表的定义和构造方法真值表是一种用来表示命题公式真假性的表格。

一般地，真值表的每一行代表了命题符号的一种取值情况，真值表的最后一列代表了整个命题公式的真假情况。

真值表的构造方法可以按照以下步骤进行： 1. 确定命题符号的取值情况，例如，若有命题符号P和Q，则可以分别取真和假两种情况，得到四种可能的取值情况：P=T,Q=T;P=T,Q=F;P=F,Q=T;P=F,Q=F。

2. 根据命题公式中的逻辑连接词，计算出整个命题公式在每种取值情况下的真假情况。

例如，若命题公式为P∨Q，则在第一行的情况下，P∨Q的真假情况为真；在第二行和第三行的情况下，P∨Q的真假情况为真；在第四行的情况下，P∨Q的真假情况为假。

3. 将每种情况下的真假情况填入真值表中，得到完整的真值表。

二、真值表法的应用真值表法可以用来判断命题公式的真假性，以及推导命题公式的逻辑等价式。

下面将分别介绍这两种应用。

1. 判断命题公式的真假性通过真值表法，我们可以得到命题公式在所有可能情况下的真假情况，从而判断命题公式的真假性。

如果在所有情况下，命题公式都为真，则该命题公式为重言式；如果在所有情况下，命题公式都为假，则该命题公式为矛盾式；如果在某些情况下，命题公式为真，而在其他情况下，命题公式为假，则该命题公式为可满足式。

例如，对于命题公式P∨P，可以通过真值表法判断其为重言式，因为在所有情况下，命题公式都为真。

2. 推导命题公式的逻辑等价式通过真值表法，我们还可以推导命题公式的逻辑等价式。

两个命题公式是逻辑等价的，当且仅当它们在所有情况下的真假情况完全相同。

因此，如果两个命题公式在真值表中的真假情况完全相同，则它们是逻辑等价的。