You've successfully subscribed to ムえのBLOG
Welcome back! You've successfully signed in.

# Discrete Mathematics 1.1 Mathematical Logic

## 研究领域

•universal system of reasoning: reasoning based on symbols+calculations

Areas: (1) set theory, (2) proof theory, (3) recursion theory, (4) model theory, and their foundation (5) propositional logic and predicate logic

（1）集合论，（2）证明论，（3）递归论，（4）模型论及其基础（5）命题逻辑和谓词逻辑


Our focus: propositional logic and predicate logic

## proposition

A proposition (命题) is a declarative sentence that is either true or false.

•Lower-case letters represent propositions: p,q,r,…

truth value (真值): The truth value of p is true (T) if p is a true proposition. The truth value of p is false (F) if p is a false proposition.

Simple Proposition(简单命题) : cannot be broken into 2 or more propositions

•√2 " is irrational".

Compound Proposition(复合命题): not simple

•2 is rational and √2 is irrational.

Propositional Constant(命题常项): a concrete proposition (truth value fixed)

•Every even integer n>2 is the sum of two primes.

Propositional Variable(命题变项): a variable that represents any proposition

•Lowercase letters denote proposition variables: p,q,r,s,…

•Truth value is not determined until it is assigned a concrete proposition

Propositional Logic(命题逻辑): the area of logic that deals with propositions

## 运算

### Negation (¬)

DEFINITION: Let p be any proposition.

• The negation (否定) of p is the statement “It is not the case that p”

• notation: ¬p; read as “not p”

truth table (真值表):

p ¬p
T F
F T

### Conjunction (∧)

DEFINITION: Let p,q be any propositions.

•The conjunction (合取) of p and q is the statement “p and q”

•Notation: p∧q; read as “p and q”

•Truth table:

p q p∧q
T T T
T F F
F T F
F F F

### Disjunction (∨)

DEFINITION: Let p,q be any propositions.

•The disjunction (析取) of p and q is the statement “p or q”

•Notation: p∨q; read as “p or q”

•Truth table:

p q p∨q
T T T
T F T
F T T
F F F

### Implication (→)

DEFINITION: Let p,q be any propositions.

•The conditional statement p→q (蕴涵) is the proposition “if p, then q.”

•p: hypothesis*;* q*:* conclusion*;* read as “p implies q”, or “if p, then q”

•Truth table:

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

### Bi-Implication (↔)

DEFINITION: Let p,q be any propositions.

•The biconditional statement p↔q (等值) is the proposition “p if and only if q.”

•read as “p if and only if q”

•Truth table:

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

### Well-Formed Formulas (合式公式)

DEFINITION: recursive definition of well-formed formulas (WFFs)

1. propositional constants (T, F) and propositional variables are WFFs
2. If A is a WFF, then ¬A is a WFF
3. If A,B are WFFs, then (A∧B), (A∨B), (A→B), (A↔B) are WFFs
4. WFFs are results of finitely many applications of ①, ② , and ③