Site Overlay

离散数学笔记:1.1 命题逻辑

下面哪些是命题?

a) Do not pass go. 不是命题。

b) What time is it? 不是命题。

c) There are no black flies in Maine. 是命题。

d) 4+x = 5. 不是命题。

e) The moon is made of green cheese. 是命题。

f) 2n ≥ 100.不是命题。

命题

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either
true or false, but not both.

命题是具有确定真假值的陈述句

4+x = 5 为什么不是命题?问题在于 x 是一个变量,在赋值之前无法确定真假。


\12. Let p, q, and r be the propositions

p :You have the flu.

q :You miss the final examination.

r :You pass the course.

Express each of these propositions as an English sentence.

a) $p → q$ IF you have the flu, THEN you miss the final examination.

b) $¬q \leftrightarrow r $ You won't miss the final examination if and only if you pass the course.

c) $ q →¬ r $IF you miss the final examination, THEN You do NOT pass the course.

d) $p∨q ∨r$ you have the flu OR you miss the final examination OR You pass the course

e) $(p →¬r)∨(q →¬r)$ You do not pass the course when you have the flu or miss the final examination

f) $(p∧q)∨(¬q ∧r)$ you miss the final examination and have the flu .Or you do not miss the final examination and pass the course

命题符号化

原子命题和复合命题

比如: 今天下雨并且明天也下雨.

这是一个复合命题, 其包含逻辑连接词(且)和原子命题(今天下雨/明天下雨).

我们可以把符合命题看作一个表达式, 原子命题是参数, 逻辑连结词是函数, 其真假是返回值

符号约定

真命题用 $T$ 表示, 假命题用 $F$ 表示. 原子命题用 $p,q,r,s$ 等字母表示. 真假的值用 $1,0$ 表示.

逻辑连结词的符号

非 p $\neg p$

p 且 q $p\wedge q$

p 或 q $p\vee q$

如果 p 那么 q $p\rightarrow q$

当且仅当(iif) $p\leftrightarrow q$

逻辑连结词

非: $\neg p$

参数: 命题 p

返回值: 命题 p 的否定.

示例:

let p = true.
let result = !p

示例返回: false.

这一函数记作 $\neg$

合取: $p \wedge q$

参数: 命题 p, q

返回值: 返回 p, q 是否都为真.

示例:

let p = true;
let q = false;
let result = p && q

示例返回: false.

这一函数记作 $\wedge $

析取: $p \vee q$

参数: 命题 p, q

返回值: 返回 p, q 是否至少一个真.

示例:

let p = true;
let q = false;
let result = p || q

示例返回: true.

这一函数记作 $\vee$

实质条件 $p\to q$

参数: 命题 p, q

实质条件也叫实质蕴涵.

参数别名:

  1. p: 前件
  2. q: 后件

返回值: 返回 $\neg q \or b$

注: $p \to q$ 表示 $p$$q$ 的充分条件, 其只在 $p$$q$ 假的情况下返回假. $p$$q$ 不一定是相关联的, 比如: $牛顿有六根手指头\to 1 是整数$ 命题, "如果你不是人,那么你是人"为真. 我们容易误认为 $\to$ 表示推出, 其实不是.

逻辑蕴含 $p\models q$

$a\to b$ 是同义反复(见后文)时, a 逻辑蕴含 b.

双条件 $p \leftrightarrow q$

参数: 命题 p, q

双条件也叫当且仅当/双向蕴含.

返回值: 返回 p, q 的真值是否相同.

等价形式:

  1. $((p ∧ q) ∨ (¬p ∧ ¬q))$
  2. $(\neg p\or q) \and (p\or\neg q)$

运算优先级

从高到低:

  1. $\neg$
  2. $\and$
  3. $\or$
  4. $\to$
  5. $\leftrightarrow$

\14. Let p, q, and r be the propositions

p :You get an A on the final exam.

q :You do every exercise in this book.

r :You get an A in this class.

Write these propositions using p, q, and r and logical connectives (including negations).

a) You get an A in this class, but you do not do every exercise in this book.

$r\wedge\neg q$

b) You get an A on the final, you do every exercise in this book, and you get an A in this class.

$p\wedge q \wedge r$

c) To get an A in this class, it is necessary for you to get an A on the final.

$p\rightarrow r$

d) You get an A on the final, but you don’t do every exercise in this book; nevertheless, you get an A in this class.

$p\wedge \neg q \wedge r$

e) Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.

$r\Leftarrow p\wedge q$

f) You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final.

$p\vee q \rightarrow r$

\26. Write each of these propositions in the form “p if and only if q” in English.

a) For you to get an A in this course, it is necessary and sufficient that you learn how to solve discrete mathematics problems.

You get an A in this course if and only if you learn how to solve discrete mathematics problems.

b) If you read the newspaper every day, you will be informed, and conversely.

You'll get informed if and only if read the newspaper everyday.

c) It rains if it is a weekend day, and it is a weekend day if it rains.

It rains if and only if it's a weekend day.

d) You can see the wizard only if the wizard is not in, and the wizard is not in only if you can see him.

You can see the wizard if and only if he's not in.

\30. How many rows appear in a truth table for each of these compound propositions?

a) (q →¬p)∨(¬p →¬q)

$2^2 = 4;$

b) (p∨¬t)∧(p∨¬s)

$2^3 = 8;$

c) (p → r)∨(¬s →¬t)∨(¬u → v)

$2^6 = 64;$

d) (p∧r ∧s)∨(q ∧t)∨(r ∧¬t)

$2^7 = 128;$

\38. Construct a truth table for ((p → q)→ r)→ s.

$p$ $q$ $r$ $s$ $(((p → q) → r) → s)$
F F F F T
F F F T T
F F T F F
F F T T T
F T F F T
F T F T T
F T T F F
F T T T T
T F F F F
T F F T T
T F T F F
T F T T T
T T F F T
T T F T T
T T T F F
T T T T T

发表评论

电子邮件地址不会被公开。 必填项已用*标注