1.语句
1.1命题
一个或真或假，而不能两者都是的陈述句。
说明：
1）命题是陈述句，而不能是疑问句、命令句、感叹句等；
例如（1）把门关上！
（2）你到哪里去？
2）如果命题为真，我们就说它的真值为真（T或1）；
如果命题为假，我们就说它的真值为假（F或0）。
3）命题通常用大写英文字母表示，如 P、Q、R、……。
4）命题语句或真或假，二者必取一；
例如 x = 3.
1.1.1命题的分类
原子命题：一个命题，但不能分解成更简单的命题。
例如 我是一位学生。
复合命题 ：若干个原子命题由联结词和圆括号联结起来构成的新命题。
例如 我是一位学生和他是一位工人。
命题常元 ：已知真假值的命题。
可直接用{T、F} 表示。
命题变元 ：以真假为其变域之变元，或没有指定真值的命题，但它不是命题。
常用大写英文字母 A , B , … , Z 表示。
1.2悖论
语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。
例如 我正在说谎。（在命题逻辑中不讨论这类问题）
例:判断下列语句是否为命题。
1）十是整数。
2）上海是一个村庄。
3）外星人曾到过地球。
4）小明很高。
5）π 的小数点后面第十亿位上是5。
6）我在说谎。
7）严禁随地吐痰！
8）她身体好吗？
9）x + y > 4.
TTTTTFFFF
2.命题联结词
在命题逻辑中有以下几种基本的联结词：
? ∧ ∨ → ?
2.1否定词( ? )
定义：给定命题 P，则在Ｐ的前面加否定词 ?，变为命题 ?P，称其为 P 的否定或非 P，记为： ?P。
其定义可用如下真值表表示:
P
?P
0
1
1
0
例如：
P：今天下雨，
?P：今天不下雨。
Q：每一种生物均是动物。——F
?Ｑ：有一些生物不是动物。——T
注：这里?Ｑ不能讲成“每一种生物都不是动物” ——F.
即对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。
2.2 合取词( ∧ )
定义：给定两个命题P、Q，则 P∧Q 称为 P 与 Q 的合取，记为： P∧Q 。
其定义可用如下真值表表示:
注：Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ和Ｑ的位置可以交换而不会影响ＰΛＱ的结果。
例如：
设 P：张三是三好学生；
Q：李四是三好学生。
则 P∧Q：张三和李四都是三好学生。
注：并非所有的“和”都表示“合取”，例如，王五和赵六是兄弟。当谓词描述的是对象之间的关系时不能用合取。
2.3析取词( ∨ )
定义：给定两个命题P、Q，则 P∨Q 称为 P 与 Q 的析取，记为： P ∨ Q 。
其定义可用如下真值表表示:
例如
设 P：灯泡坏了；
Q：开关坏了；
则 P ∨ Q： 灯泡坏了或是开关坏了。
P：今晚写字；
Q：今晚看书；
则 P ∨ Q：今晚写字或看书。
P：今天下雨；
Q：今天打雷；
则 P ∨ Q：今天下雨或打雷。
2.3.1 不可兼或
注：区分“可兼或”与“不可兼或”
并非所有的“或”都表示“析取”。
析取词“∨”为“可兼或”；
异或词“▽”为“不可兼或”；
例如 我向西走或向东走。
这种“或”就是“不可兼或”（“排斥或”、“异或”）
其特点：当两个命题的真值不同时，原命题的真值为“1”；否则为“0”。
可构造真值表如下：
设P：我向西走； Q：我向东走；
则 P ▽ Q：我向西走或向东走。
例如 1）他通过电视看杂技或到剧场看杂技。2）他乘火车去北京或乘飞机去北京。
以上两句均为“不可兼或”。
2.4蕴含词(→), 如果…，则….
定义：给定两个命题P、Q，
命题“如果P，则Q”称为“P蕴含Q”，记为：P→Q。
其中 P 称为蕴含前件//代码效果参考：http://hnjlyzjd.com/xl/wz_24279.html
、条件、前提；Q 称为后件、结果、结论。
注：当且仅当 P 为真，Q 为假时，P→Q 为假；
否则， P→Q 均为真。
其定义可用如下真值表表示:
例1 P：我拿起一本书
Q：我一口气读完了这本书
——形式条件命题
则 P→Q：如果我拿起一本书，则我一口气读完了 这本书。
例2 P：月亮出来了
Q： 3×3=9
——实质条件命题
则 P→Q：如果月亮出来了，则 3×3=9。
例3 a）如果地球是方的，则海水是咸的。
b）只有地球是方的海水才是咸的。
解：首先用字母表示简单命题。
设 P：地球是方的；
Q：海水是咸的；
该命题符号化为：a) P→Q b)?P→?Q
注：在日常生活中，用蕴含关系时前提和结论之间都有因果关系，称为“形势蕴含”，
但是在数理逻辑中，蕴含前件和后件可以没有任何因果关系，称为“实质蕴含”。
2.5 等值词（双条件词） ( ? )
定义： 给定两个命题P、Q，命题“P 当且仅当 Q”称为“P 等价 Q”记为：P?Q。
当且仅当P、Q同为真或同为假时 P?Q 为真；否则， P?Q 为假。
其定义可用如下真值表表示:
例如 设 Ｐ：△ABC是等腰三角形
Ｑ：△ABC有两只角相等
则Ｐ?Ｑ：△ABC是等腰三角形当且仅当△ABC中有
两只角相等。
例如 设 P：2+2=4；Q：雪是白的，
则 P?Q：2+2=4当且仅当雪是白的。
例如 设 P：春天来了；Q：燕子飞回来了，
则 P?Q：春天来了当且仅当燕子飞回来了。
2.6 命题联结词的结合//代码效果参考：http://hnjlyzjd.com/hw/wz_24285.html
律1）联结词在运算中的优先级由高到低为：
2）使用括号（ ）可以改变运算顺序——先括号内，后括号外。
3）连续的多个同种联结词结合力顺序为从左到右次序。
例如
2.7命题联结词小结
(1)五个联结词的含义与日常生活中的联结词的含义大致相同。
(2)“或”可分为可兼或（∨）和异或（▽）即不可兼或
(3) 除“?”为一元运算外，其余四个均为二元运算。
(4) “→”分为形式条件和实质条件命题，当前件为“Ｆ”时，不论后件怎样，则单条件命题的真值均为“Ｔ”。
(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。
经联结词运算后，复合命题真值的规定：
数理逻辑推理步骤如下：
①找出各简单命题，分别符号化。
②找出各联结词，把简单命题逐个联结起来。
例如： 将下列命题符号化：
（1）李明是计算机系的学生，他住在312室或313室。
（2）张三和李四是朋友。
（3）虽然交通堵塞，但是老王还是准时到达了车站。
（4）老王或小李中有一个去上海出差。
（5）只有一个角是直角的三角形才是直角三角形。
解：
（1）首先用字母表示简单命题。
P：李明是计算机系的学生。
Q：李明住在312室。
R：李明住在313室。
该命题符号化为：P∧（Q▽R）
（2）张三和李四是朋友。是一个简单句，该命题符号化为：P
（3）首先用字母表示简单命题。
P：交通堵塞。
Q：老王准时到达了车站。
该命题符号化为：P ∧ Q
（4）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为：P ▽ Q
也可符号化为：
或者
（5）首先用字母表示简单命题。
P：三角形的一个角是直角。
Q：三角形是直角三角形。
该命题符号化为：
注：该命题不可以化为
3.命题公式
3.1定义
命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。
定义：命题公式可按下述法则来生成：
(1)孤立的命题变元和命题常元是一个命题公式；
(2)若Ａ是命题公式， ?Ａ也为命题公式；
(3)如果A和B是命题公式，则(A∧B），(A∨B) ，(A→B)和(A?B)都是命题公式；
(4)当且仅当有限次使用规则(l)(2)和（3）所生成的公式才是命题公式。
3.2 命题公式的真值表
对命题变元用特定的命题来取代，这一过程称为对该命题变元进行指派。
命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成ｙ＝ｆ(x)
例如：公式P →(Q → R) 可定义三元函数
Y(P，Q，R)＝ P →(Q →R)
定义：命题公式 A 在其所有可能的赋值下取得的值所列成的表称为 A的真值表。
构造命题公式真值表的步骤如下：
1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。
2)按照从低到高的顺序写出命题公式的各层次。
3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。
例1：构造命题公式 ? (( P ∨ Q )∧P) 的真值表
例2：构造命题公式?(P∨?R)∧(Q∨?P)的真值表
例3 构造命题公式(P∧(P→Q))→Q 的真值表 永真式（重言式）
例4：证明 P ? Q 与 P∧Q ∨ ?P ∧ ?Q 是逻辑等假命题。
证明：可列真值表证明 真值表相同的两个公式称为等价公式。
由上二例可见，在一个命题公式中，包含：
２个命题变元就有４组真值指派；
３个命题变元就有 23＝ ８组真值指派，
ｎ个命题变元则有 2n 个真值指派。
几点说明
熟练之后，真值表的中间有些层次可不写
真值表的用途
（1）有了公式A的真值表就知道了A的一切信息
（2）其它用途待续
3.3 重言式（永真式）
举例说明
3.3.1定义
1）设命题公式A(P1,P2,...,Pn)中含有n个不同的原子变元 P1,P2,...,Pn(n为正整数)。
该变元组的任意一组确定的值（U1,…,Un）称为Ａ关于 P1,…,Pn 的一个完全指派，其中 Ui 或为Ｔ或为Ｆ。
如果对于Ａ中部分变元赋以确定值，其余变元没有赋以确定的值，
则这样的一组值称为公式Ａ的关于该变元组的部分指派。
2）使得公式 A 的真值为真的指派称为成真指派；使得公式 A 的真值为假的指派称为成假指派；
3）如果一个命题公式 A 的所有完全指派均为成真指派，则称公式 A 为重言式(永真式)。
如果一个命题公式 A 的所有完全指派均为成假指派，则称公式 A 为矛盾式(永假式)。
既不是永真式，又不是永假式，则称此命题公式是可满足式。
3.3.2 永真式的特点
（１）永真式的否定为永假式（￢Ｔ＝Ｆ）；
永假式的否定为永真式（￢Ｆ＝Ｔ）。
（２）二个永真式的析取、合取、蕴含、等值等均为永真式。
例如 求（P∧Q）∧﹁P 与（P∨Q）∨﹁P 的真值表。
3.4等价式
3.4.1定义
如果对两个公式Ａ，Ｂ不论作何种指派，它们的真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ等价于Ｂ，记作A ?B
例如 P ∨ ? P ? Q ∨ ? Q
例如 判断公式A：(P ∨ ? Q) ∨ (P ∨ Q) 与 B：(P ∨? R) ∨ (P ∨ R) 是否等价
解：列该公式的真值表
3.4.2 定理
命题公式A?B的充要条件是A?B为永真式
说明：
①“?”为等价关系符。
Ａ?Ｂ表示Ａ和Ｂ有等价关系。
Ａ?Ｂ不为命题公式。
②“?”为等值联结词（运算符）。
若Ａ、Ｂ为命题公式，则（Ａ?Ｂ）也为一命题公式。
例如 证明： ? ?P ? P
P → Q ? ? P ∨ Q.
解：列公式的真值表
3.4.3 等价式的性质
1）自反性: A ? A.
2）对称性: A ? B，则 B ? A.
3）传递性: A ? B， B ? C，则 A ? C.
3.4.4 常用等价公式
说明：
（1）上述１7组等价公式的证明方法可用真值表法，即把 ?改为 ? 所得的命题公式为永真式，则 ? 成立。
（2） Λ、∨、 ? 均满足结合律，则在单一用 Λ、∨、 ? 联结词组成的命题公式中，括号可以省去。
3.4.5置换原则
《定义》给定一命题公式Ｂ，其中P1,P2 ,…,Pn 是Ｂ中的原子命题变元，若
（1）用某些命题公式Ａi代换Ｂ中的一些原子命题变元 Pi；
（2）用命题公式Ａi 代换 Pi，则必须用Ａi代换Ｂ中的所有Pi；
由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例。
讨论定义：
（１）用命题公式只能代换原子命题变元，而不能去代换分子命题公式。
（２）要用命题公式同时代换同一个原子命题变元。
（３）永真式的代换实例仍为永真式；
反之，若代换实例为永真式时，则不能断定原公式也一定是永真式。
例１ 设Ｂ：Ｐ→（ ? QΛＰ）.
现用（Ｒ?Ｓ）代换Ｂ中的Ｐ，得
Ａ：(Ｒ?Ｓ)→( ? QΛ(Ｒ?Ｓ))
则Ａ是Ｂ的代换实例；
而Ａ’：(Ｒ?Ｓ)→(? QΛＰ)不是B的代换实例。
例２ Ｐ→ ?Ｑ的代换实例有：
(ＲΛ ?Ｓ)→ ?Ｍ，
(ＲΛ ?Ｓ)→Ｐ，
Ｑ→ ? (Ｐ→ ?Ｑ)等.
所以，一个命题公式的代换实例有无限个。
下面讨论取代过程（置换规则）：
《定义》给定一命题公式 A，设 A’是 A 的任何部分。如果 A’也是一个命题公式，则称 A’是 A 的 子命题公式。
《替换规则定理》给定一命题公式 A，设 A’是 A 的子公式。设 B’是一命题公式，如果 A’? B’，并且用B’取代 A 中 的 A’，从而生成一新的命题公式 B,则有 A ? B。
注：从定理可见，一个命题公式A，经多次取代，所得到的新公式与原公式等价。
例1 证明输出律：
Ｐ→(Ｑ→Ｒ) ? (ＰΛＱ)→Ｒ
证明：Ｐ→(Ｑ→Ｒ) ? Ｐ→(?Ｑ∨Ｒ)
? ?Ｐ∨ (?Ｑ∨ Ｒ)
? ?(ＰΛＱ) ∨Ｒ
? (ＰΛＱ)→Ｒ
真值表证明法
例2：证明：
( (Ｐ∨Ｑ) Λ ? ( ?ＰΛ ( ?Ｑ∨ ?Ｒ) ) ) ∨ ( ?ＰΛ ?Ｑ) ∨ (?ＰΛ ?Ｒ)为一永真式。
证明：原式
? ( (Ｐ∨Ｑ) Λ ? ( ?ＰΛ ?( ＱΛＲ) ) ) ∨ ?( Ｐ∨ Ｑ) ∨ ?(Ｐ∨Ｒ)
? ( (Ｐ∨Ｑ) Λ ( Ｐ∨ ( ＱΛＲ) ) )∨ ?( Ｐ∨ Ｑ) ∨ ?(Ｐ∨Ｒ)
? ( (Ｐ∨Ｑ) Λ ( Ｐ∨ ( ＱΛＲ) ) ) ∨ ?( Ｐ∨ Ｑ) ∨ ?(Ｐ∨Ｒ)
?( (Ｐ∨Ｑ) Λ ( (Ｐ∨Ｑ) Λ (Ｐ∨Ｒ) ) ) ∨ ? ( ( Ｐ∨ Ｑ) Λ (Ｐ∨Ｒ) )
? ( (Ｐ∨Ｑ) Λ (Ｐ∨Ｒ) ) ∨ ? ( ( Ｐ∨ Ｑ) Λ (Ｐ∨Ｒ) )
? T
∵它是Ｐ Λ ?Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式
3.4.6对偶原理
《定义》给定两个限定性命题公式(仅含?，∧，∨) A和A，若用∨代换∧，用∧代换∨，用T代换F，用F代换T。代换之后，一个命题公式可由另一个命题公式得来，则称 A和A 互为对偶式，而联结词 ∧和∨ 也是互为对偶的。
讨论定义：
(1)若命题公式中有联结词 →，?，则必须把其化成由联结词Λ，∨，? 组成的等价的命题公式，然后求它的对偶式；
(2)在写对偶式时，原命题公式中括号不能省去，且必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。
例1：求(P→Q)Λ(P→R)的对偶式。
解：(?P∨Q)Λ(?P∨R)
对偶式：(?PΛQ) ∨ (?PΛR)
例2：求(ＰΛＱ)∨Ｒ的对偶式。
解: 对偶式： （Ｐ∨Ｑ）ΛＲ
注： (ＰΛＱ)∨Ｒ的对偶式必须写成（Ｐ∨Ｑ）ΛＲ，而不能写成Ｐ∨ＱΛＲ。
定理1:设A和A是对偶式，P1,P2,…,Pn是出现在A和A中的所有原子命题变元,则有
?A(P1,P2,…,Pn) ? A(?P1,?P2,…,?Pn)
A(?P1,?P2,…,?Pn) ? ?A(P1,P2,…,Pn)
注 不难看出，一个命题公式的否定等价于它的对偶式，且用变元的否定代替每一个变元。
定理2:(对偶定理)若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若 A?B，则 A ?B 。
结论：（１）和（２）是互为对偶的。
3.5 永真蕴含式
3.5.1 定义
命题公式Ａ称为永真蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一个永真式，记作：Ａ?Ｂ
说明：“Ａ?Ｂ”读作“Ａ永真蕴含Ｂ”， “Ａ蕴含Ｂ”， “Ａ能推得Ｂ” “? ”是关系符，Ａ? Ｂ不是命题公式。
例如 证明：Ｐ? Ｐ∨Ｑ； ＰΛＱ? P
方法1：列出真值表
证明：Ｐ→(Ｐ∨Ｑ)和(ＰΛＱ)→Ｐ为永真式.
方法2：可用等价公式证
3.5.2 定理
设Ａ、B是两个命题公式，则Ａ?Ｂ的充要条件是Ａ?Ｂ且Ｂ? Ａ。
3.5.3 常用的永真蕴含式
3.5.4 证明方法
证明上述永真蕴含式的方法有三种：
(1)把“?”关系符改为“→”联结词，证明它为永真式。
(a)真值表法
(b)命题演算法
(2)＊找出使单条件命题的前件为“Ｔ”的所有真值指派，试看能否导致后件均为“Ｔ”，若为“Ｔ”，则永真蕴含关系式“?”成立。
例如 证明假言推理 :ＰΛ(Ｐ→Ｑ) ? Ｑ.
证：前件为“Ｔ”的所有指派为:
Ｐ、 (Ｐ→Ｑ)均为“Ｔ”，
Ｐ→Ｑ为“Ｔ”，
∵Ｐ为“Ｔ”，
∴Ｑ也应为“Ｔ” ，<
