We should always analyze and seek to understand the situation given. This often calls for attributes we cannot learn in a book, such as insight and creativity. Merely trying to apply formulas or invoke rules will not get us very far either in proving result or doing enumeration problems.
Propositional Logic
Statement
A Statement is a declarative sentence that can be True(1) or False(0).
Statements(or propositions), are declarative sentences that are either true or false. We do not regard sentences such as the exclamation or the comman.
Questions or Imperatives which can not be true or false is no logic
问题或者是祈使语句，因为他们没有 “真” 或者 “假” 所以他们没有逻辑可言
Propositions（命题） are denoted with capital letters P,Q,R,... Lowercase letters p,q,r,... are used for general propositions that have no meaning => Use them for general proofs.
命题使用大写字母来表示，小写字母表示一个命题的实例，他们没有具体的意义，一般用于论证
There is no way to break them down into anything simpler, are considered to be primitive statements.
原子命题：没有办法把它们分解成任何更简单的语句。原子命题通过连接词连接成复合命题
Connectives
Combine two or more statements into a compound statement, using the following logical connectives.
fundamentals\Logic
which denotes its negation and is read “Not p”
fundamentals\Logic
The connectives but and and convey meaning
fundamentals\Logic
or
fundamentals\Logic
statement p is called the hypothesis of the implication; q is called the conclusion;
If p, then q.
p is sufficient for q（p 对 q 来说是充分的）
p is a sufficient condition for q (p 是 q 的充分条件)
q is necessary for p（q 对 p 来说是必要的）
q is a necessary condition for p (q 是 p 的必要条件)
p only if q (？？)
fundamentals\Logic
p if and only if q as p iff q
举个栗子
s -> t: If you do your homework, then you will get to watch the baseball game.
t -> s: You will get to watch the baseball game only if you do your homework.
s has the truth value 0, q has the truth value 1. Means is you do not do your homework, but still watch the baseball game. Perhaps you watch the game because you mother not at home. Or maybe other reason. You has not gone against the resolution s->t. we accept this compound statement as true, assigning it the truth value 1.
In computer science:
// For p false, the computer goes to the next instruction in the program sequence.
if(hypothesis expression logical statement has truth value 0 or 1) {
executable statement; // q is not one of the logical statements
}
The decision structure if p then q else r, q is executed when p is true and r is executed when p is false.
举个栗子：在高级编程语言中我们经常见到 if p then q，我们习惯性的读作
fundamentals\Logic
。其实并不是 ，从逻辑上讲 if p then q 因该等价于
fundamentals\Logic
。而 if p then q else r 应该等价于
fundamentals\Logic
p is a Well-formed formula (wff)
fundamentals\Logic
is a Well-formed formula
fundamentals\Logic
is a Well-formed formula
fundamentals\Logic
is a Well-formed formula
fundamentals\Logic
is a Well-formed formula
怎样从自然语言提取复合命题？我们应该先识别命题的结构，然后填充命题
识别逻辑连接词（wff）
在识别出的连接词结构中填充命题
复合命题不一定有意义：使用逻辑连接词连接的命题不需要有意义
We must avoid Writing a compound statement such as
fundamentals\Logic
, Without parentheses to indicate which of the connectives disjunction and conjunction should be applied first. We are dealing with
fundamentals\Logic
or
fundamentals\Logic
我们应该注意连接顺序，必要时应该打个括号，比如
fundamentals\Logic
或者是
fundamentals\Logic
TruthTable
Truth tables will tell us all possible outcomes of statements and connectives. And all connectives take a truth value and output a new truth value, so depending on the connective the truth values can change.
We try to show that the conclusion q follows logically from these given statements:
fundamentals\Logic
We can do P is logically equivalent to Q by the truth table column outputs exactly the same values and the same order.
Negation
P
fundamentals\Logic
1
1
fundamentals\Logic
Conjunction
p
Q
fundamentals\Logic
1
1
1
1
1
The minimum of P and Q
Disjunction
P
Q
fundamentals\Logic
1
1
1
1
1
1
1
The maxmum of P and Q
Conditional
P
Q
fundamentals\Logic
fundamentals\Logic
1
1
1
1
1
1
1
fundamentals\Logic
eg: If it is sunny, I will wear sunscreen. If P didn't happen (P = 0) then it's true, because I only lying to you when P = 1 and Q = 0 . And
fundamentals\Logic
means P has more constraints then Q.
Biconditional
P
Q
fundamentals\Logic
1
1
1
1
1
1
P == Q
ExclusiveOr
P
Q
fundamentals\Logic
fundamentals\Logic
1
1
1
1
1
1
fundamentals\Logic
Proofs
P
Q
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
fundamentals\Logic
conjunction elimination
XOR
P
fundamentals\Logic
fundamentals\Logic
1
1
fundamentals\Logic
P nand Q
P
Q
P ↑ Q
fundamentals\Logic
1
1
1
1
1
1
1
fundamentals\Logic
(P ↑ Q) ↑ (P ↑ Q)
fundamentals\Logic
(P ↑ P) ↑ (Q ↑ Q)
Logical Equivalence: Develop an idea of when two such entities are essentially the same.
Two statements s1, s2 are said to be logically equivalent, and we write s1 <=> s2, when the statement s1 is true(respectively, false) if and only if the statement s2 is true(respectively, false)
Logic Law
We can use logical equivalences to reduce complex formulas into simpler ones.
fundamentals\Logic
to denote any tautology and the symbol
fundamentals\Logic
to denote any contradiction.
Tautology Contradiction
fundamentals\Logic
fundamentals\Logic
1
1
1
...
...
DeMorgan’s Laws:
fundamentals\Logic
DeMorgan’s
通过 truth table 我们得到以下规律
The Laws of Logic:
fundamentals\Logic
Law of Double Negation
fundamentals\Logic
fundamentals\Logic
DeMorgan’s Laws
fundamentals\Logic
fundamentals\Logic
Idempotent Laws
fundamentals\Logic
fundamentals\Logic
Distributive Laws
fundamentals\Logic
fundamentals\Logic
Absorption Laws
fundamentals\Logic
fundamentals\Logic
Identity Laws
fundamentals\Logic
fundamentals\Logic
Domination Laws
fundamentals\Logic
fundamentals\Logic
Commutative Laws
fundamentals\Logic
fundamentals\Logic
Associative Laws
fundamentals\Logic
fundamentals\Logic
Inverse Laws
fundamentals\Logic
Conditional Laws
The dual of s, denoted
fundamentals\Logic
s:
fundamentals\Logic
The dual of s is
fundamentals\Logic
:
fundamentals\Logic
and If
fundamentals\Logic
then
fundamentals\Logic
fall naturally into pairs.
We replace one or more occurrences of p by q. Then this replacement yields the compound statement
are called the premises of the argument, and the statement q is the conclusion for the argument. the truth of the conclusion q is deduced or inferred from the truth of the premises
fundamentals\Logic
if p, q are arbitrary statements such that
fundamentals\Logic
is a tautology, then we say that p logically implies q and we write
fundamentals\Logic
to denote this situation.
We can constructing truth tables to valid argument, but we want to avoid even larger tables. So we are persuaded to develop a list of techniques called rules of inference that will help us: to consider only the cases wherein all the premises are true.
The number x+2 is an even integer, we find it is an open statement that contains the single variable x.
These allowable choices constitue what is called the universe or universe of discourse for the open statement.
eg: q(x, y): The numbes y+2, x-y, and x+2y are all even integers.
Many postulates, definitions, and theorems in mathematics involve statements that are quantified open statements.
These result from the two types of quantifiers, which are called the existential ∃ and the universal quantifiers ∀.
Quantifiers
fundamentals\Logic
: "For all x, x is P" （The Universal Quantifiers）
fundamentals\Logic
: "For some x, s is P" （The Existential Quantifiers）
x is said to be a bound variable – it is bound by the existential quantifier ∃ or ∀.
statement
true
false
fundamentals\Logic
For some(at least one) a in the universe,
fundamentals\Logic
is true.
For every a in the universe,
fundamentals\Logic
is false.
fundamentals\Logic
For every replacement a from the universe,
fundamentals\Logic
is true.
There is at least one replacement a from the universe for which
fundamentals\Logic
is false
fundamentals\Logic
For at least one choice a in the universe,
fundamentals\Logic
is false, so its negation
fundamentals\Logic
is true
For every replacement a in the universe,
fundamentals\Logic
is true.
fundamentals\Logic
For every replacement a in the universe,
fundamentals\Logic
is false, so its negation
fundamentals\Logic
is true
There is at least one replacement a from the universe for which
fundamentals\Logic
is false and
fundamentals\Logic
is true.
we write
fundamentals\Logic
and say that
fundamentals\Logic
logically implies
fundamentals\Logic
.
For every real number n, there is a real number m such that
fundamentals\Logic
fundamentals\Logic
Given two rationals x and y,
fundamentals\Logic
will also be rationals
fundamentals\Logic
Negating Quantifiers
Define
fundamentals\Logic
for a universe with elements
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
For a prescribed universe and any open statements p(x), q(x) in the variable x:
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
举个栗子：
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
when a statement involve both existential and universal quantifiers, however, we must be careful about the order in which the quantifiers are written.
fundamentals\Logic
consequently
fundamentals\Logic
Translating mathematical statements:
After we translate a mathematical statement into symbolic form, the rules we have learned should then apply when we want to determine such related statements as the negation.
当我们把一个数学语句转换成符号形式的时候，当我们否定它时，我们所学到的规则就派上了用场。
be very careful and precise about the meanings of statements
但是，在转换成数学语句的时候。对陈述的意思要非常小心和准确，栗如：
For every integer n we call n even if it is divisible by 2
对于每一个整数n，我们称之为偶数，如果它可以被2整除
fundamentals\Logic
: n is an even integer
fundamentals\Logic
: n is divisible by 2
fundamentals\Logic
the given quantified statement (in the preceding definition) is an implication. However, the situation here. What appears to be stated is not what is intended. The intention is for the reader to interpret the given definition as
Every Student is majoring in math or computer science.
fundamentals\Logic
For all real x, y, x > y if
fundamentals\Logic
fundamentals\Logic
For all
fundamentals\Logic
, there is an
fundamentals\Logic
such that
fundamentals\Logic
when
fundamentals\Logic
fundamentals\Logic
If
fundamentals\Logic
means "there exists a unique x such that P(x)"
术语解释
定义：给出的东西（不需要论证）
定理：需要证明的事情
直接证明：如果
fundamentals\Logic
那么
fundamentals\Logic
，假设
fundamentals\Logic
推导
fundamentals\Logic
的过程
fundamentals\Logic
证明：如果 5|2a，
fundamentals\Logic
，那么 5|a
假设 5|2a，
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
5 是奇数，2a是偶数
fundamentals\Logic
fundamentals\Logic
fundamentals\Logic
分支证明：证明
fundamentals\Logic
假设
fundamentals\Logic
证明
fundamentals\Logic
假设
fundamentals\Logic
证明
fundamentals\Logic
证明逆反命题：证明
fundamentals\Logic
假设
fundamentals\Logic
证明
fundamentals\Logic
反证法：证明
fundamentals\Logic
假设
fundamentals\Logic
找出矛盾
fundamentals\Logic
断言
fundamentals\Logic
the method of exhaustion: If we are confronted with a situation in which the universe is larger but within the range of a computer that is available to us, then we might write a program to check all of the individual cases.（穷举法）
Certain of these consequences that follw rather immediately from a theorem are termed corollaries.（推论）
The Rule of Universal Specification:If an open statement becomes true for all replacement by the members in a given universe, then that open statement is true for each specific individual member in that universe.(A bit more symbolically –if p(x) is an open statement for a given universe, and if ∀x p(x) is true, then p(a) is true for each a in the universe.)
The word generic is applied to the element c here because it indicates that our choice(for c) must share all of the common characteristics of the elements for the given universe.
The Rule of Universal Generalization: If an open statement p(x) is proved to be true when x is replaced by any arbitrarily chosen element c from our universe, then the universally quantified statement ∀x p(x) is true. Furthermore, the rule extends beyond a single variable. So if, for example, we have an open statement q(x, y) that is proved to be true when x and y are replaced by arbitrarily chosen elements from the same universe, or their own respective universes, then the universally quantified statement ∀x ∀y q(x, y) [or, ∀x,y q(x,y)] is true. Similar result hold for the cases of three or more varables.
eg: Let n be an integer. We call n even if n is divisible by 2—that is , if there exists an integer r so that n=2r. If n is not even , then we call n odd and find for this case that there exists an integer s where n=2s+1
Assumption
Result Derived
Contraposition
¬ q(m)
¬ p(m)
Contradiction
p(m) and ¬ q(m)
F0
because it will provide us with a framework to fall back on whenever we doubt whether a given attempt at a proof really dose the job If in doubt, we have our study of logic to supply us with a somewhat mechanical but strictly objective means to help us decide
