离散数学左孝凌版本-----第一章命题逻辑

标签：合式公式左孝凌联结词 neg 命题离散数学 ----- Leftrightarrow rightarrow

第一章知识点

~~因为第一章多且杂就不分小标题了~~

定义：

命题: 非真即假！的陈述句，真值为真为真命题，真值为假为假命题。

悖论: 真假矛盾的命题。如我说的话都是假话 //不是命题

原子命题: 不可以再被拆分的为原子命题。如2 大于 3

联结词：通过已有命题构造出新命题的一种方法。

非联结词：\(\neg p\)表示当\(p\)成立时，\(\neg p\)不成立，当\(p\)不成立时，\(\neg p\)成立。

合取联结词：使用符号\(\and\)只有双方同时为真时才为真。

析取联结词：使用符号\(\or\), 只有当双方全为假时才为假。

蕴含联结词：使用符号\(\rightarrow\), 只有当后件为假，前件为真时才为假，其余的全部为真。

等价联结词：使用符号\(\leftrightarrow\), 同真同假时才为真，其余为假。

根据以上的定义推出以下定义

复合命题：原子命题通过各种联结词连接起来的命题称为复合命题。

相容或：析取双方可以同时为真的命题为相容或, 张三英语考100或者数学考100

排斥或：析取双方不可以同时为真 , 如张三是湖北人或湖南人

命题常元：表示一个确定的命题的命题标识符，真值确定，等价的理解为上一章的命题完全没有问题。

命题变元：真值可取0或者1, 真值不确定，不是命题！！！

当命题变元P用一个特定的命题取代时P才确定真值，这叫指派

自然语言中的与和与命题逻辑不同

合式公式(递归式定义）：

单个命题变元是合式公式，称为原子命题公式

若\(A\)是合式公式，那么\(\neg A\)也是合式公式.

若\(A\)和\(B\)都是合式公式，那么\(A\)与\(B\)之间进行的所有上述的联结词运算之后，仍然是合式公式。

依次使用1,2,3得到的公式仍然是合式公式。

翻译是可以考虑真值表：

黎明虽然很用功但是很愚钝P\(\and\)Q

n个变元有\(2^{n}\)个真值情况

左侧写上命题变元的所有赋值，一般从上之下以二进制从小到大的排列\([0,2^n - 1]\),\(n\)为命题变元的个数。

证明方法：真值表公式

设A是一个命题公式可能为永真式矛盾式可满足式

可以通过证明A\(\leftrightarrow\)B（是一个重言式）来证明AB等价

蕴含式当P\(\rightarrow\)Q是一个重言式时，称P蕴含Q 蕴含式可传递

蕴含式证明方法

名称	表达式
双重否定	\(A\Leftrightarrow \neg\neg A\)
幂等律	\(A\Leftrightarrow A\or A, A\Leftrightarrow A \and A\)
交换律	\(A\or B \Leftrightarrow B \or A, A\and B \Leftrightarrow B \and A\)
结合律	\(A\or(B\or C) \Leftrightarrow (A\or B)\or C \\A\and(B\and C) \Leftrightarrow (A\and B)\and C\)
分配律	\(A\or(B\and C)\Leftrightarrow(A\or B)\and(A\or C)\\ A\and(B\or C) \Leftrightarrow(A\and B)\or (A\and C)\)
德摩根律	\(\neg(A\and B) \Leftrightarrow \neg A \or \neg B\\\neg(A\or B) \Leftrightarrow \neg A \and \neg B\)
吸收律	\(A\and(A\or B) \Leftrightarrow A \\ A\or(A\and B) \Leftrightarrow A\)
零律	\(A \or False \Leftrightarrow A\\A \and False = False\)
同一律	\(A\or True \Leftrightarrow True\\A\and True \Leftrightarrow A\)
排中律	\(A\or \neg A \Leftrightarrow True\)
矛盾律	\(A \and \neg A \Leftrightarrow False\)
蕴涵等价式	\(A\rightarrow B \Leftrightarrow \neg A\or B\)
等价等价式	\(A\leftrightarrow B \Leftrightarrow (A\rightarrow B)\and (B \rightarrow A)\)
假言异位	\(A\rightarrow B \Leftrightarrow \neg B \rightarrow \neg A\)
等价否定等价式	\(A\leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B\)
归谬论	\((A\rightarrow B) \and (A\rightarrow \neg B) \Leftrightarrow \neg A\)