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
