Normal Forms And Truth Table

NORMAL FORM AND TRUTH TABLES :
Well Formed Formulas : (wff) A compound statement obtained from statement letters by using one or more connectives is called a statement pattern or statement form. thus, if P, Q, R, ……. are the statements (which can be treated as variables) then any statement involving these statements and the logical connectives ∧,∨,¬,⇔,→ is a statement form or a well formed formula or statement pattern.

Definition : A propositional variable is a symbol representing any proposition. Note that a propositional variable is not a proposition but can be replaced by a proposition. Any statement involving a propositional variable and logical connectives is a well formed formula.

Note : A wff is not a proposition but we substitute the proposition in place of propositional variable, we get a proposition.

(a) Truth table for a Well Formed Formula :
If we replace the propositional variables in a formula α by propositions, we get a proposition involving connectives. If α involves n propositional constants, we get 2n possible combination of truth variables of proposition replacing the variables.

Example : Obtain truth value for α = ( P→Q) ∧ ( Q→P) .
Solution : The truth table for the given well formed formula

(b) Tautology : A tautology or universally true formula is a well formed formula, whose truth value is T for all possible assignments of truth values to the propositional variables.
Example 11 : Consider P ∨ ¬ P , the truth table is as follows.

P ∨ ¬ P always takes value T for all possible truth value of P, it is a tautology.

(c) Contradiction : A contradiction or (absurdity) is a well formed formula whose truth value is false (F) for all possible assignments of truth values to the
propositional variables. Thus, in short a compound statement that is always false is a contradiction.
Example 12 : Consider the truth table for P ∨ ¬ P .

P ∨ ¬  P always takes value F for all possible truth values of P, it is a contradiction.
(d) Contingency : A well formed formula which is neither a tautology nor a contradiction is called a contingency. Thus, contingency is a statement pattern which is either true or false depending on the truth values of its component statement.
Example 13 : Show that ¬ p ∨ q and ¬ p∧ ¬ q are logically equivalent.
Solution : The truth tables for these compound proposition is as follows.

We cab observe that the truth values of ¬ p ∨ q and ¬ p∧ ¬ q agree for all possible combinations of the truth values of p and q.

It follows that (¬ p ∨ q) ⇔ (¬ p∧ ¬ q) is a tautology, therefore the given compound propositions are logically equivalent.