Site Overlay

# 离散数学笔记：1.1 命题逻辑

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

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

c) There are no black ﬂies 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 ﬂu.

q :You miss the ﬁnal 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 ﬁnal examination and have the ﬂu .Or you do not miss the ﬁnal examination and pass the course

### 符号约定

p 且 q $p\wedge q$

p 或 q $p\vee q$

## 逻辑连结词

### 非: $\neg p$

let p = true.
let result = !p

### 合取: $p \wedge q$

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

### 析取: $p \vee q$

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

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

### 逻辑蕴含 $p\models q$

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

### 双条件 $p \leftrightarrow 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 ﬁnal 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 ﬁnal, 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 ﬁnal.

$p\rightarrow r$

d) You get an A on the ﬁnal, 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 ﬁnal and doing every exercise in this book is sufﬁcient 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 ﬁnal.

$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 sufﬁcient 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