21
Fri, Sep

Truth Tables for:

  1. ~ p /\ q
  2. ~ p /\ (q \/ ~ r)
  3. (p \/ q) /\ ~ (p /\ q)

Truth table for the statement form ~ p /\ q

P q ~P ~P / \q
T T F F
T F F F
F T T T
F F T F

Truth table for ~ p /\ (q \/ ~ r)

Truth Tables

Truth table for (p \/ q) ~ (p /\ q)

Truth Tables

Double Negative Property ~(~p) ≡p

Truth Tables

Example

“It is not true that I am not happy”

Solution:

Let p“I am happy”
then ~ p“I am not happy”
and ~(~ p)“It is not true that I am not happy”
Since ~ (~p) ≡p

Hence the given statement is equivalent to:
“I am happy” ~ (p /\ q) and ~p /\ ~q are not logically equivalent.

Truth Table

Different truth values in row 2 and row 3

DE MORGAN’S LAWS:

  1. The negation of an and statement is logically equivalent to the or
    statement in which each component is negated.
    Symbolically ~(p /\ q) ≡~p \/ ~q.
  2. The negation of an or statement is logically equivalent to the and
    statement in which each component is negated.
    Symbolically: ~(p \/ q) ≡~p /\ ~q.
    ~(p \/ q) ≡~p /\ ~q

    Truth Table

    Application:

    Give negations for each of the following statements:

    • The fan is slow or it is very hot.
    • Akram is unfit and Saleem is injured.

    Solution.

    • The fan is not slow and it is not very hot.
    • Akram is not unfit or Saleem is not injured.

    Inequalities & Demorgan's Laws:

    Use DeMorgan’s Laws to write the negation of
    -1 < x < 4

    for some particular real no. x
    -1 < x < 4 means x > –1 and x < 4

    By DeMorgan’s Law, the negation is:

    x > –1 or x < 4Which is equivalent to: x < –1 or x > 4

    Exercise:

    1. (p /\ q) /\ r = p /\(q /\ r)
    2. Are the statements (p /\ q)\/ r and p /\~(q \/ r) logically equivalent?

    Tautology:

    A tautology is a statement form that is always true regardless of the truth values of the statement variables.

    A tautology is represented by the symbol “T”.

    Example:

    The statement form p \/ ~ p is tautology

    P ~P P \/ ~ P
    T F T
    F T T

    p \/ ~p ≡t

    Contradiction:

    A contradiction is a statement form that is always false regardless of the truth values of the statement variables.

    A contradiction is represented by the symbol “c”.
    So if we have to prove that a given statement form is CONTRADICTION we will make the truth table for the statement form and if in the column of the given statement form all the entries are F ,then we say that statement form is contradiction.

    Example:

    The statement form p /\ ~ p is a contradiction.

    P ~P P /\ ~P
    T F F
    F T F

    Since in the last column in the truth table we have F in all the entries so is a contradiction p /\ ~p ≡c.

    Remarks:

    • Most statements are neither tautologies nor contradictions.
    • The negation of a tautology is a contradiction and vice versa.
    • In common usage we sometimes say that two statements are contradictory.

    By this we mean that their conjunction is a contradiction: they cannot both be true.

    Logical Equivalence Involving Tautology.

    Show that p /\ t ≡p

    P T P /\ T
    T T T
    F T F

     

    Since in the above table the entries in the first and last columns are identical so we have the corresponding statement forms are Logically Equivalent that is
    p /\ t ≡p

    Logical Equivalence Involving Contradiction

    Show that p /\ c ≡c
    P C P /\ C
    T F F
    F F F

    Same truth values in the indicated columns so p /\ c ≡c

    Exercise:

    Use truth table to show that (p /\ q) \/(~p \/(p /\ ~q)) is a tautology.

    Solution:

    Since we have to show that the given statement form is Tautology so the column of the above proposition in the truth table will have all entries as T.

    As clear from the table below

    Truth Table

    Hence(p /\ q) \/ (~p \/(p /\ ~q)) ≡ t

    Exercise:

    Use truth table to show that (p /\ ~q) /\(~p \/ q) is a contradiction.

    Solution:

    Since we have to show that the given statement form is Contradiction so its column in the truth table will have all entries as F.

    As clear from the table below

    Truth Table

    Usage Of “OR” In English

    In English language the word or is sometimes used in an inclusive sense (p or q or both).

    Example:

    I shall buy a pen or a book.

    In the above statement, if you buy a pen or a book in both cases the statement is true and if you buy (both) pen and book then statement is again true. Thus we say in the above statement we use or in inclusive sense.
    The word or is sometimes used in an exclusive sense (p or q but not both). As in the below statement.

    Example:

    Tomorrow at 9, I’ll be in Lahore or Islamabad.

    Now in above statement we are using or in exclusive sense because both the statements are true then we have F for the statement.
    While defining a disjunction the word or is used in its inclusive sense. Thus the symbol \/ means the “inclusive or”.

    Exclusive OR:

    When or is used in its exclusive sense, the statement “p or q” means “p or q but not both” or “p or q and not p and q” which translates into symbols as:

    (p \/ q) /\ ~ (p /\ q)

    Which is abbreviated as:
    p Å q or p XOR q

    Truth Table For Exclusive OR:

    Truth Table

    Note:
    Basically p Å q ≡ (p /\ ~q)\/~(p /\ q)
    ≡ [p /\ ~q) \/~p] /\[(p /\ ~q) \/ q]
    ≡ (p \/ q) /\ ~ (p /\q)
    ≡ (p \/ q) /\(~p \/~q)

