學海無涯，思境無維；數乃六藝，理之始也。
或有一得足矣 愚千慮

$$$$

Logic

3.1 Propositions and Logical Operators

Proposition(主張): A proposition is a sentence to which one and only one of the terms true or false can be meaningfully applied.

Example:

“Four is even,”, “4 ∈ {1, 3, 5}” and “43 > 21” are propositions

3.1.2 Logical Operations

Suppose

$p,q$ are propositions.

Logical Conjunction

$pandq⟺p\wedge q$

p	q	$p\wedge q$
0	0	0
0	1	0
1	0	0
1	1	1

Logical Disjunction

$porq⟺p\vee q$

p	q	$p\vee q$
0	0	0
0	1	1
1	0	1
1	1	1

Logical Negation

$notp⟺\mathrm{\neg }p$

p	$\mathrm{\neg }p$
0	1
1	0

Conditional Statement

If

$p$, then

$q$, denoted "

$p\to q$".

p	q	$p\to q$
0	0	1
0	1	1
1	0	0 (this is ruled out)
1	1	1

When we write "

$p\to q$", it means "if p is true, then q must be true.", so the case that p = 1 and q = 0 is ruled out.

Converse

The converse of

$p\to q$ is

$q\to q$.
But this would be a different thing.

Contrapositive

The contrapositive of the proposition

$p\to q$ is "

$\mathrm{\neg }q\to \mathrm{\neg }p$".

Biconditional Proposition

if and only if = iff

$p⟺q$ : if

$p$ then

$q$, also if

$q$ then

$p$,

$p$ is equivalent to

$q$.

p	q	$p⟺q$
0	0	1
0	1	0
1	0	0
1	1	1

Propositions Generated by a Set

Let S be any set of propositions. A proposition generated by S is any valid combination of propositions in S with conjunction, disjunction, and negation. Or, to be more precise,
(a) If p ∈ S, then p is a proposition generated by S, and
(b) If x and y are propositions generated by S, then so are (x), ¬x, x ∨ y , and x∧y.

Equivalence and Implication

$$\{\begin{array}{l}\mathrm{\neg }(p\wedge q)⟺\mathrm{\neg }p\vee \mathrm{\neg }q\end{array}$$

Tautology: An expression involving logical variables that is true in all cases is a tautology. The number 1 is used to symbolize a tautology.
ex:

$$\{\begin{array}{l}p\vee \mathrm{\neg }p\\ p\wedge q\to p\\ q\to p\vee q\end{array}$$
Contradiction: An expression involving logical variables that is false for all cases is called a contradiction. The number 0 is used to symbolize a contradiction.
ex:

$$p\wedge \mathrm{\neg }p$$

Equivalence: Let S be a set of propositions and let r and s be propositions generated by S. r and s are equivalent if and only if r ↔ s is a tautology. The equivalence of r and s is denoted r

$⟺$ s.
ex:

$$\{\begin{array}{l}(p\wedge q)\vee (\mathrm{\neg }p\wedge q)⟺q\\ p\to q⟺\mathrm{\neg }q\to \mathrm{\neg }p\\ p\vee q⟺q\vee p\\ p\vee \mathrm{\neg }p⟺1\\ p\wedge \mathrm{\neg }p⟺0\end{array}$$

Implication

Implication: Let S be a set of propositions and let r and s be propositions generated by S. We say that r implies s if r → s is a tautology. We write r ⇒ s to indicate this implication.
ex: Disjuctive Addition

$$p⟹p\vee q$$

A Universal Operation

The Sheffer Stroke:

$p\mid q$

p	q	$p\mid q$	$p\wedge q$	$p\vee q$
0	0	1	0	0
0	1	1	0	1
1	0	1	0	1
1	1	0	1	1

and : 有 0 則 0 (皆 1 方 1)
or : 有 1 則 1 (皆 0 方 0)
sheffer : 有 0 則 1 (皆 1 方 0)

$p\wedge q⟺\mathrm{\neg }(p\mid q)$

$p\vee q⟺\mathrm{\neg }p\vee \mathrm{\neg }q$

$\mathrm{\neg }p⟺p\mid p$

$p\to q⟺\mathrm{\neg }p\vee q$

The Laws of Logic

duality principle

Basic Logical Laws - Equivalences

$\vee$	$\wedge$	Name of Law
$p\vee q⟺q\vee p$	$p\wedge q⟺q\wedge p$	Communitive Law
$(p\vee q)\vee r⟺p\vee (q\vee r)$	$(p\wedge q)\wedge r⟺p\wedge (q\wedge r)$	Associative Law
$p\vee (q\wedge r)⟺(p\vee q)\wedge (p\vee r)$	$p\wedge (q\vee r)⟺(p\wedge q)\vee (p\wedge r)$	Distributive Law
$p\vee 0⟺p$	$p\wedge 1⟺p$	Identity Law
$p\vee \mathrm{\neg }p⟺1$	$p\wedge \mathrm{\neg }p⟺0$	Negation Law
$p\vee p⟺p$	$p\wedge p⟺p$	Idempotent Law
$p\vee 1⟺1$	$p\wedge 0⟺0$	Null Law
$p\vee (p\wedge q)⟺p$	$p\wedge (p\vee q)⟺p$	Absorption Law
$\mathrm{\neg }(p\vee q)⟺\mathrm{\neg }p\wedge \mathrm{\neg }q$	$\mathrm{\neg }(p\wedge q)⟺\mathrm{\neg }p\vee \mathrm{\neg }q$	DeMorgan's Law
$\mathrm{\neg }(\mathrm{\neg }p)⟺p$		Involution Law

Basic Logical Laws - Common Implications and Equivalences

Detachment	$(p\to q)\wedge p⟹q$
Contrapositive	$p\to q⟺\mathrm{\neg }q\to \mathrm{\neg }p$
Indirect Reasoning	$(p\to q)\wedge \mathrm{\neg }q⟹\mathrm{\neg }p$ ( $\because p\to q⟺\mathrm{\neg }q\to \mathrm{\neg }p$)
Disjunctive Addition	$p⟹p\vee q$
Conjunctive Simplification	$p\wedge q⟹p$ ; $p\wedge q⟹q$
Disjunctive Simplification	$(p\vee q)\wedge \mathrm{\neg }p⟹q$ ; $(p\vee q)\wedge \mathrm{\neg }q⟹p$
Chain Rule	$(p\to q)\wedge (q\to r)⟹p\to r$
Conditional Equivalence	$p\to q⟺\mathrm{\neg }p\vee q$ (當 p 成立時，q 必需成立，否則 $\mathrm{\neg }p\vee q$ 就不成立。)
Biconditional Equivalence	$p\leftrightarrow q⟺(p\to q)\wedge (q\to p)⟺(p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$

Mathematical Systems and Proof

• A set or universe, U.
• Definitions
• Axioms
• Theorems: A true proposition derived from the axioms of a mathematical system is called a theorem.
  p1 ∧ p2 ∧ · · · ∧ pn ⇒ Conclusion

Proof: A proof of a theorem is a finite sequence of logically valid steps that demonstrate that the premises of a theorem imply its conclusion.

tags: math logic