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

# Discrete Mathematics Lecture 2

## From Natural Language to WFFs

The Method of Translation:

1. Introduce symbols p,q,r… to represent simple propositions
2. Connect the symbols with logical connectives to obtain WFFs

### Ex

•(√2)^√2 is rational or irrational. (ambiguity in natural language)

•p: “(√2)^√2 is rational”; q: “(√2)^√2 is irrational”

Explanation 1: (√2)^√2 cannot be neither rational nor irrational.

•Translation 1: p∨q

•We agree that p∨q is the correct translation of

“(√2)^√2 is rational or irrational .”

Explanation 2: (√2)^√2 cannot be both rational and irrational.

•Translation 2: (p∧¬q)∨(q∧¬p)

•We agree that (p∧¬q)∨(q∧¬p) is the translation of

​ “(√2)^√2 is rational or irrational, but not both.”

## Precedence

### 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 ③

## Precedence**(**优先级): ¬, ∧, ∨, →, ↔

1. formulas inside () are computed firstly
2. different connectives: ¬, ∧, ∨, →, ↔
3. same connectives: from left to the right

## DEFINITION:

Let F be a WFF of p_1,…,p_n, n propositional variables

• A truth assignment (真值指派) for F is a map α:{p_1,…,p_n }→**{T,F}**.
• There are 2^n different truth assignments.
$p_1$ $p_2$ $p_n$ F
T T T
T T F
F F F

## Types of WFFs

### Tautology(重言式/永真式)

a WFF whose truth value is T for all truth assignment

• p∨¬p is a tautology

#### Rule of Substitution代入规则

Let B be a formula obtained from a tautology A by substituting a propositional variable in A with an arbitrary formula. Then B must be a tautology.

##### Ex:

$p∨¬p$is a tautology: $(q∧r)∨¬(q∧r)$is a tautology as well.

a WFF whose truth value is F for all truth assignment

### Contingency( 可能式)

• p→¬p is a contingency

### Satisfiable(可满足的)

• a WFF is satisfiable if it is true for at least one truth assignment
• the Tautology & the Contingency are the Satisfiable