Course Objective:

  1. Express statements with the precision of formal logic.
  2. Analyze arguments to test their validity.
  3. Apply the basic properties and operations related to sets.
  4. Apply to sets the basic properties and operations related to relations and function.
  5. Define terms recursively.
  6. Prove a formula using mathematical induction.
  7. Prove statements using direct and indirect methods.
  8. Compute probability of simple and conditional events.
  9. Identify and use the formulas of combinatorics in different problems.
  10. Illustrate the basic definitions of graph theory and properties of graphs.
  11. Relate each major topic in Discrete Mathematics to an application area in computing.

Recommended Books:

  1. Discrete Mathematics with Applications (second edition) by Susanna S. Epp.
  2. Discrete Mathematics and Its Applications (fourth edition) by Kenneth H. Rosen.
  3. Discrete Mathematics by Ross and Wright.

Main Topics:

  1. Logic.
  2. Sets & Operations on sets.
  3. Relations & Their Properties.
  4. Functions.
  5. Sequences & Series.
  6. Recurrence Relations.
  7. Mathematical Induction.
  8. Loop Invariants.
  9. Combinatorics.
  10. Probability.
  11. Graphs and Trees.

Discrete

Set of Integers:

• • • • • •

3 -2 -1 0 1 2

Set of Real Numbers:

• • • • • •

-3 -2 -1 0 1 2

What is Discrete Mathematics?:

Discrete Mathematics concerns processes that consist of a sequence of individual steps.

Logic:

Logic is the study of the principles and methods that distinguishes between a valid and an invalid argument.

Simple Statement:

A statement is a declarative sentence that is either true or false but not both.

A statement is also referred to as a proposition.

Example: 2+2 = 4, It is Sunday today.

If a proposition is true, we say that it has a truth value of "true”.

If a proposition is false, its truth value is "false".

The truth values “true” and “false” are, respectively, denoted by the letters T and F.

Examples:

  1. Grass is green.-- -- -- -- -- Not Propositions
  2. 4 + 2 = 6 -- -- -- -- -- -- -- - Close the door.
  3. 4 + 2 = 7 -- -- -- -- -- -- -- - x is greater than 2.
  4. There are four fingers
    in a hand. are propositions. -- -- -- -- -- He is very rich are not propositions.

Rule:

If the sentence is preceded by other sentences that make the pronoun or variable reference clear, then the sentence is a statement.

Example:

  • x = 1
  • x > 2
  • x > 2 is a statement with truth - value FALSE.

Understanding Statements:

  1. x + 2 is positive. -- -- -- -- -- -- -- Not a statement.
  2. May I come in? -- -- -- -- -- -- -- - Not a statement.
  3. Logic is interesting.-- -- -- -- -- -- A statement.
  4. It is hot today.-- -- -- -- -- -- -- -- -- A statement.
  5. -1 > 0 -- -- -- -- -- -- -- -- -- -- -- -- -- A statement.
  6. x + y = 12 -- -- -- -- -- -- -- -- -- -- -- Not a statement.

