Chapter 1: Propositions and Predicates J;;I, 15
DefInition 1.12 A formula ex is in principal conjunctive normal form if ex
is a product of maxterms. For obtaining the principal conjunctive normal form
of ex, we can construct the principal disjunctive normal form of -, ex and apply
negation.
EXAMPLE 1.16
Find the principal conjunctive normal form of ex = P v (Q :::::} R).
Solution
-, ex= -,(P v (Q:::::} R))
== -, (P v (-, Q v R))
by using 1 12
== -, P 1\ (-, (-, Q v R)) by using DeMorgan' slaw
== -, P 1\ (Q 1\ -, R)
by using DeMorgan's law and 1 7
-, P /\ Q 1\ -, R is the principal disjunctive normal form of -, ex. Hence,
the principal conjunctive normal form of ex is
-, (-, P 1\ Q 1\ -, R) = P v -, Q v R
The logical identities given in Table 1.11 and the normal forms of well-formed
formulas bear a close resemblance to identities in Boolean algebras and normal
forms of Boolean functions. Actually, the propositions under v, 1\ and -, form
a Boolean algebra if the equivalent propositions are identified. T and F act as
bounds (i.e. 0 and 1 of a Boolean algebra). Also, the statement formulas form
a Boolean algebra under v, 1\ and -, if the equivalent formulas are identified.
The normal forms of \vell-formed formulas correspond to normal forms
of Boolean functions and we can 'minimize' a formula in a similar manner.
1.3 RULES OF INFERENCE FOR PROPOSITIONAL
CALCULUS (STATEMENT CALCULUS)
In logical reasoning. a certain number of propositions are assumed to be true.
and based on that assumption some other propositions are derived (deduced or
inferred). In this section we give some important rules of logical reasoning or
rules of inference. The propositions that are assumed to be true are called
h)potheses or premises. The proposition derived by using the rules of inference
is called a conclusion. The process of deriving conclusions based on the
assumption of premises is called a valid argument. So in a valid argument we /
are concerned with the process of arriving at the conclusion rather ~
obtaining the conclusion.
The rules of inference are simply tautologies in the form of implication
(i.e. P :::::} Q). For example. P :::::} (P v Q) is such a tautology, and it is a rule
P
of inference. We write this in the form
Q . Here P denotes a premise.
. ".Pv
The proposition below the line. i.e. P v Q is the conclusion.
http://engineeringbooks.net
DefInition 1.12 A formula ex is in principal conjunctive normal form if ex
is a product of maxterms. For obtaining the principal conjunctive normal form
of ex, we can construct the principal disjunctive normal form of -, ex and apply
negation.
EXAMPLE 1.16
Find the principal conjunctive normal form of ex = P v (Q :::::} R).
Solution
-, ex= -,(P v (Q:::::} R))
== -, (P v (-, Q v R))
by using 1 12
== -, P 1\ (-, (-, Q v R)) by using DeMorgan' slaw
== -, P 1\ (Q 1\ -, R)
by using DeMorgan's law and 1 7
-, P /\ Q 1\ -, R is the principal disjunctive normal form of -, ex. Hence,
the principal conjunctive normal form of ex is
-, (-, P 1\ Q 1\ -, R) = P v -, Q v R
The logical identities given in Table 1.11 and the normal forms of well-formed
formulas bear a close resemblance to identities in Boolean algebras and normal
forms of Boolean functions. Actually, the propositions under v, 1\ and -, form
a Boolean algebra if the equivalent propositions are identified. T and F act as
bounds (i.e. 0 and 1 of a Boolean algebra). Also, the statement formulas form
a Boolean algebra under v, 1\ and -, if the equivalent formulas are identified.
The normal forms of \vell-formed formulas correspond to normal forms
of Boolean functions and we can 'minimize' a formula in a similar manner.
1.3 RULES OF INFERENCE FOR PROPOSITIONAL
CALCULUS (STATEMENT CALCULUS)
In logical reasoning. a certain number of propositions are assumed to be true.
and based on that assumption some other propositions are derived (deduced or
inferred). In this section we give some important rules of logical reasoning or
rules of inference. The propositions that are assumed to be true are called
h)potheses or premises. The proposition derived by using the rules of inference
is called a conclusion. The process of deriving conclusions based on the
assumption of premises is called a valid argument. So in a valid argument we /
are concerned with the process of arriving at the conclusion rather ~
obtaining the conclusion.
The rules of inference are simply tautologies in the form of implication
(i.e. P :::::} Q). For example. P :::::} (P v Q) is such a tautology, and it is a rule
P
of inference. We write this in the form
Q . Here P denotes a premise.
. ".Pv
The proposition below the line. i.e. P v Q is the conclusion.
http://engineeringbooks.net