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.

     "Connective": Two or more propositions can be combined together to make compound propositions with
     the help of logical connectives.
     Example:
     Above two propositions can be used to make a compound proposition using any of the logical connectives.      Their truth vales are false and true respectively. For the first compound proposition to be true both the
     propositions have to be true as the connective is AND and as OR is the connective for the second one
     if either of the propositions is true the truth value of the compound proposition is true.

    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
p
q
p ^ q
T
T
T
T
F
F
F
T
F
F
F
F

    b. Disjunction
    This is logical "or" read as either true value of the individual propositions.
    Truth table is given below
p
q
p V q
T
T
T
T
F
T
F
T
T
F
F
F

    c. Negation
    This is the logical "negation" and it is expressed by     as  p   for "not p".
    Truth table is given below
p
p
T
F
F
T

    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
p
q
p  q
T
T
T
T
F
F
F
T
T
F
F
T

    p -> q is also expressed in a number of different (but equivalent) ways in English.
    For example, "p only if q" , "if not q then not p" , "p is sufficient for
    q" , "q is necessary for p", "q is a necessity/consequence of p" and "q whenever p"
    are all differnt ways of saying "if p then q".

    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

  1. (P Q) ( P Q) ----- DeMorgan's Law
  2. (P Q) ( P Q) ----- DeMorgan's Law
  3. (P Q) ( P Q) ----- implication
  4. [(P Q) R] [P (Q R)] ----- exportation
  5. (P Q) (Q P) ----- contrapositive

    For explanations, examples and proofs of these identities go to Identities

    Implications

  1. [(P Q) Q] P ----- modus tollens
  2. [(P Q) (R S)] [(P R) (Q S)]
  3. [(P Q) (Q R)] (P R)

    For explanations, examples and proofs of these implications go to Implications

    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 click here for example for example ).
    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:

  1. assign a value to the variable
  2. quantify the variable using a quantifier (see below).

    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 equivalences, implications and inference rules.


    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:

  1. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]
  2. [ x P(x) x Q(x) ] x [ P(x) Q(x) ]
  3. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]
  4. x [ P(x) Q(x) ] [ x P(x) x Q(x) ]

    For more discussions and examples on these rules and others, see Reasoning(with predicate logic)
    and Quantifiers and Connectives in Discrete Structures course. Also for proof and proof
    techniques see Mathematical Reasoning.


  Click here for Review Excercises

Click here for Online Test


 
 
 
Back to Study Schedule

Back to Table of Contents