Logic Introduction

邏輯的世界 Logic 陳鍾誠 2006 年於金門

大綱 Outline • Boolean Logic ( 布林邏輯 )

• First-Order Logic ( 一階邏輯 )

何謂邏輯 ? What is Logic ? • A world of true and false. • Data –T , F

• Function – And (&) – Or (|) – Not (-)

邏輯系統的種類 Types of Logic • Propositional logic ( 命題邏輯 ) – Also known as Boolean Logic (§1.1-1.2): – Basic definitions. (§1.1) – Equivalence rules & derivations. (§1.2)

• Predicate logic ( 述詞邏輯 或 謂詞邏輯 ) – Also known as First-Order Logic (§1.3-1.4) – Predicates. – Quantified predicate expressions. – Equivalences & derivations.

述詞邏輯 Propositional Logic Propositional Logic is the logic of compound statements built from simpler statements using so-called Boolean connectives. Some applications in computer science: • Design of digital electronic circuits. • Expressing conditions in programs. • Queries to databases & search engines.

George Boole (1815-1864)

述詞邏輯的基本運算 Propositional Logic – Operators Formal Name

Nickname Arity

Symbol

Negation operator

NOT

Unary

¬

Conjunction operator

AND

Binary

∧

Disjunction operator

OR

Binary

∨

Exclusive-OR operator

XOR

Binary

⊕

Implication operator

IMPLIES

Binary

→

Biconditional operator

IFF

Binary

↔

運算一：反相 Negation operator - NOT

p ¬p T F F T

運算二：及 Conjunction operator – AND p F F T T

q F T F T

p∧q F F F T

運算三：或 Disjunction operator – OR p F F T T

q F T F T

p∨ q F T T T

述詞邏輯的表示式 Expressions of Propositional Logic • Use parentheses to group sub-expressions – Example : • m : male • c : child • m ∧c : male child (boy)

– Example : • f ∧(g ∨s)

運算四：互斥或 Exclusive-Or – XOR p F F T T

q p⊕ q F F T T F T T F

自然語言的語義不清楚 Natural Language is Ambiguous Note that English “or” can be ambiguous regarding the “both” case! “Pat is a singer or Pat is a writer.” “Pat is a man or Pat is a woman.” Need context to disambiguate the meaning! For this class, assume “or” means inclusive.

p F F T T

q p "or" q F F T T F T T ?

運算五：導致 The Implication Operator • p → q means p implies q. – If p is true, then q is true; – but if p is not true, then q could be either true or false.

• Example : – E.g., let p = “You study hard.” q = “You will get a good grade.” – p → q = “If you study hard, then you will get a good grade.” (else, it could go either way)

pq 的真值表 Implication Truth Table • p → q is false only when p is true but q is not true. • p → q does not say that p causes q! • p → q does not require that p or q are ever true! • E.g. “(1=0) → pigs can fly” is TRUE!

p F F T T

q p→q F T T T F F T T

Imply 運算  的範例 Examples of Implications • “If this lecture ends, then the sun will rise tomorrow.” True or False? • “If Tuesday is a day of the week, then I am a penguin.” True or False? • “If 1+1=6, then Bush is president.” True or False? • “If the moon is made of green cheese, then I am richer than Bill Gates.” True or False?

三種反運算 Converse, Inverse, Contrapositive Some terminology, for an implication p → q: • Its converse is: q → p. • Its inverse is:

¬p → ¬q.

• Its contrapositive:¬q → ¬ p. • One of these three has the same meaning (same truth table) as p → q. Can you figure out which?

p → q = -q → -p 兩者相等 How do we know for sure? Proving the equivalence of p → q and its contrapositive using truth tables:

p F F T T

q ¬ q ¬ p p→ q ¬ q→ p ¬ F T T T T T F T T T F T F F F T F F T T

利用真值表來證明 Proving Equivalence via Truth Tables • -(-p∧-q) = p∨q Ex. that p∨ ⇔p ¬(¬p ¬q). p qProve p∨ q ¬ p ¬ qq ¬ q ∧¬ (¬ p∧ q) ∧ ¬ ¬ T T T F FF F T F F T FT T TF T F T F T TT T F F F T • Demorgan’s Theorem : ( 笛摩根定律 )

p q = p + q = p+q

p ↔ q 的真值表 Biconditional Truth Table • p ↔ q means that p and q have the same truth value. • Note this truth table is the exact opposite of ⊕’s! – p ↔ q means ¬(p ⊕ q)

• p ↔ q does not imply p and q are true, or cause each other.

p F F T T

q p ↔q F T T F F F T T

布林運算總整理 Boolean Operations Summary • We have seen 1 unary operator (out of the 4 possible) and 5 binary operators (out of the 16 possible). Their truth tables are below.

p F F T T

q F T F T

p p∧ q p∨ q p⊕ q p→ q p↔ q ¬ T F F F T T T F T T T F F F T T F F F T T F T T

布林運算的幾種符號表達法 Some Alternative Notations Name: Propositional logic: Boolean algebra: C/C++/Java (wordwise): C/C++/Java (bitwise): Logic gates:

not and or xor implies iff ¬∧ ∨ ⊕ → ↔ p pq + ⊕ ! && || != == ~ & | ^