2.2, 2.3, and 2.4 Notes

Logically Equivalent Statements

    Logically Equivalent - Two expressions are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions.


Converse and Contrapositive

    Converse - The converse of P→Q is Q→P

    Contrapositive - The contrapositive of P→Q is -Q→-P


De Morgan’s Laws

  • The statement, -(P ^ Q) = -P v -Q

  • The statement, -(P v Q) = -P ^ -Q


Logical Equivalencies Related to Conditional Statements

    Theorem 2.6

  • P →Q = -P v Q

  • -(P → Q) = P ^ -Q

  • P→ Q = -Q → -P


The Negation of a Conditional Statement

    The negation of a conditional statement is not another conditional statement


Important Logical Equivalences

    Biconditional Statement - (P ←→ Q) = (P → Q) ^ (Q → P)

    Double Negation - -(-P) = P

    Distributive Laws - P v (Q ^ R) = (P v Q) ^ (P v R)

                                  P ^ (Q v R) = (P ^ Q) v (P ^ R)

    Conditionals with Disjunctions - P → (Q v R) = (P ^ -Q) → R

                                                       (P v Q) → R = (P → R) ^ (Q → R)


Open Sentences and Sets

Sets and Set Notation

    Set - A well-defined collection of objects that can be thought of as a single entity itself; {…}

    Roster Method - Listing the elements of a set inside braces


Variables

    Variable - A symbol representing an unspecified object that can be chosen from a given set U. The set U is called the UNIVERSAL SET FOR THE VARIABLE. It is the set of specified objects from which objects may be chosen to substitute the variable. A CONSTANT is a specific member of the universal set.

    Number Systems

  • R - Real numbers

  • Q - Rational numbers

  • Z - Integers

  • N - Natural numbers


Some Set Notation

    The set A is a SUBSET of a set B provided that each element of A is an element of B. In this case, we write A c B and also say that A is CONTAINED in B. When A is not a subset of B, we write A c/ B.


Variables and Open Sentences

    Open Sentence - A sentence P(x1, …, xn) involving variables x1, …, xn with the property that when specific values from the universal set are assigned to x1, …, xn, then the resulting sentence is either true or false. That is, the resulting sentence is a statement. An open sentence is also called a PREDICATE or a PROPOSITIONAL FUNCTION.


Working with Open Sentences

    Truth Set of an Open Sentence with One Variable - The collection of objects in the universal set that can be substituted for the variable to make the predicate a true statement. Also called TRUTH SET.

    Set Builder Notation - The set is defined by stating a rule that all elements of the set must satisfy.


Quantifiers and Negations

An Introduction to Quantifiers

    Universal Quantifier - “For every”; A

    Existential Quantifier - “There exists… such that”; E


Theorem 2.16

    For any sentence P(x),

        -(Ax e U) [P(x)] = (Ex e U) [-P(x)], and

        -(Ex e U) [P(x)] = (Ax e U) [-P(x)]


Important Set Theory Notation

Notation                    Description

    y e A                            y is an element in the set A

    {x e U | P(x)}               set builder notation