Logical Laws and Operators in Sets and Logic

An experiment.. SETS AND LOGIC . CHAPTER 2

LOGICAL LAWS DeMorgan s Laws ? ? ?? ?????????? ?? ? ? ?? ?????????? ?? ? ? ? ? Commutative, Associative, and Idempotent Distributive ? ? ? ?? ?????????? ?? (? ?) (? ?) ? Q ? ?? ?????????? ?? ? ? ? ? Absorption: ? ? ? ?? ?????????? ?? ? ? ? ? ?? ?????????? ?? ?

TAUTOLOGIES AND CONTRADICTIONS Statements or Formulas which are always true are Tautologies Formulas that are always false are Contradictions ? ?????????? ? ????????? ; ? ????????????? ; ? (?????????????)

VARIABLES AND SETS We will consider statements dependent upon a variable or a number of variables Ex s P(x): x is a prime number D(x,y): x is divisible by y In this case we don t have truth tables we have truth sets

CONDITIONAL STATEMENTS P implies Q: ? ? If its raining and I don t have my umbrella, then I ll get wet. If Mary did her homework, then the teacher won t collect it, and if she didn t, the he ll ask her to do it on the board

EQUIVALENCES ? ? is equivalent to ? ? ? ? is equivalent to (? ?)

THE CONVERSE AND CONTRAPOSITIVE Consider ? ? and ? ? ? ? is called the converse of ? ? ? ? is the contrapositive of ? ? The converse of ? ? is not equivalent The contrapositive is .. ? ? ?? ?????????? ?? ? ?

CHAPTER 2: QUANTIFIERS Three ideas For all or for every, we use the notation: There is one, or there exists: The universe

SEVEN OPERATORS Connectives Quantifiers ??? This is really all we need to write any mathematical statement!

NEW NOTATION ? ? > 2 ?2> 4 Is there and implied universe?

EXAMPLES ? ?2> 0 ? ?2 2? + 3 = 0 , Universe in what universe? ? ? ? ? ? , where M(x) is ( x is a man) and B(x) is ( x has brown hair ) ? ? ? ? ? ??(?,?) where L(x,y) is a like function from x to y.

WRITE AS LOGICAL STATEMENTS Someone didn t do the homework Everything in that store is either overpriced or poorly made Nobody s perfect Susan likes everyone who dislikes Joe ? ? ? ? ?\C

WRITE AS STATEMENTS Everybody in the dorm has a roommate he doesn t like Nobody likes a sore loser Anyone who has a friend who has the measles will have to be quarantined If anyone in the dorm has a friend who has the measles, then everyone in the dorm will have to be quarantined If ? ?, then A and C\B are disjoint

MULTIPLE QUANTIFIERS ? ? ? < ? ? ? ? < ? ? ? ? < ? ? ? ? < ? ? ? ? < ? ? ?(? < ?)

EQUIVALENCE INVOLVING QUANTIFIERS Quantifier Negation Laws ?? ? ?? ?????????? ?? ? ? ? ?? ? ?? ?????????? ?? ? ?(?)

EXAMPLES Negate the statements, and then reexpress the results as equivalent positive statements ? ? Everyone has a relative he doesn t like

ANALYZE THE LOGICAL FORMS All married couples have fights Everyone likes at least two people John likes exactly one person

ANAYZE THE LOGICAL FORMS Statements about the natural numbers x is a perfect square x is a multiple of y x is prime x is the smallest number that is a multiple of both y and z

ANALYZE THE STATEMENTS Statements about real numbers The identity element for addition is 0. Every real number has and additive inverse Negative numbers don t have square roots Every positive number has exactly two square roots

2.3. MORE ON SETS Instead of just ? ?(?) we can consider more general forms ?(?) ? [0,1] ??+? ??+???[0,1]

MORE EXAMPLES 3? ?? ?? ????? ? ?2?? and ?3?? are disjoint

THE POWER SET The Power Set ? = ? ? ? Find the Power Set for ? = ?,?,?

ANALYZE THE LOGICAL FORMS ?? ? ? ? ?? (?) ? ?? ? ? ?? (?) (?)

INTERSECTIONS AND UNIONS = 1,2,3,4 , 2,3,4,5}, 3,4,5,6 Find

DEFINITIONS: UNIONS AND INTERSECTIONS = ? ?? ??? = ? ?(?? ??? = ? ?? ??? = ? ?(?? ???

ANALYZE THE LOGICAL FORMS ?? G ?? ?? (?) ??

ANOTHER EXAMPLE ? = 1,2,3 ??= ?,? + 1,? + 2,? + 3 Find ?????and ?????