Valuation

Valuation

There are precisely two truth values: truth and falsity. The truth value truth is denoted by the symbol T and the truth value falsity is denoted by the symbol F. In other words, we regard symbols T and F as standing for true and false, respectively.

Now, suppose σ be a map whose domain is set of all propositions (or atomic well-formed formulas) and whose range is the set {T, F}; then σ is said to be an assignment. The idea is that assignment σ assigns a truth-value to each proposition (or atomic well-formed formula). The purpose of such an assignment is to show that each atomic statement has a unique truth-value. Recall, this is exactly the definition of 'function'. And we say: A valuation is a function v from the set of propositions (to be very precise, proposition letters such as p, q, r, ...) to the set {T, F} of truth-values.

This idea can easily be extend to compound statements (or composite well-formed formulas). That is, well-formed formulas also receive unique truth-values, we use an assignment, σ, to provide each composite well-formed formula with a truth-value. As a matter of fact, we extend assignment σ to a map v of the set of all well-formed formulas into {T, F} which is defined as follows:

1.	v(A)	=	σ (A)	for each atomic well-formed formula A.
.
2.	v(~B)	=	T	If v(B) = F
2.	v(~B)	=	F	If v(B) = T
.
3.	v(A∨B)	=	F	If v(A) = v(B) = F
3.	v(A∨B)	=	T	Otherwise.

The map v is called a valuation; for each well-formed formula A, v(A) is said to be the truth-value of A under assignment σ.

Note that we can define valuation in terms of function as follows. A valuation is a function v whose domain is the set of well-formed formulas and whose range is the set {T, F} and followed by above rules. It is easy to see that this definition is exactly the same as above since the concept of mapping is embedded in the "function."

Following are some facts about valuation:

Fact 1: For any valuation v and any well-formed formulas A and B, we have

	v(A∧B)	=	T	If v(A) = v(B) = T
	v(A∧B)	=	F	Otherwise.

We demonstrate this fact by pointing out A ∧ B = ~(~A ∨ ~B).

Fact 2: For any valuation v and any well-formed formulas A and B, we have

	v(A→B)	=	T	If v(A) = T or v(B) = T
	v(A→B)	=	F	If v(A) = T or v(B) = F

We demonstrate this fact by point out A→B = ~A ∨ B.

Note that the other way of writing the fact 2 is as follows:

v(A→B) = F if, and only if, v(A) = T and v(B) = F.

Fact 3: For any valuation v and any well-formed formulas A and B, we have

	v(A↔B)	=	T	If v(A) = v(B)
	v(A↔B)	=	F	If v(A) ≠ v(B)

We demonstrate this fact by point out A ↔ B = (A → B) ∧ (B → A)

It is easy to see that a well-formed formula A is a tautology if for every valuation v, we have

v(A) = T

Note that this is the same as regarding A as a statement and applying the definition of valuation.

Formally, we say

A well-formed formula A is tautology if, and only if, v(A) = T for every valuation v.

Now we are ready to prove that a well-formed formula is a theorem if, and only if, it is a tautology. And this is our next topic.