Discrete mathematics Software school Fudan University April 23, 2013
. . Discrete Mathematics Yi Li Software School Fudan University April 23, 2013 Yi Li (Fudan University) Discrete Mathematics April 23, 2013 1 / 25
Review o Soundness o Completeness
Review Soundness Completeness Yi Li (Fudan University) Discrete Mathematics April 23, 2013 2 / 25
utline o Deduction from premises o Compactness Applications
Outline Deduction from premises Compactness Applications Yi Li (Fudan University) Discrete Mathematics April 23, 2013 3 / 25
C onsequence Definition Let 2 be a(possibly infinite)set of propositions. We say that o is a consequence of∑( and write as∑ha), for any valuation v (D()= T for allT∈∑)→()=T
Consequence . Definition . . Let Σ be a (possibly infinite) set of propositions. We say that σ is a consequence of Σ (and write as Σ |= σ) if, for any valuation V, (V(τ ) = T for all τ ∈ Σ) ⇒ V(σ) = T. Yi Li (Fudan University) Discrete Mathematics April 23, 2013 4 / 25
C onsequence am dle oLet∑={A,=AVB}, we have∑hB oLet∑={A,A→B}, we have∑hB o Let 2={-A}, we have∑h(A→B)
Consequence . Example . . 1. Let Σ = {A, ¬A ∨ B}, we have Σ |= B. 2. Let Σ = {A, A → B}, we have Σ |= B. 3. Let Σ = {¬A}, we have Σ |= (A → B). Yi Li (Fudan University) Discrete Mathematics April 23, 2013 5 / 25