入门级数理逻辑学习笔记：第一章命题逻辑的语义理解

最编程 2024-02-03 13:39:37

...

Q: \((p\vee q)\vee r\)对应的布尔函数（真值函数）定义域和值域分别是什么？将它表示成真值表为几行几列？一共有多少个与它相同定义域和值域的真值函数？
A: \(f:\{1,0\}^3\to\{1,0\}\).
（如果表头4列分别为\(p,q,r,(p\vee q)\vee r\)，不计表头所占的1行，则）4列，8行。
\(2^{2^3}\)个。（当然，我们认为当定义域、值域和对应法则均相同的函数是相同的，而不重复计数。即使其对应命题形式可能不同）

Q: “如果\(1=2\)则\(-1=-2\)”是真命题吗？
A: （按数字和符号通常的意义理解）是真命题。因为\(1=2\)为假命题，故用\(\to\)连接它和任何命题都得到真命题。（这是“空虚(vacuous)的真”）

Q: 如何理解“命题形式可嵌套，可潜在无限长；给定一个命题形式，则为有限长”？
A: 嵌套：命题形式由归纳（递归）定义，即首先任一变元是命题形式，其次变元间各种（一元或二元）运算也得到命题形式。
“潜在”意为任给一个命题形式，都存在“比它更长”的，此过程可以“无限进行”下去。但是每一个确定的命题形式都是有限长的。
注：线性代数中无限维线性空间中“线性表出”的定义也是如此。确定的某一种线性表出方式一定只含有限个向量。但并不存在一个整数是所有表出方式中向量个数的上界。

Q: 如何理解“技术性符号如( ) ...都不是必要的”？请解释：没有省略号，怎么表示\(p_1\wedge p_2\wedge\cdots \wedge p_n\)呢？
A: 比如中缀表达式转化为前缀表达式（\(p\vee q\vee r\)转化为\(\vee\vee pqr\)）则无需括号。用省略号表达命题形式只是为了表达方便，完全可以不需要。
“没有省略号，怎么表示\(p_1\wedge p_2\wedge\cdots \wedge p_n\)”这个疑问并不清晰合理。实际上，当\(n\)为任意确定正整数时，显然可以去除省略号。而泛泛地说“\(p_1\wedge p_2\wedge\cdots \wedge p_n\)”而不确定\(n\)则并不是一个命题形式（不符合命题形式的定义）。

Q: “判定一个命题形式是否可满足/重言式/矛盾式的方法就是构造其真值表”是否说明SAT问题有通用解法？是否说明了解决了\(P=^?NP\)问题？为什么？
A: 构建真值表需要指数复杂度，是一个平凡的通用解法。这样的“解决”并没有带来任何新的意义。
注：SAT问题指判定一个命题形式是否可满足。如果找到了多项式复杂度的解决方法才相当于解决了\(P=^?NP\)问题。

Q: 逻辑等价和运算符\(\leftrightarrow\)有何联系和区别？
A: 联系：若\(\mathscr A\leftrightarrow\mathscr B\)是重言式，称\(\mathscr A \equiv \mathscr B\). 然而要注意逻辑等价\(\equiv\)针对的是命题形式，而\(\leftrightarrow\)可以连接命题（复合命题或简单命题）或者命题形式。
更具体地说：你可以下结论：\(\mathscr A\equiv \mathscr B\)，也可以下结论：\(\mathscr A\leftrightarrow \mathscr B\)是重言式。但是，\(\mathscr A\leftrightarrow \mathscr B\)本身只是一个命题形式，并不是“结论”，与\(\mathscr A\equiv \mathscr B\)含义不同。
注：中文术语：若……则……、当且仅当：针对命题；逻辑隐含、逻辑等价：针对命题形式。

Q: 简述具体怎么构造\(\sim (p\wedge q)\leftrightarrow((\sim p)\vee (\sim q))\)的真值表。
A: 在这里插入图片描述

例如可以如此进行，先写黑色，再写红色……总之简单命题最先写，接着运算顺序先的先写。

上一篇：全面解析C++赋值运算符重载函数(operator=)

下一篇：集异璧

入门级数理逻辑学习笔记：第一章 命题逻辑的语义理解