DHARM112 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEConsider the formation tree shown in Fig. 5.13. Determine the truth value of the for-
mula for the truth values of propositional variables (P, Q, R, S) are (T, F, F, T) respectively.
Putting truth values to corresponding variables shown at leaf and obtains the truth
value of its immediate subformula in that path and moves one level up in the tree. Continue,
this process until we reach to root node with truth value. Here we find the truth value of the
formula (at root) is T (Fig. 5.14).Fig. 5.145.4.5 Truth Table.........................................................................................................
A wff may consist of several propositional variables. In the dual-logic paradigm the propositional
variables have only possible truth value T or F. To determine the truth values of wff for all
possible combinations of the truth values of the propositional variables-a table is prepared-
called truth table.
Assume a formula contains two propositional variables then there are 2^2 possible com-
binations of truth values are to be considered in the truth table. In general, if a formula con-
tains n distinct propositional variables then, possible combination of truth values are 2n or
total number of possible different interpretation are 2n.
The process of arbitrarily assignments of truth value (T/F) to the propositional vari-
ables is called atomic valuation. Thus, we get the truth values of the formula called valua-
tion. It can’t assign the truth values arbitrary.
There is another term frequently used in propositional logic that is boolean valua-
tion. Boolean valuation is a valuation under some restrictions.
Lets ‘v’ be a boolean valuation, then
· If the formula X gets value T under ‘v’ then ‘v’ must assign F to ~ X. Conversely, if
formula X gets value F under ‘v’ then ~ X must get value T under ‘v’.
· The formula (X ∧ Y) can get value T under ‘v’ if and only if both X and Y get value T
under ‘v’.