You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

Discrete Mathematics Lecture 2

. 1 min read

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

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


本站总访问量