CSC 28 - Discrete Structures - Quantified Statements
----------------------------------------------------

** These notes are not intended as a replacement to lecture. There sole purpose
** is to remind me what I want to say, and remind you what I thought was
** important


** Predicates (aka Conditional Statements):

- A predicate is a statement about one or more variables.

   "I have x dollars in my wallet" <== single variable predicate
   " x < y"                        <== two variable predicate

** Quantified statements:

Sometimes we want to say that every element in the universe has some property.
Let's say the universe is the people in this room and we want to say everyone
in the room is awake.

- Everyone in this room is awake.

- Let P(x) mean "x is awake"

   P(Allie) and P(Bob) and P(Cara) and ...  (list them all, or make a pattern)

Shortcomings: First is monolithic an inflexible. Second is cumbersome.

New notation:

\forall x P(x)  --  States every element in the universe makes P true.

    true iff truth set of P is the universe U

\exists x P(x)  --  States at least one element in the universe makes P true.

    true iff { x | P(x) } != { }

Ex: Analyze logical form

- Someone didn't do the homework.

Create relevant predicate: H(x) means "x did the homework"
What does someone mean? At least one person.

  Try 1:  \not ( \exists x H(x) )

          Means it's not true that at least one person did their homework.

  Try 2:  \exists x \not H(x) )

          Means, for at least one person, they did not do their homework.

- Nobody's perfect.

   \forall x \not P(x)  or  \not \exists x P(x)

- A \intersect B \subseteq B \ C

Asserts that every x found in A \intersect B can also be found in  B \ C.

  x \in A \intersect B \implies x \in B \ C               <==  Predicate!!
  \forall x (x \in A \intersect B \implies x \in B \ C)   <==  Statement!!


** Bound versus free variables

Each variable in an expression is either bound or free.

-- Free if a value must be supplied to it before expression can be evaluated.
-- Bound if not free (usually a dummy variable)

Ex: { x | x \in Z and x > c }

Which variables need we supply a value before the expression can be evaluated?

x: no, it is a dummy variable.
c: yes, once we give a value for c, we know exactly which values are in the
set.


Ex: (x^2 - 4 > c)

Which variables need we supply a value before the expression can be evaluated?

Both x and c. Without knowing both we cannot evaluate the expression.


Ex: \forall x (x^2 - 4 > c)

Which variables need we supply a value before the expression can be evaluated?

x: no, it is a dummy variable.
c: yes, once we give a value for c, we can evaluate the expression.


** Multiple quantifiers

A statement may have more than one quantifier.

\forall x \exists y (x > y)

  x > y is an expression with two free variables: evaluates to true if x is
supplied which is greater than y.

  \exists y (x > y) is an expression with one free variables: evaluates to true
if x is supplied and there is a y greater than the supplied x.

  \forall x \exists y (x > y) is an expression with no free variables:
evaluates to true if \exists y (x > y) is true for every x in the universe.

\forall x P(x) \implies \forall x Q(x)

  States that whenever "\forall x P(x)" is a true statement, then so is
"\forall x Q(x)".

Ex: Analyze logical form

- Anyone who has a friend who has measles will have to be quarantined

Go slowly...

Overall statement: \forall x (if x has a friend with measles, x must be
quarantined)

How do we say "x has a friend with measles"?

  \exists y (x and y are friends, and y has measles)

So...

  \forall x (\exists y (x and y are friends, and y has measles) \implies x must
be quarantined)

Let...

  F(x,y) mean "x and y are friends"
  M(x) mean "x has measles"
  Q(x) mean "x must be quarantined"

Finally...

  \forall x (\exists y (F(x,y) \and M(y)) \implies Q(x))

- If A \subseteq B, then A and C\B are disjoint.

Slowly...
  Overall: (A \subseteq B) \implies (A and C\B are disjoint)
  A \subseteq B  goes to  \forall x (x \in A \implies x \in B)
  A and C\B are disjoint  goes to  \not \exists x (x \in A and x \in C\B)

Finally...

  \forall x (x \in A \implies x \in B) \implies \not \exists x (x \in A and x
\in C\B)


** Equivalence

- Negations

  \not \exists x P(x)  ==  \forall x \not P(x)
  \not \forall x P(x)  ==  \exists x \not P(x)

I remember this as: "you can push a negation through a quantifier by toggling
the quantifier.

Ex: Everyone in the room is awake. Opposite: Everyone is asleep? No. Someone is
asleep.

Ex: Write \not (A \subseteq B) as a positive statement (ie, saying something is
true)

  \not (A \subseteq B)
      == \not \forall x (x \in A \implies x \in B)
      == \exists x \not (x \in A \implies x \in B)   Quantifier Negation
      == \exists x \not (\not (x \in A) \or x \in B) Conditional Definition
      == \exits x ( x \in A and x \notin B)          DeMorgans

- Back to back quantifiers

  \forall x \exists y P(x,y) says "for every x there is a y which makes P true"
  \exists y \forall x P(x,y) says "there is a y for which every x makes P true"

  These are very different. On the other hand,

  \forall x forall y, P(x,y) == \forall y forall x, P(x,y)

  Both say "every pair x and y makes P true".


** Bounded Quantifiers

If we wish to say that P(x) is true for every x that is in set A, we can write

  \forall x (x \in A \implies P(x))

but instead we use the shorthand

  \forall x \in A P(x)

They are equivalent, and so may be substituted for one another.

Likewise...

  \forall x (x > 5 \implies P(x))  ==  \forall x > 5 P(x)