离散数学之逻辑
Connectives
Negation (not): $\lnot$ (unary connective) 非
Conjunction (and): $\land$ (binary connective) 与
Disjunction (or): $\lor$ (binary connective) 或
Exclusive or: $\bigoplus$ (binary connective) 异或
Implication (if … , then): $\rightarrow$ (binary connective)
Biconditional (if and only if): $\leftrightarrow$ (binary connective)
Combining proposition
Examples
Let two atomic propositions p and q be “It is raining” and “I am at classroom”.
$\lnot$ p (“not p”): It is not the case that it is raining, or it is not raining.
p $\land$ q (“p and q”): It is raining and I am at classroom.
p $\or$ q (“p or q”): It is raining or I am at classroom.
p $\bigoplus$ q (“p exclusive or q”): It is raining or I am at classroom,but not both.
p $\rightarrow$ q (“if p, then q”): If it is raining, then I am at classroom.
p $\leftrightarrow$ q (“p if and only if q”): It is raining if and only if I am at classroom.
Tautology重言式/永真式 and contradiction 矛盾/永假式
Tautology
A tautology is a statement that is always true, i.e., a propositional form which is always true regardless of the truth values of its variables is called a tautology. Examples:
$r\land\lnot r$
$\lnot(p \land q)=\lnot p \lor \lnot q$
If $p \rightarrow q$ is a tautology, we write p $\Rightarrow$ q;
If p $\leftrightarrow$ q is a tautology, we write p $\Leftrightarrow$ q.
Contradiction
A contradiction is a statement that is always false, i.e., a propositional form which is always false regardless of the truth values of its variables is called a contradiction.
Examples:
$r\land\lnot r$
$\lnot(\lnot(p\land q))\leftrightarrow\lnot p\lor\lnot q$
The negation of any tautology is a contradiction, and the negation of contradiction is a tautology.
Implications 蕴含
if-then
We can write “if p, then q” for $p\rightarrow q$ , but there are other ways to say this. E.g., we can write
(1) q if p
(2) p only if q
(3) when p, then q.
For each of these statements, de ne propositional variables representing each proposition inside the statement and write the proposition form of the statement.
- You will feel dizzy during class if you do not have enough sleep.
- You can get A from this course, only if you work fairly hard.
- When you eat a lot and you do not have enough exercise, then you will get fat.
Only-if
Let p be “you work fairly hard.”
Let q be “you get A from this course.”
Let r be “You can get A from this course, only if you work fairly hard.”
Let’s think about the truth values of r .
Thus, r should be logically equivalent to p ! q. (We write $r\equiv p\rightarrow q$ in this case.)
If and only if
Given p and q, we denote by $p \leftrightarrow q$
the statement “p if and only if q.” It is logically equivalent to $(p \leftarrow q) \land (p \rightarrow q)$
i.e.$p\leftrightarrow q \equiv (p \leftarrow q) \land (p \rightarrow q)$
Precedence of logical operators
Because some rules may be difficult to remember, we will continue to use parentheses so that the order of the disjunction and conjunction operators is clear.
Logic and Bit Operations
A bit is a symbol with two possible values, namely, 0 (false) and 1 (true). A variable is called a Boolean variable if its value is either true or false.
Applications of Propositional Logic
Translating sentences
Example
You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.
Solution:
p = “You can ride the roller coaster;”
q = “you are under 4 feet tall;”
r = “you are older than 16 years old.”
Then the sentence can be translated to
$(q\land\lnot r)\rightarrow \lnot p$ or $p\rightarrow(\lnot q\lor r)$
System specications
Determine whether these system speci cations are consistent?
- “The diagnostic message is stored in the buffer or it is retransmitted”
- “The diagnostic message is not stored in the buffer;”
- “If the diagnostic message is stored in the buffer, then it is retransmitted.”
Let p denote The diagnostic message is stored in the buffer and q denote The diagnostic message is retransmitted.
$p\lor q$
$\lnot p$
$p\rightarrow q$
作业练习剪影
充分必要条件怎么在命题当中表示？
A是B的充分不必要条件： $A\rightarrow B$
A是B的必要不充分条件：$A\leftarrow B$
A是B的充分必要条件：$A\leftrightarrow B$
Let p, q, and r be the propositions
p : Grizzly bears have been seen in the area.
q : Hiking is safe on the trail.
r : Berries are ripe along the trail.
For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area.
$\lnot r\land \lnot p$ 是 q的必要不充分条件，所以 $q\rightarrow (\lnot r\land \lnot p)$但是这还没体现不充分性。所以 $q\rightarrow (\lnot r\land \lnot p)\land \lnot ((\lnot r\land \lnot p)\rightarrow q)$ 是完整答案。也就是既要反应A不能推出B又要反应B能推出A，中间用$\land$ 连接
inclusive or(兼或) 和 exclusive or(异或) 的区别
数学或者英语90分以上者，可以发奖励：这是兼或，意思是数学90分以上的人，英语不到90分;或英语80分以上的人，数学不到90分;或数学和英语都90分以上的人都可以得到奖励。
有2种22元套餐A、B，您可以选择一种：这是异或，意思是你花22元后，可以选择任意一种套餐，但不能同时得到A、B两种套餐，也不会A、B都得不到，这是个二选一的问题。
if…then…的其他表示
下面的语句都可以写成 $p \rightarrow q$
If p , then q
$p$ is sufficient for $q$ 或者 a sufficient condition for $q$ is $p$ 或者 a necessary condition for $p$ is $q$
to $q$,it is sufficient that $p$
It is necessary to $q$ to $p$ 或者 $q$ is necessary for $p $
$p$ implies $q$
$q$ whenever $p$
$p$ only if $q$
$q$ follows from $p$
$q$ unless $\lnot p$
If and only if 的其他表示
If $p$ then $q$ ,if $q$ then $p$
For $p$ it is necessary and sufficient $q$
$p$ only if $q$ , $q$ only if $p$
$p$ excatly $q$
If $p$ then $q$ ,and conversely
converse,contrapositive,inverse
判断真值表有几行
每一个命题，p,q,r,t,s …. 都有T和F两个值可以选。
所以真值表的行数是由多少命题来决定的。有 n个命题，那么就有 $2^n$ 行数据。
求比特串的AND OR XOR
OR 有1就是1
AND 全1才是1
XOR 不一样的才是1
Logical Equivalences
Definition
Compound propositions that have the same truth values in all possible cases are called logically equivalent.
- Compound propositions p and q are called logically equivalent if $p \leftrightarrow q$ is a tautology, denoted as $p \Leftrightarrow q $ or $p \equiv q$
- Remark: Symbol $\equiv$ is not a logical connectives, and $p \equiv q$ is not a proposition. $p \equiv q$ 不是命题！
- One way to determine whether two compound propositions are equivalent is to use a truth table.
De Morgan’s laws
$\lnot (p\land q)\equiv \lnot p\lor \lnot q$
$\lnot (p\lor q)\equiv \lnot p\land \lnot q$
德摩根律还可以推广到 $p_n$
$\lnot(p1\land p_2\land\cdots\land p_n)\equiv \lnot p_1\lor\lnot p_2\lor\cdots\lnot p_n$ 也就是 $\lnot\Lambda^n{i=1}\equiv V_{i=1}^n\lnot p_i$
$\lnot(p1\lor p_2\lor\cdots\lor p_n)\equiv \lnot p_1\land\lnot p_2\land\cdots\lnot p_n$ 也就是 $\lnot V^n{i=1}\equiv \Lambda_{i=1}^n\lnot p_i$
The truth table can be used to determine whether two compound propositions are equivalent.
Table of logical equivalence
| Equivalence | name |
|---|---|
| $p\land T\equiv p$ $p\lor F\equiv p$ |
Identity Laws 同一律 |
| $p\land p\equiv p$ $p\lor p\equiv p$ |
idempotent Laws幂等律 |
| $(p\land q)\land r\equiv p\land (q\land r)$ | Associative Laws 结合律 |
| $p\lor(p\land q)\equiv p$ $p\land(p\lor q)\equiv p$ |
Absorption Laws 吸收律 |
| $p\land\lnot p \equiv F$ $p\lor\lnot p \equiv T$ |
Negation laws 否定律 |
| $p\lor T\equiv T$ $p\land F\equiv F$ |
Domination laws 零律 |
| $p\land q\equiv q\land p$ $p\lor q \equiv q\lor p$ |
Commutative laws 交换律 |
| $(p\land q)\lor r\equiv (p\lor r)\land(q\lor r)$ $(p\lor q)\land r\equiv (p\land r)\lor(q\land r)$ |
Distributive laws 分配律 |
| $\lnot (p\land q)\equiv \lnot p\lor \lnot q$ $ \lnot (p\lor q)\equiv \lnot p\land \lnot q$ |
De Morgan’s laws 德摩根律 |
| $\lnot(\lnot p)\equiv p$ | Double negation law |
Equivalence of implication
Logical equivalences involving conditional statements
$p\rightarrow q\equiv \lnot p\lor q$ 这是最重要的，一定得记住
$p\rightarrow q\equiv\lnot q\rightarrow \lnot p$
$\lnot p \rightarrow q \equiv p\lor q$
$p\land q \equiv\lnot(p\rightarrow \lnot q)$
$\lnot(p\rightarrow q)\equiv p\land \lnot q$
$p\rightarrow(q\land r)\equiv (p\rightarrow q)\land (p\rightarrow r)$ 这四行也是重点
$p\rightarrow(q\lor r)\equiv (p\rightarrow q)\lor (p\rightarrow r)$
$(p\lor q)\rightarrow r \equiv (p\rightarrow r)\land(q\rightarrow r)$
$(p\land q)\rightarrow r \equiv (p\rightarrow r)\lor(q\rightarrow r)$
Logical equivalences involving biconditional statements
$p\leftrightarrow q\equiv(p\rightarrow q)\land(q\rightarrow p)$
$p\leftrightarrow q\equiv \lnot p\leftrightarrow \lnot q$
$p\leftrightarrow q\equiv (p\land q)\land(\lnot p\land\lnot q)$
$\lnot(p\leftrightarrow q)\equiv p\leftrightarrow \lnot q$
Propositional satistiab ility 可满足式
A compound proposition is satis able if there is an assignment of truth values to its variables that makes it true.
Determine whether each of the compound propositions
$(p\lor\lnot q)\land(q\lor\lnot r)\land(r\lor \lnot p)\equiv(q\rightarrow p)\land(r\rightarrow q)\land(p\rightarrow r)$
Note that $(p\lor\lnot q)\land(q\lor\lnot r)\land(r\lor \lnot p)$ is true when the three variable p, q, and r have the same truth value.
Hence, it is satis able as there is at least one assignment of truth values for p, q, and r that makes it true.
Applications of satisability
Sudoku puzzle
Predicates 谓词
“x is greater than 3” has two parts: variable x (the subject of the statement), and predicate P “is greater than 3”, denoted as P(x) : x > 3.
- Statement P(x) is the value of the propositional function P at x;
- Once variable x is fi xed, statement P(x) becomes a proposition and has a truth value. e.g., P(4) (true) and P(2) (false)
- Let A(x) denote “Computer x is under attack by an intruder”. Assume that CS2 in the campus is currently under attack by intruders. What are truth values of $A(CS_1)$, and $A(CS_2)$?
- Let Q(x, y) denote the statement “x = y + 3”. What are the truth values of the propositions Q(1, 2) and Q(3, 0)?
In general, a statement involving n variables $x1, x2,\cdots ,x_n $ can be denoted by $P(x_1, x_2, … x_n)$, where P is also called an n-place predicate or a n-ary predicate, and $x1, x2, \cdots, x_n$ is a n-tuple.
Quantifiers 量词
Quanti cation expresses the extent to which a predicate is true over a range of elements. In general, all values of a variable is called the domain of discourse (or universe of discourse), just referred to as domain.
The universal quanti cation of P(x) is the statement “P(x) for all values of x in the domain”. Notation $\forall xP(x)$ denotes the universal quanti cation of P(x), where $\forall$ is called the universal quanti er. An element for which P(x) is false is called a counterexample of $\forall xP(x)$
The existential quanti cation of $P(x)$ is the proposition “There exists an element x in the domain such that $P(x)$”. Notation $\exists xP(x) $ denotes the existential quanti cation of $ P(x)$, where $\exists$ is called the existential quanti er.
Examples
Universal quanti cation
- Let $P(x)$ be “$x + 1 > x$”. What is the truth value of $\forall xP(x)$ for $\forall x \in R$?
Note that if the domain is empty, then $\forall xP(x)$ is true for any propositional function $P(x)$ because there are no elements x in the domain for which $P(x)$ is false. - Let P(x) be “$x^2 > 0$”. What is the truth value of $\forall xP(x)$ for $\forall x \in Z$? (Note that $x = 0$ is a counterexample because $x^2 = 0$)
Existential quanti cation
Let P(x) denote “$x > 3$”. What is the truth value of $\forall xP(x)$ for $\forall x\in R$ ?
Let P(x) be “$x^2 > 0$”. What is the truth value of $\exists xP(x)$ for $\forall x \in Z$?
Remarks
Quantiers with restricted domains
What do the statements $ \forall x < 0(x^2 > 0) $ and $\exists y > 0(y^2 = 2)$ mean, where the domain in each case consists of the real numbers?
- The statement $\forall x < 0(x^2 > 0) $ states that for every real number x with $x < 0,x^2 > 0$, i.e., it states “The square of a negative real number is positive”. This statement is the same as $\forall x(x < 0 \rightarrow x^2 > 0)$
- The statement $\exists y > 0(y^2 = 2)$ states “There is a positive square root of 2”, i.e., $\exists y(y > 0 \land y^2 = 2).$
- Note that the restriction of a universal quanti cation is the same as the universal quanti cation of a conditional statement.
- On the other hand, the restriction of an existential quanti cation is the same as the existential quanti cation of a conjunction.
Precedence of quantiers and binding variables
Logical equivalences involving quantiers
Statements involving predicates and quanti ers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation $S \equiv T$ to indicate that two statements S and T involving predicates and quanti ers are logically equivalent.
Table of logical equivalence
Applications of Quantifiers
Quantiers in system specications
Use predicates and quanti ers to express the system speci cations “Every mail message larger than one megabyte will be compressed” and “If a user is active, at least one network link will be available.”
Let $S(m,y) $be “Mail message m is larger than y megabytes“ where variable x has the domain of all mail messages and variable y is a positive real number, and let $C(m)$ denote “Mail message m will be compressed.“ Then “Every mail message larger than one megabyte will be compressed“ can be represented as $\forall m(S(m, 1) \rightarrow C(m))$.
Let $A(u)$ represent “User u is active,“ where variable u has the domain of all users, let $S(n, x)$ denote “Network link n is in state x,” where n has the domain of all network links and x has the domain of all possible states for a network link. Then “If a user is active, at least one network link will be available“ can be represented by $\exists uA(u)\rightarrow \exists nS(n, available)$
Nested Quantifiers 嵌套量词
Nested quantiers
Nested quanti ers is one quanti er within the scope of another. For example, $\forall x\exists y(x + y = 0)$. Note that everything within the scope of a quanti er can be thought of as a propositional function.
$\forall x\exists y(x + y = 0)$ is the same thing as $\forall xQ(x)$, where Q(x) is $\exists yP(x, y)$, where $P(x, y)$ is $x + y = 0$
Please translate following nested quanti ers into statements
Order of quantiers
It is important to note that the order of the quanti ers is important, unless all the quanti ers are universal quanti ers or all are existential quanti ers.
Applications of nested quantiers
Negation of nested quantiers
作业剪影
不利用真值表，证明永真式
我们首先要了解这些定律
然后要规范格式
如果不限方法的话，看看命题数量。如果命题数量只有2个，那么使用真值表法更容易，如果命题数量比较多，那么使用逻辑等价，一定也能推出来。
Determine whether each of thes compound propositions is satisfiable
这类题是让我们找出是否存在一种情况让下面的命题成立。
同样当命题数少的时候，我们可以直接利用真值表。命题数量多的时候，我们先化简，再利用真值表找出是否满足。
只要有一个满足，那么这个命题就是 satisfiable 的
Rules of Inferences
Argument 论断
De nition
An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises or hypotheses and the fi nal proposition is called the conclusion.
Valid argument
De nition
We say that the statement is valid if when all hypotheses are true, the conclusion must be true as well. In that case, we say that the conclusion logically follows from the hypotheses.
Example
Proof Methods and Strategy
我们要搞懂几个术语
All but the final proposition in the argument are called premises (前提假定) or hypotheses (假定) and
the final proposition is called the conclusion.
We say that the statement is valid if when all hypotheses are true, the conclusion must be true as well. In that case, we say that the conclusion logically follows from the hypotheses.
几个重要的结构要熟悉：
Modus ponens 肯定前件式
Modus tollens 否定后件式
hypothelical syllogism 假言三段论
disjunctive syllogism 选言三段论
Addition
Simpli cation
Conjunction
Resolution
Inference rules for quanti ed statements
Universal instantiation
Universal generalization
Existential instantiation
Existential generalization
Proof by contraposition
Proofs by contradiction 反证法
We want to prove that proposition p is true. To do so, we rst assume that p is false, and show that this logically leads to a contradiction. This means that it is impossible for p to be false; hence, p has to be true. This is called a proof by contradiction or reductio ad absurdum.
Proofs by cases
Proofs by cases in propositional logic
