Discrete mathematics Software school Fudan University April 2, 2013
. . Discrete Mathematics Yi Li Software School Fudan University April 2, 2013 Yi Li (Fudan University) Discrete Mathematics April 2, 2013 1 / 20
Review o Formation tree o Parsing algorithm
Review Formation tree Parsing algorithm Yi Li (Fudan University) Discrete Mathematics April 2, 2013 2 / 20
utline o Truth assignment Truth valuation Tautology o Consequence
Outline Truth assignment Truth valuation Tautology Consequence Yi Li (Fudan University) Discrete Mathematics April 2, 2013 3 / 20
Truth Assignment How we discuss the truth of propositional letters? Definition(Assig gnment A truth assignment A is a function that assigns to each propositional letter A a unique truth value 4(A)∈{T,F}
Truth Assignment How we discuss the truth of propositional letters? . Definition (Assignment) . . A truth assignment A is a function that assigns to each propositional letter A a unique truth value A(A) ∈ {T, F}. Yi Li (Fudan University) Discrete Mathematics April 2, 2013 4 / 20
Truth∨ aluation How we discuss the truth of propositions? Exampl e Truth assignment of a and B and valuation of (av B B(a③)
Truth Valuation How we discuss the truth of propositions? . Example . . Truth assignment of α and β and valuation of (α ∨ β). α β (α ∨ β) T T T T F T F T T F F F Yi Li (Fudan University) Discrete Mathematics April 2, 2013 5 / 20
Assignment and valuation Definition(Valuation A truth valuation v is a function that assigns to each proposition a a unique truth value v(a) so that its value on a compund proposition is determined in accordance with the appropriate truth tables Specially, v(a) determines one possible truth assignment if a is a propositional letter
Assignment and Valuation . Definition (Valuation) . . A truth valuation V is a function that assigns to each proposition α a unique truth value V(α) so that its value on a compund proposition is determined in accordance with the appropriate truth tables. Specially, V(α) determines one possible truth assignment if α is a propositional letter. Yi Li (Fudan University) Discrete Mathematics April 2, 2013 6 / 20
Assignment and valuation merrem Given a truth assignment a there is a unique truth valuation V such that V(a)=A(a) for every propositional letter a roo The proof can be divided into two step O Construct a v from a by induction on the depth of the associated formation tree o Prove the uniqueness of v with the same A by nduction bottom-up
Assignment and Valuation . Theorem . . Given a truth assignment A there is a unique truth valuation V such that V(α) = A(α) for every propositonal letter α. . Proof. . . The proof can be divided into two step. 1. Construct a V from A by induction on the depth of the associated formation tree. 2. Prove the uniqueness of V with the same A by induction bottom-up. Yi Li (Fudan University) Discrete Mathematics April 2, 2013 7 / 20
Assignment and valuation If vi and v2 are two valuations that agree on the support of a, the finite set of propostional letters used in the construction of the proposition of the proposition a, then n(a)=2(a)
Assignment and Valuation . Corollary . . If V1 and V2 are two valuations that agree on the support of α, the finite set of propostional letters used in the construction of the proposition of the proposition α, then V1(α) = V2(α). Yi Li (Fudan University) Discrete Mathematics April 2, 2013 8 / 20
Tautology Definition A proposition o of propostional logic is said to be valid if for any valuation v, v(o)=T. Such a proposition is also called a tautology
Tautology . Definition . . A proposition σ of propostional logic is said to be valid if for any valuation V, V(σ) = T. Such a proposition is also called a tautology. Yi Li (Fudan University) Discrete Mathematics April 2, 2013 9 / 20
Tautology am e a V na is a tautology Solution: a-a aV -a
Tautology . Example . .α ∨ ¬α is a tautology. . Solution: . . α ¬α α ∨ ¬α T F T F T T Yi Li (Fudan University) Discrete Mathematics April 2, 2013 10 / 20