首页 > 其他分享 >离散数学 第1章 数理逻辑

离散数学 第1章 数理逻辑

时间:2024-01-22 19:11:34浏览次数:22  
标签:合取范式 联结词 公式 命题 离散数学 变元 析取范式 数理逻辑

1.1 命题

1.1.1 基本概念

断言:一个陈述语句。祈使句、疑问句一定不是断言。
命题:要么为真,要么为假,不能二者都是的断言。
原子命题(本源命题):一个命题已不能分解成更简单的命题
命题和本源命题常用大写字母P、Q、R表示 eg.P:4是质数

1.1.2 命题联结词

复合命题:命题和原子命题可通过一些联结词构成新命题
联结词:命题验算中的运算符,叫逻辑运算符或逻辑联结词

常用的逻辑联结词

  1. 否定词 ¬
  2. 合取词 ^
    P^Q称为P和Q的合取,P并且Q
  3. 析取词 v
    PvQ称为P和Q的析取,P或Q
  4. 蕴涵词 ->
    P->Q称为P蕴含Q,如果P,那么Q,P叫做前提、假设或前件,Q叫做结论或后件
    P->Q 等价与 ¬PvQ
    image
    形式蕴含:用蕴含式来断言前提和结论之间的因果或实质关系
    实质蕴含:前提和结论并不需要有因果和实质关系
    P->Q的逆命题:Q->P
    P->Q的反命题:¬P -> ¬Q
    P->Q的逆反命题:¬Q -> ¬P
  5. 等值词↔
    P↔Q称为等值式,读做P等值于Q(当且仅当P则Q)
    P↔Q 等价于 P->Q ^ Q->P
    image

运算符结合力的由强至弱的顺序为¬ 、 ^ 、 v 、 -> 、 ↔。凡符合此顺序的,括号均可省去

1.1.3 命题变元和命题公式

命题变元:真值未指定的任意命题
命题常元:真题已指定的命题
原子公式:单个命题变元或命题常元
命题公式:命题变元的断言,由以下规则生成的公式叫命题公式

  1. 单个原子公式是命题公式
  2. 若A和B是命题公式,则¬A,(A^B)、(AVB)、(A->B)、(A↔B)是命题公式
  3. 有限步的应用规则1和2生成的公式,才叫命题公式

命题公式的真假值一般是不确定的。当命题公式中所有的命题变元代以命题时,命题公式就变为命题
两个命题公式如果有相同的真值,则称它们是逻辑等价命题

1.2 重言式

1.2.1 基本概念

指派:对有n个命题变元的命题公式,命题变元的真值有2n种不同的组合,每一种组合叫做一种指派
重言式(永真式):对应于所有指派,命题公式均取值为真,eg.Pv¬P
矛盾式(永假式):对应于所有指派,命题公式均取值为假,eg.P^¬P
偶然式:不是重言式,也不是矛盾式,这种命题公式叫偶然式
可满足的:一个公式如果至少存在一个指派,使其值为真
非永真:如果至少存在一个指派,使其值为假

1.2.2 恒等式

逻辑恒等式:如果A↔B是重言式,则A与B对任何指派都有相同的真值。记为<=>
注意:区分等值词↔和等价<=>的关系:↔是逻辑联结词(运算符),而<=>是表示A和B有逻辑等价这个关系的符号,它的作用相当于代数中的"="
image

1.2.3 永真蕴含式

证明方法

  1. 假定前件是真,若能推出后件是真,则此蕴含式是真
  2. 假定后件是假,若能推出前件是假,则此蕴含式是真

1.2.6 对偶原理

对偶规则:^ -> v、v -> ^、T->F、F->T
注意:对偶不涉及否定联结词¬
对偶的对偶仍为自身,对偶是相互的

对偶原理

若A<=>B,且A、B为由命题变元P1,P2,……,Pn及联结词^ 、v、¬构成的公式,则A*<=>B*
若A=>B,且A、B为由命题变元P1,P2,……,Pn及联结词^ 、v、¬构成的公式,则B*=>A*

1.3 范式

1.3.1 析取范式和合取范式

基本积:命题公式中的一些命题变元和一些命题变元的否定之积
eg.P ^ Q、¬P ^ Q
基本和:命题公式中的一些命题变元和一些命题变元的否定之和
eg.PvQ、PvQv¬Q
任何一个命题公式都可求得它的析取范式,因为->和<=>可用^、v和¬表达,但一个命题公式的析取范式不是唯一的,把运算符最少的称为最简析取范式
如果给定的公式的析取范式中每个基本积都是永假式,则该式也必定是永假式
任何一个命题公式都可求得它的合取范式,因为->和<=>可用^、v和¬表达,但一个命题公式的合取范式不是唯一的,把运算符最少的称为最简合取范式
如果给定的公式的合取范式中每个基本积都是永真式,则该式也必定是永真式

1.3.2 主合取范式和主析取范式

极小项:在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫极小项
主析取范式:一个由极小项之和组成的公式
一个命题的主析取范式可通过真值表求解,真值表是唯一的,因此一个命题公式的主析取范式也是唯一的。
两个命题公式如果有相同的主析取范式,那么这两个命题公式是逻辑等价的

极大项:在n个变元的基本和中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本和叫极大项
主合取范式:一个由极大项之积组成的公式
一个命题公式的主合取范式也是唯一的。
两个命题公式如果有相同的主析取范式,那么这两个命题公式是逻辑等价的

