We use the letters p, q, r, s, ...... for propositions. Thus for example, we
might decide that P should stand for the proposition “The earth is round”. Then
we shall write
p: “the earth is round”
to express this. We read this
p is the state ment “the earth is round”.
8.1.1 Con nec tives
In order to make use of some keywords like and, ‘or’, ‘not’, etc. which are
called “sentential connectives”, it is required to have some ground rules before
making use of them. Let us now discuss about the different forms of
connectives.
(a) Negation (NOT): The negation of p is the statement ~p, which is read as
“not P”. Its truth value is defined by the following truth table.
p
~p
T
F
F
T
where p is the statement, T and F represent ‘True’ and ‘False’ respectively.
Illus tra tion
(i) Given p = + =
"
",
3 3 6 we have
~
"
".
p = + ≠
3 3 6
Note that ~p is false in this case, since p is true.
(ii) If p = “2 = 0”, then we have
~ :"
".
p 1 0
≠
~ p is true in this case, since p is false.
(iii) If p = “I loved either Nirmala or Padmaja”.
then we have
~ p : “I loved nei ther Nirmala nor Padmaja”.
Here p is a hypothetical statement (but which was true!)
(iv) If p = “All the doctors in this town are crooks”, then we have
~ p = “Not all the doc tors in this town are crooks”
or
~ p = “At least one of the doc tors in this town is not a crook”.
246
Theory of Automata, Formal Languages and Computation