Compound Statement:

Simple statements could be used to build a compound statement.

Examples:-- -- -- -- --- -- -- - Logical Connectives.

  1. “3 + 2 = 5” and “Lahore is a city in Pakistan”.
  2. “The grass is green” or “ It is hot today”.
  3. “Discrete Mathematics is not difficult to me”.
    AND, OR, NOT are called LOGICAL CONNECTIVES.

Symbolic Representation:

Statements are symbolically represented by letters such as p, q, r,...

Examples:

p = “Islamabad is the capital of Pakistan”.

q = “17 is divisible by 3”.

Symbolic Representation

Examples:

p = “Islamabad is the capital of Pakistan”.

q = “17 is divisible by 3”.

p  q = “Islamabad is the capital of Pakistan and 17 is divisible by 3”.

p  q = “Islamabad is the capital of Pakistan or 17 is divisible by 3”.

~p = “It is not the case that Islamabad is the capital of Pakistan” or simply. “Islamabad is not the capital of Pakistan”.

Translating From English To Symbols:

Let p = “It is hot”, and q = “It is sunny”.

Sentence -- -- -- -- -- -- -- -- -- -- -- --Symbolic Form.

  1. It is not hot.-- -- -- -- -- -- -- -- -- -- -- - ~ p
  2. It is hot and sunny. -- -- -- -- -- -- -- - p /\ q.
  3. It is hot or sunny. -- -- -- -- -- - -- -- - p \/ q.
  4. It is not hot but sunny. -- -- -- -- -- ~ p /\ q
  5. It is neither hot nor sunny. -- -- -- ~ p /\ ~ q.
  6. Examples:

    Let h = “Zia is healthy”
    w = “Zia is wealthy”
    s = “Zia is wise”.

    Translate the compound statements to symbolic form:

    1. Zia is healthy and wealthy but not wise. -- -- -- -- -- -- -- -- -- (h /\ w) /\ (~s).
    2. Zia is not wealthy but he is healthy & wise. -- -- -- -- -- -- -- ~w /\ (h /\ s).
    3. Zia is neither healthy, wealthy nor wise. -- -- -- -- -- -- -- -- -- ~h /\ ~w /\ ~s.

    Translating From Symbols To English:

    Let m = “Ali is good in Mathematics”.

    c = “Ali is a Computer Science student”.

    Translate the following statement forms into plain English:

    1. ~ c -- -- -- -- -- - Ali is not a Computer Science student.
    2. c \/ m -- -- -- Ali is a Computer Science student or good in Maths.
    3. m /\ ~c-- -- -- - Ali is good in Maths but not a Computer Science student.

    A convenient method for analyzing a compound statement is to make a truth table for it.

    A truth table specifies the truth value of a compound proposition for all possible truth values of its constituent propositions.

    Negation (~):

    If p is a statement variable, then negation of p, “not p”, is denoted as “~p”.

    It has opposite truth value from p i.e., if p is true, ~p is false; if p is false, ~p is true.

    Truth Table For ~ p

    Discrete

    Conjunction(/\):

    If p and q are statements, then the conjunction of p and q is “p and q”, denoted as “p /\ q”.

    It is true when, and only when, both p and q are true. If either p or q is false, or if both are false, p /\ q is false.

    Truth Table For p /\ q

    Discrete

    Disjunction ( \/ ) or INCLUSIVE OR

    If p & q are statements, then the disjunction of p and q is “p or q”, denoted as “p \/ q”. It is true when at least one of p or q is true and is false only when both p and q are false.

    Truth Table For p \/ q

    Note it that in the table F is only in that row where both p and q have F and all other values are T. Thus for finding out the truth values for the disjunction of two statements we will only first search out where the both statements are false and write down the F in the corresponding row in the column of p Ú q and in all other rows we will write T in the column of p Ú q.

    Remark:

    Note that for Conjunction of two statements we find the T in both the statements, but in disjunction we find F in both the statements. In other words we will fill T first in the column of conjunction and F in the column of disjunction.

    Summary

    1. What is a statement?
    2. How a compound statement is formed.
    3. Logical connectives (negation, conjunction, disjunction).
    4. How to construct a truth table for a statement form.