一个命题公式的主析取范式和主合取范式紧密相关,代表极小项和极大项的足标是互补的。eg.P ^ Q v R <=> ∑(1,3,5,6,7) <=> π(0,2,4)

1.3.3 主析取范式/主合取范式的个数

n个命题变元可构造2的2n次幂个不同的主析取范式/主合取范式

1.4 联结词的扩充与归约

与非:P↑Q <=> ¬(P^Q)
或非:P↓Q <=> ¬(PvQ)
异或:P⊕Q <=> ¬PvQ ^ Pv¬Q
蕴含否定:¬(P->Q)

只用^、v、¬三个联结词构造的式子,就足以把一切命题公式等价地表示出来

1.5 推理规则和证明方法

image
规则P:在推导的任何步骤上都可以引入前提
规则T:在推导中,如果前面有一个或多个公式永真蕴含S,则可把S引进推导过程

1.6 谓词和量词

谓词

个体:命题中所涉及的对象
谓词:刻画个体的性质或若干个体间关系的模式。一般用大写字母P、Q、R…表示
eg.Q(x,y):x生于y

量词

全称量词:∀x P(x)表示对一切x,P(x)为真
存在量词:Ex P(x)表示存在一些x使P(x)为真

标签:合取范式,联结词,公式,命题,离散数学,变元,析取范式,数理逻辑
From: https://www.cnblogs.com/zjq182/p/17978528

相关文章

  • 离散数学
    计算题1:假设\(p\)表示“我喜欢数学”,\(q\)表示“我会编程”,\(r\)表示“我喜欢阅读”,\(s\)表示“我会游泳”。现有如下命题:(1)如果我不喜欢数学,那么我一定不会编程;(2)如果我会编程,那么我要么喜欢阅读,要么会游泳;(3)我不会游泳且不喜欢阅读。回答:将以上命题翻译成命题......
  • 离散数学 第一章 命题逻辑 1-3命题公式与翻译
    前面已经提到,不包含任何联结词的命题叫做原子命题,至少包含一个联结词的命题称作复合命题。设p和q是任意两个命题,则┓p,p∨q,(p∧q)∨(p→q),p«(q∨┓p)等都是复合命题。若p和q是命题变元,则上述各式均称作命题公式。p和q称作命题公式的分量。必须注意:命题公式是没有真假值的,仅当在一个公式中......
  • 离散数学 第一章 命题逻辑 1-2 联结词
    在自然语言中,常常使用“或”,“与”,“但是”等一些联结词,对于这种联结词的使用,一般没有很严格的定义,因此有时显得不很确切。在数理逻辑中,复合命题是由原子命题与逻辑联结词组合而成,联结词是复合命题中的重要组成部分,为了便于书写和进行推演,必须对联结词作出明确规定并符号化。下面介......
  • 离散数学 第一篇 数理逻辑
    第一篇数理逻辑    逻辑学是一门研究思维形式及思维规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分为辨证逻辑与形式逻辑两种,前者是以辨证法认识论的世界观为基础的逻辑学,而后者主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。......
  • 离散数学蕴含式的问题
    如何理解数理逻辑中的蕴含?P→Q它表示自然语言的“如果…,则…”这种假言判断的,如果P为真命题,Q也为真命题时,P→Q是真命题,当P为真命题,而Q为假命题时,P→Q是一个假命题。比如张三说,“如果明天天不下雨(P),那么他去你家玩(Q)”,如果第二天天不下雨,他去了你家,他说了真话(P→Q为真),如果天不......
  • 离散数学 第一章 命题逻辑 1-1 命题及其表示法
    在数理逻辑中,为了表达概念,陈述理论和规则,常常需要应用语言进行描述,但是日常使用的自然语言进行描述,往往叙述时不够确切,也易产生二义性,因此就需要引入一种目标语言,这种目标语言和一些公式符号,就形成了数理逻辑的形式符号体系。所谓目标语言就是表达判断的一些语言的汇集,而判断就是对......
  • 《离散数学》双语专业词汇表 名词术语中英文索引
    《离散数学》双语专业词汇表set:集合subset:子集element,member:成员,元素well-defined:良定,完全确定brace:花括号representation:表示sensible:有意义的rationalnumber:有理数emptyset:空集Venndiagram:文氏图contain(in):包含(于)universalset:全集finite(infinite)set:有限(无限)集......
  • 离散数学
    数理逻辑分为命题逻辑和谓词逻辑两部分命题逻辑命题的真值只有两个:“真”或者“假”命题的表示:用大写字母表示逻辑连接词复合命题由若干个连结词、标点符号及原子命题复合构成的命题非$\neg$合取$\land$表示:并且、不但而且定义:两个命题P和Q的合取是一个复合命题,记作......
  • 数理逻辑 (1) 命题逻辑
    命题表达式命题语言的字符集由和变量和命题运算符构成,由于\(\land,\lor,\leftrightarrow\)都能用\(\lnot,\to\)代替,故定义符号表:\[\Sigma:=\{(,),\lnot,\to,A_n|n\in\mathbbN\}\]其中\(A_n\)代表了可数个命题变量命题逻辑的有限符号串定义为:\[\Sigma^......
  • 离散数学笔记——集合
    离散数学笔记——集合集合的概念集合是由一些确定的元素所组成的整体,其中的元素可以是任何事物定义:A={a1,a2,a3,...,an}表示集合的名称,{}表示集合的符号。a1,a2,a3,...an表示集合中的元素x∈A表示元素x属于集合A集合的特点集合没有重复元素集合......