• Logic is ”the study of reasoning”

Propositions

• A proposition (ประพจน์) is a declarative sentence that is either TRUE or FALSE, but no both.
  • ประโยคบอกเล่าหรือประโยคปฏิเสธที่ เป็นจริงหรือเป็นเท็จอย่างใดอย่างหนึ่ง เท่านั้น!!

Compound Propositions

• We can build composite propositions from simpler propositions by using 5 connectives:
  • and ($\land$), or ($\lor$), not ($\neg$), implies ($\rightarrow$), if and only if ($\longleftrightarrow$)

Truth Tables

• The truth values of compound propositions can be described by truth tables

Conditional Proposition

• $p$ เป็น Condition part, hypothesis, antecedent, premise
• $q$ เป็น Conclusion, consequence

• $p\rightarrow q$ can also be read as:
  • “If $p$, then $q$”
  • “$q$ when $p$”
  • “A sufficient condition for $q$ is $p$”
  • “A necessary condition for $p$ is $q$”

Biconditional Proposition

• Input เหมือนกันเป็น TRUE ต่างกันเป็น FALSE ตรงข้ามกับ XOR Gate นะ!!! ระวังจำสับสน
  • The exclusive or (XOR) is also equivalent to the negation of a logical biconditional
• $p \leftrightarrow q$ can also be read as:
  • “$p$ is a necessary and sufficient condition for $q$”
  • and sometimes written as “$p$ iff $q$”

Logical Equivalence

• ประพจน์ $p$ สมมูลกับ $q$ เมื่อ $p$ และ $q$ มีค่าความจริงเหมือนกันทุกกรณี (ดูใน Truth Table) เขียนแทนด้วย “p $≡$ q”
  • Logically equivalent = Same in every possible combination

• ปัญหาอยู่ตรงที่ว่า จะรู้ว่า Logcally equivalent กันเนี่ย ถ้ามีทั้งหมด 10 symbols ไม่ต้องเขียน Truth Table $2^{10}=1,024$ แถวเลยหรอ?!!!
  • เพราะว่า The size of the truth table grows “exponentially” as the number of symbols increases.

Basic Logical Equivalences (สมมูลที่สำคัญ ๆ)

Biconditional Law

Implication Law

Contrapositive Law

De Morgan’s Law

Associative Laws (The Grouping is Not Important)

• เครื่องหมาย ใน เหมือนกับ นอก!

Distributive Law

• Check Link อีกทีว่าถูกต้องมั้ย
• เครื่องหมาย ใน ต่างกับ นอก!

Quantifications (ตัวบ่งปริมาณ)

Universal Quantification ($\forall$)

• $\forall x$, $P(x)$ is true, if $P(x)$ is true for every $x$ in $D$ → to show, examine all objects
• $\forall x$, $P(x)$ is false, if $P(x)$ is false for at least one $x$ in $D$ → to show, give one counterexample

Existential Quantification ($\exists$)

• $\exists x$, $P(x)$ is true, if $P(x)$ is true for at least one $x$ in $D$ → to show, give one example
• $\exists x$, $P(x)$ is false, if $P(x)$ is false for every $x$ in $D$ → to show, examine all objects

Generalized De Morgan’s Law

$\neg(\forall x, P(x))$ and $\exists x, \neg P(x)$ have the same truth values.

$\neg(\exists x, P(x))$ and $\forall x, \neg P(x)$ have the same truth values.

• ง่าย ๆ ก็คือกระจาย $\neg$ เข้าไปใน quantified statement นั่นเอง

Nested Quantifiers

• ง่าย ๆ ก็คือการมีประพจน์ มากกว่า 1 ตัว = 2 ตัว นั่นแหละ