Discrete mathematics Yi li Software sc Fudan unive April 24, 2012
Discrete Mathematics Yi Li Software School Fudan University April 24, 2012 Yi Li (Fudan University) Discrete Mathematics April 24, 2012 1 / 25
Review Soundness o Completeness
Review Soundness Completeness Yi Li (Fudan University) Discrete Mathematics April 24, 2012 2 / 25
utline o Deduction from premises o Compactness Applications
Outline Deduction from premises Compactness Applications Yi Li (Fudan University) Discrete Mathematics April 24, 2012 3 / 25
C onsequence Definition Let 2 be a(possibly infinite)set of propositions. We say that o is a consequence of 2(and write as 2h o) if, 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 24, 2012 4 / 25
C onsequence am dle oLet∑={A,=AVB}, we have∑hB oLet={A,A→B}, we have∑hB oLet∑={-A}, we have∑(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 24, 2012 5 / 25