SKEDSOFT

Automata | Comp. Sc. Engg.

Connectives: 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.

where p is the statement, T and F represent ‘True’ and ‘False’ respectively.

Illustration

(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”.

 

It is very important to be careful while negating a statement involving the words “All” or “Some”. The use of these “quantifiers” is the subject of “Predicate calculus”. ~p is also written as Ø p.

 

(b)    Conjunction (AND):The conjunction of p and q is the statement pÙ q, which is read as “p and q”, whose truth value is defined by the following truth table.

If p and q columns are listed, all four possible combinations of truth values for p and q, and in the pÙ q column we find the associated truth value for pÙ q. Let us see how the statement “This chapter is definitely not boring even though logic is a boring subject” is expressed in logical form. The first clause is the negation of p, so is ~p. The second clause is simply stating the (false) claim that logic is a boring subject, and thus amounts to q. The phrase “even though” is a colorful way of saying that both clauses are true, and so the whole statement is just (~ p) Ù q.

(c)    Disjunction (OR): The disjunction of p and q is the statement pÚ q, which is read as “p or q”, whose truth value is defined by the following truth table.

Note that the only way for the whole statement to be false is for both p and q to be false. Hence we say that pÚ q means “p and q are not both false”.