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
