Basic Mathematical Objects   Back to Table of Contents
The following are the contents of this introductory chapter.
Logic
Proposition and Logical Connectives
"Proposition"
can be defined as a declarative statement having a
specific truth-value, true or false.
Example:
The following statements are propositions
as they have precise truth values. Their truth values are false and
true, respectively.
The following are the logical connectives used commonly:
a. Conjunction
The logical conjunction is understood in the same
way as commonly used ôandö. The compound proposition
truth-value is true iff all the constituent propositions hold
true. It is represented as " ^ ".
Truth table for two individual propositions p and
q with conjunction is given below
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b. Disjunction
This is logical "or" read as either true value of
the individual propositions.
Truth table is given below
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c. Negation
This is the logical "negation" and it is expressed by
as p for "not p".
Truth table is given below
|
|
|
|
|
|
d. Conditional
This is used to define as "a proposition holds true
if another
proposition is true" i.e. p q
is read as "if p, then q"
Truth table is given below
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
e. Biconditional
A proposition (p
q) ^ (q p) can be abbreviated
using biconditional conjunction
as p
q and is read as "if p then q, and if q then p".
f. Tautology
A compound proposition, which is true in every case.
E.g.: p V
p
g. Contradiction
This is the opposite of tautology, which is false
in every case.
E.g.: p ^ p
Logical implication and equivalence
If the value of p -> q is true in every case,
then p is said to logically imply q.
It is represented as p =>
q. If p and q have the same truth-value in every case
then they are
said to be logically equivalent and it is represented as p
<=>
q.
Following are some of the useful identities and implications from propositional logic:
Identities
For explanations, examples and proofs of these identities go to
Implications
For explanations, examples and proofs of these implications go to
Predicate and Predicate Logic
The propositional logic is not powerful enough to represent all types of assertions
that are used
in computer science and mathematics, or to express certain types of
relationship between
propositions such as equivalence
( for more detail
For more complex
reasoning we need
more powerful logic capable of expressing complicated
propositions
and reasoning. The
predicate logic is one of the extensions of propositional logic
and it is fundamental
to most other
types of logic.
Central to the predicate logic are the concepts
of predicate and quantifier.
A predicate is a template
involving a verb
that describes a property of objects, or
a relationship
among objects represented by the variables.
For example, the sentences "The car Tom is driving is blue", "The sky is blue",
and
"The cover
of this book is blue" come from the template "is blue"
by placing an
appropriate noun/noun phrase
in front of it.
The phrase "is blue" is
a predicate and it describes the property of being blue.
Predicates are often
given a name. For example any of "is_blue", "Blue" or "B" can be used
to
represent the predicate "is blue" among others. If we adopt B as the name
for the predicate
"is_blue", sentences that assert an object is blue can be
represented as "B(x)", where x represents
an arbitrary object. B(x) reads as "x is
blue".
A predicate with variables,
called atomic formula,
can be made
a proposition by applying one of
the following two operations to each of its
variables:
For example, x > 1 becomes 3 > 1 if 3 is assigned to x,
and it becomes a true statement,
hence a proposition.
In general, a quantification is performed on formulas of predicate logic
(called
wff
),
such as
x > 1 or P(x), by using quantifiers on variables
.
There are two types
of quantifiers:
universal quantifier
and existential
quantifier.
The universal quantifier turns, for example, the statemen
t x > 1
to "for every object x
in the universe, x > 1", which is expressed as "
x x > 1".
This new statement is true or false
in the universe of discourse. Hence it is a proposition
once the universe is specified.
Similarly the existential quantifier turns, for example,
the statement x > 1
to "for some
object x in the universe, x > 1", which is expressed as "
x x > 1." Again, it is true or false
in the universe of discourse, and hence
it is a proposition once the universe is specified.
Universe of Discourse
The universe of discourse, also called universe
, is the set of objects
of interest.
The propositions in the predicate logic are statements on objects of a universe.
The universe
is thus
the domain of the (individual) variables. It can be the set of real numbers,
the set of integers, the set of all cars on a parking lot, the set of all students
in a classroom etc.
The universe is often left implicit in practice. But it should be obvious from the
context.
Predicate logic is more powerful than propositional logic. It allows one
to reason about properties
and relationships of individual objects.
In predicate logic, one can use some additional
inference
rules, some of which are given below,
as well as
those for propositional logic such as
the
Important Inference Rules of Predicate Logic:
First there is the following rule concerning the negation of quantified statement which is very useful:
x
P(x)
x
P(x)
Next there is the following set of rules on quantifiers and connvectives: