谓词公式-浙江大学计算机学院

具体的谓词。
2018/10/5
计算机学院
9
注：定义中所谓指定一个具体函数，即是对 每组可能的变量值给出函数的对应值；所谓 指定一个具体的谓词，就是对每组可能的客 体变元取值给出谓词的对应值， 1 表示逻辑
真，0表示逻辑假。
2018/10/5
计算机学院
10
含有量词的公式的解释
对于含有量词的公式的解释，需要根据量 词的逻辑意义来决定公式的值。 设论域 D={a1,a2, …，an} 1）（x)P(x) P(a1) ∧ P(a2) ∧…∧P(an) 表示公式（ x)P(x) 值为 1“ 当且仅当”对 论域D中每个元素a， P(a)的值为1。 2）（x)P(x) P(a1) ∨ P(a2) ∨…∨P(an) 表示公式（x)P(x)值为0“当且仅当”对论 域D中每个元素a，P(a)的值为0（或在论域D中 至少存在一个元素a，使P(a)的值为1）。
2018/10/5 计算机学院 4
一、谓词的合适公式
定义2.6 谓词逻辑中的,项被递归地定义为： 1）任意的常量符号是项；
2）任意的个体变元符号是项；
3）若f(x1,x2,x3,…,xn)是n元函数符号，
t1,t2,t3,…,tn是项，则f(t1,t2,t3,…,tn)
是项；
4）只有有限次使用1）～3）产生的符号串才
2018/10/5
计算机学院
3
四类符号
常量符号：一般用 a,b,c,… ； a1,b1,c1,… 来表示，它
可以是D中的某个元素; 变量符号：一般用 x,y,z,…, x1,y1,z1,… 来表示 . 它 可以取值于D中的任意元素； 函数符号：一般用 f,g,h,…, f1,g1,h1,… 来表示。 n 元函数符号 f(x1,x2,...xn) 可以是 Dn→D的任意一个函 数； 谓词符号：一般用P,Q,R,..., P1,Q1,R1,...来表示。 n元谓词符号P(x1,x2,...xn)可以是Dn→{0,1}的任意一 个谓词。 注：不含变元的函数是常量； 不含客体变元的谓词是命题。

T
所以
T
xA(x)∨xB(x) x(A(x)∨B(x))
F
F
xA(x)∨xB(x) → x(A(x)∨B(x))
此处取T亦可
例(续前)：试判断xA(x)∨xB(x) → x(A(x)∨B(x))是否是永真式，并说明理由。
总的思路：试图在D={1,2}上找到一个使所给公式为假的解释。 注意：以前进行运算都是根据形成过程由里往外逐次进行的，但这里的过程正好相反：自顶向下逐步推演。 在推演过程中，首先考虑以下事实： 若是上述五种情况之外的情况，则利用D中元素的对称性避免讨论。
例
取解释I如下：
D={1,2}, 定义D上的二元谓词P真值为 P(1,1): T； P(1,2): F； P(2,1):F； P(2,2): T 则xyP(x,y)和yxP(x,y) 在解释I下的真值分别为?
T
F
T
T
关于x的一元函数
xyP(x,y)
P(x,y)
T
yP(x,y)
T
xyP(x,y)
F
T
F
F
F
F
F
T
2
1
2
2
1
1
yx P(x,y)
xP(x,y)
P(x,y)
x
y
关于y的一元函数
yxP(x,y)
取解释I如下： D={1,2}, 令 a:1, f(1)=2, f(2)=1 定义D上的谓词P和Q为 P(1): F； P(2): T； Q(1,1):T； Q(1,2):T； Q(2,1):F； Q(2,2): F 求谓词公式x(P(x)→Q(f(x),a))在解释I下的真值
8
单击此处添加大标题内容
量词对及→的处理 x(A(x)→B(x))xA(x)→xB(x) xA(x)→xB(x)x(A(x)→B(x)) 证明1. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x)) 证明2. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x))

安徽大学计算机学院2010 —20 11 学年第 1 学期《离散数学---数理逻辑部分》测试试卷院/系 计算机 年级 09 专业 计算机科技 姓名 倪晨 学号 E10914029一、填空题（每小题1分，共16分）1、 判断下列公式的类型① (P Q)( P Q R)∨⌝→⌝∧∧是 偶然 式；② (Q P)(P Q)→∧⌝∧是 永假 式； ③ ()P (P Q P →∧→是 永真 式；2、 命题联结词有 否定 、合取 、 析取 、 蕴含 、 等值 。

3、 含有n 个命题变元的主析取范式的个数是 2的2n 个 。

4、 辖域：紧接在量词之后最小的子公式 。

5、 命题公式P 与()()P Q P Q ∧∨∧⌝是 等值 （等值、不等值）。

6、 ()()()(),,,x y P x y Q x y xP x y ∀∀∧∧∃的自由变元是 y 。

7、 已知公式A 含有两个命题变元，且A 的主析取范式为12m m ∨，则它的主合取范式为 ()()P Q P Q ⌝∨⌝∧∨。

8、 假言推理的规则为 如果P 且P →Q 是真 则Q 。

9、 “中国有四大发明” 是（是，不是）命题。

10、 谓词公式()()()(),,,,x Px y tQ t z R x y t ∀∧∃→中量词∃的辖域为 Q(t,z) 。

二、选择题（每小题2分，共20分） 1、 下列语句中哪个是真命题（ C ） （A ）我正在说谎（B ）如果1+2=3，那么雪是黑的 （C ）如果1+2=5，那么雪是黑 （D ）严禁吸烟2、 下面哪个命题公式是重言式（B ） （A ）()()P Q Q P →∧→ （B ）()P Q P ∧→（C ）()()P Q P Q ⌝∨∧⌝⌝∧⌝ （D ）()P Q ⌝∨3、 下列推理不正确的是（A ） （A ）()P Q P Q →∧→ （B ）()P Q P P →∧→ （C ）()P Q P Q ∨∧⌝→ （D ）()P Q Q P →∧→4、 设论述域为整数集，下列公式中哪个的值为真（ B ） （A ）()0x y x y ∀∃+= （B ）()0x y x y ∃∀+= （C ）()0x y x y ∀∀+=（D ）()0x y x y ⌝∃∃+=5、 设个体域为A={a,b},公式()()xP x xS x ∀∧∃在A 上消去量词后应为（ B ） （A ）()()P x S x ∧（B ）()()()()()P a P b S a S b ∧∧∨ （C ）()()P a P b ∧（D ）()()()()P a P b S a S b ∧∧∨6、 设P ：我去镇上，Q ：我有时间。

谓词公式考试题目及答案一、选择题1. 谓词公式中，谓词的参数可以是：A. 常量B. 变量C. 函数D. 所有以上选项答案：D2. 下列哪个不是谓词逻辑表达式？A. ∀x P(x)B. ∃y Q(y)C. ¬R(x, y)D. x + y = z答案：D二、填空题3. 谓词逻辑中，全称量词的符号是______。

答案：∀4. 谓词逻辑中，存在量词的符号是______。

答案：∃三、简答题5. 简述谓词公式的一般形式。

答案：谓词公式的一般形式是P(x1, x2, ..., xn)，其中P是一个谓词，x1, x2, ..., xn是参数，参数可以是常量、变量或函数。

6. 解释谓词逻辑中的量词。

答案：谓词逻辑中的量词用来表示对变量的量化，包括全称量词（∀）和存在量词（∃）。

全称量词表示对所有可能的值都成立，而存在量词表示至少存在一个值使得命题成立。

四、计算题7. 给定谓词公式：∀x ∃y R(x, y)，解释其含义。

答案：该谓词公式的含义是对于所有的x，都存在一个y，使得R(x, y)成立。

8. 如果有谓词公式：∃x (P(x) ∧ Q(x))，它表示什么？答案：该谓词公式表示存在至少一个x，使得P(x)和Q(x)同时成立。

五、论述题9. 论述谓词逻辑与命题逻辑的区别。

答案：谓词逻辑与命题逻辑的主要区别在于谓词逻辑引入了量词和谓词，能够表达更复杂的关系和属性。

命题逻辑主要处理简单的命题和它们的逻辑关系，而谓词逻辑则可以表达涉及个体和属性的更复杂的逻辑结构。

10. 描述谓词逻辑在数学证明中的应用。

答案：谓词逻辑在数学证明中应用广泛，它可以用来形式化地表达数学概念和定理，以及它们的证明过程。

通过谓词逻辑，数学家可以更精确地定义数学对象和它们的性质，以及使用逻辑推理来证明数学命题的正确性。