SLOG #3: Review of Test 1 Material

REVIEW OF TEST 1 MATERIAL

·         Universal claims (") - claim about all objects

®     to verify: consider every element in the domain and show that they satisfy the claim

®     to falsify: provide a single counter-example

·         Existential claims ($) - claim about some objects

®     to verify: show at least one example

®     to falsify: show there are no examples

·         SETS:

®     P Í Q "P is a subset of Q", "Every P is a Q"

-        To prove: show every element of P is an element of Q

-        To disprove: Find at least one element of P that is not an element of Q

®     P Ë Q "Some P is a Q"

-        To prove: find one P that is a Q

-        To disprove: Show that every P is not in Q

·         IMPLICATIONS:

®     IF antecedent, THEN consequent

®     can also be shown by antecedent Þ consequent

®     to disprove, show an example where P is True and Q is False.

®     note: "If...then..." tells you nothing about causality. For example, "If it rained yesterday, then the sun rose today" is true, but rain did not cause the sun to rise.

®     for antecedent, look for words such as: if, when, enough, sufficient

®     for consequent, look for words such as: then, requires, must, need, necessary, only if, when

·         CONTRAPOSITIVE:

®     the contrapositive of (P Þ Q) is (¬Q Þ ¬P)

®     "all non-Q are non-P"

·         CONVERSE:

®     the converse of (P Þ Q) is (Q Þ P)

·         NEGATION:

®     negation inverts the truth value

®     When negating a statement:

-        Existential quantifiers turn into universal quantifiers, and universal quantifiers turn into existential quantifiers

-        use manipulation rules, such as DeMorgan laws and distributive laws (for full list see Course notes pg.29)

®     Example: ¬($ xÎD, P(x) Ù Q(x)) Û (" xÎD, ¬P(x) Ú ¬ Q(x))

·         VACUOUS TRUTH:

®     Whenever the antecedent is false, and the consequent is either true or false, the implication as a whole is TRUE

®     the set where the antecedent is true is empty(vacuous), and hence a subset of every set

·         TAUTOLOGY, SATISFIABILITY, UNSATISFIABILITY

®     Tautology: you can't dream up a domain, or a meaning for predicates P and Q that provides a counter-example, since the truth tables are identical

®     Satisfiable: true for some choice of domain, predicates P and Q, and values of domain elements, ex: (P Þ Q) Û (Q Þ P). Saying that a statement is satisfiable only tells us that it is possible for it to be true, without saying anything whether or not it is also possible for it to be false

®     Unsatisfiable (or Contradiction): something for which no domains, predicates, or values can be chosen to make it true

***note: This SLOG was supposed to be posted before the test, but I ran into some password and username trouble with my account for the past couple weeks.