Chapter 1 - Logic and Proofs

写在前面

离散数学的笔记对翁老师分享的前辈的笔记有所参考，所以放在前面，文章中讲的不详细的地方，大家可以去阅读学长的笔记

定义

注意

补充、解释

其他

术语对照

参考这就来了(

• conjunction 合取
• disconjunction 析取
• exclusive or 异或
• precedence 优先级

1 Propositional Logic

1.1 Proposition

Definition

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

• Beijing is the captial of China.
• He shouted, “Stop!”(光看这句话我们不知道真假，但是在那一刻地点那一时刻，他要么说了，要么没说，一定可以确定真假)
• x+1=2(这不是命题，因为我们无法判断真假，注意与上一个区别，上一个是我们不知道真假，但可以确定真假，譬如问一下在场的人，而这一个无法确定，因为我们不知道x的取值)
• Open the door.(祈使句，不是陈述句)
  Anyway,it doesn’t matter.

Propositional Logic is the area of logic that deals with propositions.

• Propositional variables: each represents a proposition like “Today is Friday.”
• Truth value:T(if a proposition is true),F
• Logical operators(Connectives) :be used to form compound propositions from existing propositions

1.2 Logical Operators

• Negation
• Conjunction (p和q都真才为真)
• Disjunction (p和q至少有一个为真即为真)
• Exclusive OR (p和q真值不同时为真)

1.2.1 Conditional Operator

Definition

Let and be propositions.The conditional statement(implication),is the proposition “if ,then .”

The conditional statement is false only when is true and is false.

Equivalent Forms

• If p,then q
• p implies q
• q if p
• q when p
• q whenever(every time that,每当，只要) p
• p is sufficient condition for q
• p only if q
  (只有q为真时，p才能是真的，也就是说p can’t be true when q isn’t true,q为假时p为假(事实上，这个命题就只规定了这一件事)，所以p为真q为假时这个命题为假；如果p是假的，那么q是真是假这个命题都是对的，因为这个命题只要求p是真的时，q必须是真的)
• 让我们举个例子，我去上课only if我醒了，即只有我醒了，我才会去上课，但这并不说明我一定去上课了，其实就是在说我醒了是我去上课的必要条件，一定要我醒了，我才能去上课，而不是如果我醒了我就去上课(如果你因此更晕了，那就记住它或者忘掉我所说的orz)
• unless (q是真的，除非p是假的，也就是p为真时q一定为真，p为假时这个命题一定正确，因为没说p是假的时对q有什么要求，而p是假的但q是真的时这个命题就是假的，因此它与implication等价)

Converse of Conditional Statement :

二者不一定等价

Inverse of Conditional Statement :

二者不一定等价

Contrapositive of Conditional Statement :

二者等价
When two compound propositions always have the same truth value in all possible cases we call them equivalent

1.2.2 Biconditional Operator

is the position “p if and only if q.”
即

p和q同时为真或同时为假时，为真

如果是永真式，那么称p和q是逻辑等价的，其中p和q是复合命题
注意一定要求是永真式，如果说：如果是真的，那么p和q等价，这样是不对的
例如，p:今年是2026年，q:我今天喝了水
那么在2026年，有一天我喝了水，那么那一天就是真的，我就可以得到今年是2026年等价于我今天喝了水，即如果我今天喝了水，那么今年是2026年，这是不合理的，(而且根据上面的定义，这意味着我今天喝水和今年是2026年一定同时成立或同时不成立)我们必须要求是恒真的，即p和q只可能同时为真或者同时为假，不能有其他情况，而这个例子中，完全可以是今年是2027年而我今天喝了水，就是假的了

如果你还是很晕，那么记住下面这点：
我们说复合命题p和复合命题q等价，只是在陈述“p和q的真值一定一样”或“永远是真的”，并不是一个复合命题，虽然确实可能为真可能为假，但更多时候我们把它看作一种关系的描述“p和q的真值一定一样”

另一方面，是真的只是说明p是真的，q是真的，或p是假的，q是假的，它就像是真值表中某一行的各种值，并没有说明“p和q只能同时真或同时假”，而更多是一种对p和q真值的限制的陈述

1.2.3 Precedence of Logical Operators

Operator	Precedence
	1
	2
	3

1.3 Translation

You can access the Internet from campus only if you are a computer science major or you are not a freshman.
Let
a:”you can access the Internet from campus”
c:”you are a cs major”
f:”you are a freshman”

1.4 Consistent System Specifications

Definition

A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true.

2 Propositional Equivalences

2.1 Classification of Compound Propositions

• Tautology:compound proposition that is always true
• Contradiction:compound proposition that is always false
• Contingency neither a tautology nor a contradiction
  For example, is a tautology

2.2 Logical Equivalences

Definition

The compound propositions and are called logically equivalent if is a tautology.
Notation:

Name	Equivalence
Identity laws
Domination laws
Idempotent laws(幂等律)
Commutative laws
Associative laws
Distributive laws
De Morgan’s laws
Absorption laws
Implication law
Equivalence law

2.3 Propositional Satisfiability

A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true.When no such assignments exist,the compound proposition is unsatisfiable.

3 Predicates and Quantifiers

3.1 Predicate

Definition

A predicate (propositional function) is a statement that contains variables.Once the values of the variables are specified,the function has a truth value.

• ””,and is false
• ” is the ’s best friend”

3.2 Quantifiers

Predicate Logic:the area of logic that deals with predicate and quantifiers.

3.2.1 Universal Quantification

Definition

A universal quantification of ,denoted by ,is the statement “P(x) for all values of x in the domain.”

Domain:range of the possible values of the variable x
An element for which P(x) is false is called a counterexample(反例) of

Example

1. The truth value of is false if the domain consists of all real numbers.

2. Express the following statement as a universal quantification:
   “All lions are fierce.”

Let Q(x) denote the statement “x is fierce.”
(1) Assuming that the domain is the set of all lions.

(2) Assuming that the domain is the set of all creatures.
P(x): “x is a lion.”

3.2.2 Existential Quantification

Definition

An existential quantification of P(x),denoted by ,is the statement “There exists an element x in the domain such that P(x).”

Example

Express the following statement as an existential quantification.
“Some real numbers are rational numbers.”

Let Q(y): y is a rational number
(1) Assuming that the domain is the set of all real numbers.

(2) Assuming that the domain is the set of all complex numbers.Let R(y): y is a real number

存在唯一：

3.2.3 Quantifiers with Restricted Domains

Example

Domain: the real numbers
means for every real number with > 0,
It’s logically equivalent to

3.2.4 Precedence of Quantifiers

The quantifiers have higher precedence than all logical operators from propositional calculus.

3.2.5 Binding Variables

When a quantifier is used on the variable x,we say that this occurence of the variable is bound(受约束的).

A variable neither quantified nor specified with a value is said to be free.

All the variables in a propositional function must be quantified or set equal to a particular value to turn it into a proposition.
例如中x被存在量词作用，是约束变元，y是自由变元，当然这不是命题，可以是谓词，根据上面所述，y也必须被赋值或者被量词作用才能变成命题
(一般默认x和y的取值范围是一样的，不清楚，问了几个ai这么说的)

Scope of a quantifier:the part of a logical expression to which the quantifier is applied.
这里或操作符左右的x是不一样的，比如左边可以存在x=1，这时右边是要任意的x属于论域，这两个x不是一个东西

3.3 Logical Equivalences Involving Quantifiers

Definition

Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value for every predicate substituted into these statements and for every domain of discourse used for the variables iin the expressions.

(The domain is same)

x is not occurring in A

Equivalence	Proof
	分A为T或F两种情况证明
上式任意或存在选一个，与变成或或者或变成与，四种情况都成立
上式任意变成存在仍成立
	先去掉箭头，再利用第三行
上式任意、存在互换仍成立

3.4 Translation

Example

All lions are fierce.
Some lions do not drink coffee.

P(x):x is a lion
Q(x):x is fierce
R(x):x drinks coffee
Assume the domain consists of all creatures.

(1)
(2)
注意不能是，这样的话并不是说有些狮子不喝咖啡，事实上如果x不是狮子，这个命题也是真的，就不是原来的意思了
同理(1)中不能用与，那样就变成所有的生物都是狮子而且很凶狠

3.5 Nested Quantifiers

Two quantifiers are nested if one is within the scope of the other.
可理解为遍历论域中每个x，都要存在一个y满足C(x,y)

这里是在的scope里的,体现在C(x,y)里的x受前面量词的论域限制

也可以理解成，其中为，P(x)里的x在量词的scope里

Example

Everyone has exactly one best friend.
Domain:All people

B(x,y): “y is the best friend of x.”

注意x后的括号要一直括到最后，否则B(x,z)里的x就没被量词作用，也没赋值，就不是命题
同理y,z右侧的括号也要括到最后
也可以写成嵌套量词

过程是先遍历论域中的x，对每一个x要找到一个y满足：遍历论域中的z，即成立

3.5.1 The Order of Quantifiers

The order of nested quantifiers matters if quantifiers are of different types.

Example

论域：实数

存在一个x，使得对所有y，x+y=1，这是假命题

对任意y，都存在一个x使得x+y=1，这是真命题

3.5.2 Negating Nested Quantifiers

Successively apply the rules for negating statements involving a single quantifier.
这时这样理解的好处就凸显了
可理解为遍历论域中每个x，都要存在一个y满足Q(x,y),这里是在的scope里的，也可以理解成，其中为，P(x)里的x在量词的scope里

例如
等价于
等价于
等价于

4 Functionally Complete

Definition

A set of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only this set of logical operators.

比如与、或、非构成的逻辑操作符集合就是functionally complete的
与非也可以(跟数逻联动了)

5 Propositional Normal Forms

Literal(字面量):或者

Disjunctions (conjunctions) with one or more literals as disjuncts (conjuncts) are called disjunctive (conjunctive) clauses.

例如
是析取子句
是析取子句，也可以是合取子句
不是clause(子句)

5.1 Normal Forms(CNF&DNF)

A conjunction with one or more disjunctive clauses is said to be in conjunctive normal form.

A disjunction with one or more conjunctive clauses is said to be in disjunctive normal form.

例如
是CNF
如果看作disjunctive clause就是CNF，看作conjunctive clause就是DNF
是CNF(两个disjunctive clause)，也可以是DNF(看作一个conjunctive clause)

5.2 How to Obtain Normal Forms

1. 利用和和去掉箭头
2. 德摩根律去掉非
3. 利用分配律统一符号