第一章 命题逻辑的基本概念

命题逻辑的基本概念命题逻辑（propositional logic），又称命题演算，是数理逻辑的一个分支，它研究命题与命题之间的逻辑关系。

在命题逻辑中，命题是语句或陈述，可以判断为真或假。

命题逻辑的基础概念包括命题、联结词和复合命题等。

一、命题在命题逻辑中，命题是用来陈述某种事实或陈述的语句，可以判断为真或假。

命题通常用字母表示，如p、q、r等。

下面是一些例子：1. p：今天是晴天。

2. q：明天会下雨。

3. r：1+1=2。

二、联结词联结词是用来连接命题的词语，它们可以表示不同的逻辑关系。

常见的联结词有否定、合取、析取、条件、双条件等。

1. 否定（¬）：表示命题的否定，将命题的真值取反。

例如，¬p表示命题p的否定。

2. 合取（∧）：表示逻辑与的关系，表示两个命题都为真时，结果命题才为真。

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

3. 析取（∨）：表示逻辑或的关系，表示两个命题中至少一个为真时，结果命题为真。

例如，p∨q表示命题p或命题q至少一个为真。

4. 条件（→）：表示逻辑蕴含的关系，表示命题p成立时，命题q也必定成立。

例如，p→q表示命题p蕴含命题q。

5. 双条件（↔）：表示逻辑等价的关系，表示命题p和命题q有相同的真值。

即当p和q同时为真或同时为假时，结果命题为真。

例如，p↔q表示命题p和命题q等价。

三、复合命题复合命题是由多个命题通过联结词构成的新命题。

复合命题的真假取决于其组成命题的真假以及联结词的逻辑关系。

例如：1. (p∧q)→r：表示命题p和命题q的合取蕴含命题r。

2. ¬(p∨q)：表示命题p和命题q的析取的否定。

3. p↔q∧r：表示命题p和命题q等价，并且命题r为真。

在命题逻辑中，通过运用联结词的组合和推理规则，可以进行逻辑推理和推断。

命题逻辑为我们提供了分析和解决复杂问题的思维工具。

总结：命题逻辑是数理逻辑的一个重要分支，研究命题与命题之间的逻辑关系。

命题逻辑的基本概念和符号命题逻辑作为逻辑学的一个重要分支，研究的是命题及其之间的关系。

在命题逻辑中，有一些基本概念和符号是我们必须要了解的。

一、命题命题是一个陈述性的句子，它要么是真的，要么是假的，不存在中间值。

比如，“天空是蓝色的”和“2加2等于5”都是命题。

我们可以用大写字母P、Q、R等来表示命题。

二、命题变项命题变项是指用小写字母p、q、r等来表示具体的命题。

它们通常用来表示多个具体的命题，而不是单个的命题。

三、命题运算符命题运算符是用来表示命题之间关系的符号。

常见的命题运算符有如下几种：1. 否定运算符（¬）：表示取反，即命题的否定。

若P为一个命题，那么¬P表示P的否定。

2. 合取运算符（∧）：表示逻辑“与”，即两个命题同时为真时结果才为真。

若P和Q都是命题，那么P∧Q表示P与Q同时为真。

3. 析取运算符（∨）：表示逻辑“或”，即两个命题其中一个为真时结果就为真。

若P和Q都是命题，那么P∨Q表示P或Q至少一个为真。

4. 条件运算符（→）：表示逻辑“如果...那么”，即若一个命题成立，则另一个命题也成立。

若P和Q都是命题，那么P→Q表示如果P成立，则Q也成立。

5. 双条件运算符（↔）：表示逻辑“当且仅当”，即两个命题同时为真或同时为假时结果为真。

若P和Q都是命题，那么P↔Q表示当且仅当P和Q同时为真或同时为假。

四、真值表真值表是用来列出命题在不同情况下的真值的表格。

通过真值表，我们可以确定命题在各种情况下的真假情况，从而帮助我们进行逻辑推理。

五、重言式和矛盾式重言式是指在所有情况下都为真的命题，矛盾式是指在所有情况下都为假的命题。

根据命题逻辑的基本规则，我们可以通过真值表判断一个命题是重言式还是矛盾式。

六、命题公式命题公式是由命题和命题运算符组成的复合命题。

常见的命题公式可以通过命题运算符的组合得到，如(P∧Q)→R。

综上所述，命题逻辑的基本概念和符号对于我们理解和分析命题之间的逻辑关系非常重要。

离散数学笔记总结一、命题逻辑。

1. 基本概念。

- 命题：能够判断真假的陈述句。

例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。

- 命题变元：用字母表示命题，如p,q,r等。

2. 逻辑联结词。

- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。

- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。

- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。

- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。

- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。

3. 命题公式。

- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。

- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。

- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。

4. 逻辑等价与范式。

- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。

例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。

- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。

- 合取范式：由有限个简单析取式的合取组成的命题公式。

- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。

- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。

二、谓词逻辑。

1. 基本概念。

- 个体：可以独立存在的事物，如人、数等。

- 谓词：用来刻画个体性质或个体之间关系的词。

例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。

- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。

- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。

命题逻辑的基本概念命题与联结词命题：非真即假的陈述句。

真值：命题的陈述句所表达的判断结果，真值只取真或假两种情况。

假命题：真值为假的命题。

真命题：真值为真的命题。

简单命题（原子命题）：无法继续拆分的命题。

复合命题：多个原子命题通过联结词联结而成的命题。

悖论：自相矛盾的陈述句。

否定联结词：符号﹁（复合命题非p称作p的否定式，记作﹁p）合取联结词：符号∧（复合命题p且q称作p与q的合取式记作p∧q）析取联结词：符号∨（复合命题p或q称作p与q的析取式记作p∨q）蕴涵联结词：符号→（复合命题如果p，则q称为p与q的蕴涵式记作p→q，p为蕴涵式的前件，q为蕴涵式的后件）蕴涵联结词的使用及判定方法：使用：1：因为p所以q这类直抒胸臆的表达时可以直接看作：p→q2：只有p才q这类具有转折性的表达时可以直接看作：q→p判定：1：同假时为真2：后件为真前件为假时为真3：后件为真前件为真时为真其他情况皆为假等价联结词：符号↔（复合命题p当且仅当q称为p与q的等价式）等价联结词的判定：1：当p与q同时为真时为真2：当p与q同时为假时为假命题公式及其赋值命题常项（命题常元）：可以直接理解为原子命题或简单命题命题变项（命题变元）：真值可以变化的陈述句，因此命题变项不是命题合式公式：命题变项使用联结词组合成的符号串（可以当作命题用联结词组合成的复合命题）合式公式层数的判定：下面p和q都是公式或者命题常项1：当个命题变项为0层公式。

2：﹁p为1层公式3：p∧q为n+1层公式，n=max（p的层数，q的层数）4：p∨q为n+1层公式，n=max（p的层数，q的层数）5：p→q为n+1层公式，n=max（p的层数，q的层数）6：p↔q为n+1层公式，n=max（p的层数，q的层数）赋值（解释）：对公式中的命题变项指定一个真值，真值为1即该命题变项为成真赋值，真值为0即该命题变项为成假赋值。

重言式（永真式）：即该合式公式在任意赋值下取值都是真矛盾式（永假式）：即该合式公式在任意赋值下取值都是假可满足式：即至少存在一种赋值下取值为真故重言式必是可满足式，可满足式不一定是重言式，可满足式必不是矛盾式，矛盾式必不是可满足式。

第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q 前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

命题逻辑的概念与应用命题逻辑是逻辑学中的一种形式逻辑，也被称为命题演算或命题推理，它主要关注的是命题之间的关系和推理规则。

在实际应用中，命题逻辑具有广泛的用途，涉及到数学、计算机科学、哲学等多个领域。

本文将介绍命题逻辑的概念与应用，并从数学和计算机科学的角度探讨其实际价值。

一、命题逻辑的概念命题逻辑是研究命题之间关系的一种形式逻辑。

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

命题逻辑通过逻辑运算符来描述命题之间的关系，主要包括合取、析取、蕴含和否定等逻辑运算符。

1. 合取（AND）：用符号“∧”表示，在命题p和q成立时，合取命题p ∧ q也成立。

2. 析取（OR）：用符号“∨”表示，在命题p和q中至少一个成立时，析取命题p ∨ q成立。

3. 蕴含（IMPLICATION）：用符号“→”表示，在命题p成立的情况下，蕴含命题p → q成立。

4. 否定（NEGATION）：用符号“¬”表示，在命题p不成立时，否定命题¬p成立。

二、命题逻辑的应用命题逻辑作为一种形式逻辑，具有广泛的应用。

在数学和计算机科学领域，命题逻辑被广泛应用于推理、证明和问题求解等方面。

1. 数学应用命题逻辑在数学中具有重要的作用。

数学中的定理和推理可以通过命题逻辑的运算符和规则进行严密的推导和证明。

例如，在数学中我们经常使用蕴含和否定来推导和证明命题，同时也可以使用合取和析取来建立和证明复合命题。

2. 计算机科学应用命题逻辑在计算机科学中应用广泛。

计算机的逻辑电路、编程语言中的条件语句和循环语句，以及人工智能中的推理系统等都与命题逻辑密切相关。

命题逻辑为计算机科学提供了一种严密的推理和判断方法，帮助计算机进行逻辑推断和问题解决。

在计算机科学中，命题逻辑被用于描述计算机程序的正确性和程序验证。

通过使用命题逻辑的规则和推理方法，可以检验程序中的逻辑错误，并以此来验证程序是否满足需求和规范。

此外，命题逻辑还在人工智能领域中被广泛应用。