## From Natural Language to WFFs

**The** **Method** **of Translation:**

- Introduce symbols p,q,r… to represent simple propositions
- 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**)

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

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

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

## Truth Table

**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.

### Contradiction(矛盾式/永假式)

a WFF whose truth value is **F** for all truth assignment

- p∧¬p is a contradiction

### Contingency( 可能式)

neither tautology nor contradiction

- 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