1.2.
Well – formed Formulas
A well-formed formula (wff) is defined recursively as follows:
(i) A proposition variable alone is a wff
(ii) If is a wff then is a wff
(iii) If and are wffs, then and are wffs.
(iv) A string of symbols containing the proposition variables, connectives and
parentheses is a wff if and only if it can be obtained by finitely many
applications of the above rules (i), (ii) and (iii).
By the above definitions the following are wffs:
We use parentheses to avoid ambiguity. For the sake of convenience we shall
omit the outer parentheses. Thus we write the above wffs respectively as
Since we deal with only wffs, we refer wffs as formulas.
The following are not formulas
Note:
(i) In the construction of formulas, the parentheses will be used in the
same sense in which they are used in elementary algebra or some times
in a programming language.
(ii) The following is the hierarchy of operations and parentheses:
1. Connectives within parentheses; among parentheses innermost first
2. Negation
3. and
4.
5.
Truth tables of well-formed Formulas
If there are distinct variables in a formula, then we need to consider possible
combinations of truth values in order to obtain the truth table of the formula.
Construction of truth tables
There are two methods of construction of truth tables.
The first columns of the table are for the proposition variables and
create enough number of rows ( rows if there are variables) in the table
for all possible combinations of and for the variables.
Method – 1
Devote a column for each elementary stage of the construction of the formula.
The truth value at each step is determined from the previous stages by the
definition of connectives. Finally the truth value of the formula is given in the last
column.
Method – 2
Write the formula on the top row to the right of its variables. A column is drawn
for each variable as well as for the connectives that appear in the formula. The
truth values are entered step by step. The step numbers at the bottom of the
table show the sequence followed in arriving the final step.
Example 1:
Construct the truth table for the formula
Solution:
Method- 1
Let be . Then the given formula is .
Truth table for
Method- 2
Step is the final step and it gives the truth values of the given formula
Tautology
A wff is said to be a tautology (a universally valid formula or logical truth) if its
truth value is for all possible assignments of truth values to the proposition
variables of the formula.
Note:
(i) If is any proposition then the formula is a tautology
(ii) The conjunction of two tautologies is also a tautology
The proof of the above result (ii) is given below:
Let and be formulas which are tautologies. For all possible assignments of
truth values to the variables of and , the truth values of both and will be
and hence the truth value of will be . Thus is a tautology.
Contradiction
A wff is said to be a contradiction (or absurdity) if its truth value is for all
possible assignments of truth values of the proposition variables of the formula.
Note:
(i) If is any proposition then the formula is a contradiction
(ii) The negation of a contradiction is a tautology
Contingency
A wff is said to be satisfiable or contingency if it is neither a tautology nor a
contradiction.
Ex: If and are propositions then and are satisfiable (contingency).
Example 2:
Show that the formula
is a tautology.
Solution:
Method-1
Let be the formula and be the formula .
Then the given formula is .
Truth table for
It is a tautology since its truth value is for all possible assignments of truth
values to the proposition variables of the formula.
Method- 2
Step is the final step and it has truth values of ’s only. Hence the given
formula is a tautology.
Example 3:
Show that the formula is a contradiction.
Solution:
We show this by constructing truth table.
Step is the final step and it has truth values of only. Hence the given formula
is a contradiction.
Example 4:
Is the formula a tautology, contradiction or contingency?
Solution:
Step is the final step and it has truth values of and . Hence the given formula
is neither a tautology nor a contradiction. Therefore, it is a contingency.
Substitution instance
Let and be formulas. We say that is a substitution instance of if can be
obtained from by substituting formulas for the variables of , with the condition
that the same formula is substituted for the same variable each time it occurs.
Example: Let . Then
is a substitution instance of , since is
substituted for in .Note that is not a substitution instance
of .
Note:
1. In constructing substitution instances of a formula, substitutions are made for
the atomic formula and never for the molecular formula:
Ex: is not a substitution instance of , since it is which must be
substituted and not .
2. Any substitution instance of a tautology is a tautology
It is known that is a tautology. If we substitute any formula for , the
resulting formula will be a tautology.
Example 5:
Determine the formulas which are substitution instances of other formulas in the
following list and give the substitutions.
(a)
(b)
(c)
(d)
(e)
Solution:
(i) Substitute for and for in , we get .Therefore , is
the substitution instance of
(ii) Substitute for in , we get . Therefore, is
the substitution instance of
(iii) Substitute and for and respectively in we get .
Therefore, is the substitution instance of .
P1:
Construct the truth table for .
Solution:
Truth table for
P2:
Construct the truth table for .
Solution:
Truth table for
P3:
Show that the formula is a tautology.
Solution:
We show this by constructing its truth table
Method- 1
Truth table for
It is a tautology since its truth value is for all possible assignments of truth
values to the proposition variables of the formula.
Method- 2
Step is the final step and it has truth values of only. Hence the given formula
is a tautology.
is a tautology
P4:
If and are proposition variables then show that is a
tautology.
Solution:
We show this by constructing truth table.
Method-1
Truth Table for
:
It is a tautology since its truth value is for all possible assignments of truth
values to the proposition variables of the formula.
Method-2
Step is the final step and it has truth values of only. Hence the given formula
is a tautology.
P5:
Show that the formula is a contradiction.
Solution:
Step is the final step and it has truth values only. Hence the given formula is a
Contradiction
P6:
Show that the formula for is a contradiction.
Solution:
Step is the final step and it has truth values only. Hence the given formula is a
Contradiction
P7:
Show that the formula is a contingency.
Solution:
Step is the final step and it has truth values and . Thus it is neither a
Tautology nor a contradiction. Therefore it is a contingency.
P8:
Show that the formula is a contingency.
Solution:
Step is the final step and it has truth values and . Thus it is neither a
Tautology nor a contradiction. Therefore it is a contingency.
1.2. Well-Formed Formulas
Exercises:
Which of the following formulas is a tautology, contradiction, contingency?
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
k.
