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 5谓词逻辑

Discrete Mathematics Lecture 5谓词逻辑

. 3 min read

Predicate Logic(谓词逻辑)

Predicate谓词

describe the property of the subject term (in a sentence)

  • A predicate is a function from a domain of individuals to {𝐓,𝐅}
  • 𝒏-ary  predicate𝒏元谓词: a predicate on 𝑛 individuals𝐼: “is an integer” // unary𝐺: “is greater than” //binary
  • Predicate constant谓词常项: a concrete predicate // 𝐼,𝐺
  • Predicate variable谓词变项: a symbol that represents any predicate

Individual个体词

the object you are considering (in a sentence)

“√(1+2√(1+3√(1+⋯)) )  is an integer”
“𝑒^𝜋 is greater than 𝜋^𝑒”

  • Individual Constant个体常项: √(1+2√(1+3√(1+⋯)) ) ,  𝑒^𝜋, 𝜋^𝑒
  • Individual Variable个体变项: 𝑥,𝑦,𝑧
  • Domain个体域: the set of all individuals in consideration

Propositional function命题函数

**$𝑃(𝑥_1,…,𝑥_𝑛)$, where 𝑃 is an 𝑛-ary predicate **

𝑃(𝑥,𝑦):“𝑥 is greater than 𝑦”
𝑃(𝑥,𝑦) gives a proposition when we assign values to 𝑥,𝑦
𝑃(𝑒^𝜋,𝜋^𝑒) is a proposition (a true proposition)
𝑃(𝑥,𝑦) is not a proposition

EXAMPLE:

​ 𝑝:“Alice’s father is a doctor”; 𝑞:“Bob’s father is a doctor”

  • Individuals: Alice’s father, Bob’s father; Predicate 𝐷: “is a doctor”
  • 𝑝=𝐷(Alice′ s father), 𝑞=𝐷(Bob′ s father)

Function of Individuals:  a map on the domain of individuals

  • 𝑓(𝑥)=𝑥’s father
  • 𝑝=𝐷(𝑓(Alice));𝑞=𝐷(𝑓(Bob))

Universal Quantifier全称量词

DEFINITION:

Let $P(x)$ be a propositional function. The universal quantification全称量化 of $P(x)$ is “$P(x)$ for all x in the domain”.

notation: $∀x P(x)$; read as “for all $x$ $P(x)$” or “for every $x$ $P(x)$”

“∀” is called the universal quantifier全称量词

“∀x P(x)” is true iff P(x) is true for every x in the domain

“∀x P(x)” is false iff there is an x_0 in the domain such that $P(x_0)$ is false

Counterexample反例: an x_0 such that P(x_0) is false

Existential Quantifier

DEFINITION:

Let P(x) be a propositional function. The existential

​    quantification存在量化 of P(x) is “there is an x in the domain

​    such that P(x)”

  • notation: ∃x P(x); read as “for some x P(x)” or “there is an x s.t. P(x)”
  • “∃” is called the existential quantifier****存在量词
  • “∃x P(x)” is true iff there is an x in the domain such that P(x) is true
  • “∃x P(x)” is false iff P(x) is false for every x in the domain

EXAMPLE:

$P(x):“x^2-x+1=0”$

•“$∃x P(x)$”  is false when D=R and is true when D=C

REMARK: If the domain is empty, then "∃x P(x)" is false for any P.

REMARK: if not stated, the individual can be anything.

Binding Variables and Scope 绑定范围和变量

DEFINITION:

An individual variable x is bound约束的 if a quantifier (∀, ∃) is used on x; otherwise, x is said to be free自由的.

  • ∃x(x+y=1)
  • x is bound and y is free
  • scope辖域 of a quantifier: the part of a formula to which a quantifier is used
  • the scope of ∃x in ∃x(x+y=1) is (x+y=1)

Predicate Logic谓词逻辑:

the area of logic that deals with predicates and quantifiers (a.k.a. predicate calculus)处理谓词和量词的逻辑区域(又称谓词演算)

  • predicate logic is an extension of propositional logic

Well-Formed Formulas

Elements that may appear in Well-Formed Formulas合式公式

  • Propositional constants: T,F, p,q,r,…(命题常数)
  • Propositional variables: p,q,r,…  (命题变量)
  • Logical Connectives: ¬,∧,∨,→, ↔(逻辑连接词)
  • Parenthesis: (, )(插入语)
  • Individual constants: a,b,c,…(个体常项)
  • Individual variables: x,y,z,…(个体变项)
  • Predicate constants: P,Q,R,…(命题常项)
  • Predicate variables: P,Q,R,…(命题变项)
  • Quantifiers: ∀, ∃(量词)
  • Functions of individuals: f,g,…(个体函数)

DEFINIITON: well-formed formulas合式公式/formulas

  1. propositional constants, propositional variables, and propositional functions without connectives are WFFs(无连接词的命题常数,命题变量和命题函数是WFF)
  2. If A is a WFF, then ¬A is also a WFF(如果A是WFF,则¬A也是WFF)
  3. If A,B are WFFs and there is no individual variable x which is bound in one of A,B but free in the other, then (A∧B), (A∨B), (A→B), (A↔B) are WFFs.(如果A,B是WFF,并且没有单个变量x绑定到A,B中的一个而在另一个中自由,则(A∧B),(A∨B),(A→B),(A↔ B)是WFF。)
  4. If A is a WFF with a free individual variable x, then ∀x A, ∃x A are WFFs.(如果A是具有自由个体变量x的WFF,则∀xA,∃xA是WFF。)
  5. WFFs can be constructed with.(WFF由1到4构造而成)

Precedence

∀, ∃ have higher precedence than ¬, ∧, ∨, → , ↔

From Natural Language to WFFs

The Method of Translation

  1. Introduce symbols to represent propositional constants, propositional variables, individual constants, individual variables, predicate constants, predicate variables, functions of individuals
  2. Construct WFFs with 1-4 such that WFFs reflect the real meaning of the natural language


本站总访问量