哑元无关性 定理16设在P的公式a中出现的命题符号都在p1;P2 ,P;n中,若P的两个指派1,02满足:a1(m1)= 02(p)(k=1,2,…,m),则a1=a2
16 P α pi1, pi2, · · · , pin , P σ1, σ2 : σ1(pik) = σ2(pik) (k = 1, 2, · · · , n), ασ1 = ασ2. 15
公式的分类 定义20 若对P的任一指派σ,Q=1,则称a为一个重 言式(或永真式) 若对P的任一指派σ,a=0,则称a为一个矛 盾式(或永假式) 若存在P的指派σ,使Q=1,则称a为一个可满 足式
20 • P ✖ σ, ασ = 1, α ✖ ( ). • P ✖ σ, ασ = 0, α ✖ ( ). • P σ, ασ = 1, α ✖ . 16
永真式的例子 定理17P的公理都是永真式 证:下证(A3)是永真式。 (a)|(6(a→-)7(→a)(A3) 0011 0101 1010 1011 1111
17 P : (A3) ✒ σ(α) σ(β) (¬ α→¬ β)σ (β→α)σ (A3)σ 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 17
(M)的保真性 定理18P的分离规则保持永真性, 即:若a和a→β都是永真式,则也是永真式 若不然,则存在P的指派σ使=0 由于a为重言式,故a=1,从而(a→B)=0, 与a→B为重言式矛盾
(M) 18 P , : α α → β , β . : , P σ βσ = 0. ✛α , ασ = 1, (α→β)σ = 0, α→β . 18
替换定理 定理19设α是P中公式,q1,q2,…,q是P中命 题变元符号,β1,B2,…,月n是P中另外m个公式, 将Q中每个q(若有)换为(1≤≤m)所得的公式 为.若a为重言式,则6也为重言式 说明 92 gn
19 α P , q1, q2, · · · , qn P , β1, β2, · · · , βn P n , α qi( ) βi (1 ≤ i ≤ n) β. α , β .. : α : · · · q1 · · · q2 · · · · · · qn · · · β : · · · β1 · · · β2 · · · · · · βn · · · 19