Solu tion
(a) (i) (
)
¬ ∧
⇒
P R
Q
(ii) R Q
⇒
(iii) ¬ P
(iv) P
Q
∧ ¬
(b) (i) Q
R
P
⇔ ∧ ¬
(
).
I will go to town, if and only if I have time and it is not
snowing.
(ii) R Q
∧ .
I have time and I will go to town.
(iii) (
) (
)
Q R
R Q
⇒ ∧
⇒ .
I will go to town if I have time and if I have time, I will go to
town.
(iv) ¬ ∨
(
)
R Q .
It is not that I have time or I will go to town.
Ì Exam ple 8.1.14: How many rows are needed for the truth table of the
formula (
)
((
)
)
p
q
r s
t
∧ ¬ ⇔ ¬ ∧ ⇒ ?
Solu tion
Given p, q, r, s, t as propositions.
∴ Number of rows needed in Truth Table = 2
5 = 32.
Ì Exam ple 8.1.15: If p p
p n
1
2
, , KK
are primitive propositions and
∅( , ,
)
p p
p n
1
2 KK
is a formula which contains at least one occurrence of
each p
i n
i (
),
1 ≤ ≤
how many rows are needed to construct the truth table
for ∅?
Solu tion
Given p p
p n
1
2
, , KK
as propositions. Therefore number of rows needed in
Truth Table = 2
n (for n elements).
8.1.3 Log i cal Iden tities
If two propositional forms are logically equivalent one can be substituted for
the other in any proposition in which they occur. Table below shows a list of
important equivalences, which are called “identities.” The symbols P, Q , and
R represent arbitrary propositional forms. The symbol “1” is used to represent
either a “tautology” or a true proposition. Similarly, “0” represents a false
proposition or a contradiction.
258
Theory of Automata, Formal Languages and Computation