Show that the proposition
p> ((q> (r> s)) > t)
is a contingency WITHOUT constructing its full truth table.
Using the universe of integers for all quantifiers express the
following English sentences in predicate logic using the predicates,
P, E, and L where P(x) means `x is prime', E(x) means `x is even',
and L(x,y) means `x < y'.
 No prime greater than 2 is even.
 For every number, there is a larger prime number.
 Translate the following predicate logic expression into
English where
the predicates are the same as above:
 FORALL x [( E(x) AND P(x)) > L(x,100)].
In an undirected graph G, we define dist(v,w) to be
the length of the shortest path from v to w. Show that for vertices
x, y, z, we have dist(x,z)<= dist(x,y) + dist(y,z).
Let G=(V,E) be a directed graph. Define a relation R on
E by (e_1,e_2) is an element of R iff e_1 and e_2 lie on a common simple
circuit.
(Recall that a simple circuit is a path that starts and ends at the
same vertex, and does not repeat any edges).

Is R necessarily reflexive? Prove or disprove.

Is R necessarily symmetric? Prove or disprove.

Is R necessarily transitive? Prove or disprove.
Let R be a relation on a set A.
Is the transitive closure of R always equal to the transitive
closure of R^2 ? Prove or disprove.
Prove that in the graph below, there are exactly 2^n paths of
length 2n between vertex A and vertex B for n>= 1.
* * * *
/ \ / \ / \ / \ / \
A * * * * * ... * B
\ / \ / \ / \ / \ /
* * * *
(n diamond shapes in a row)
The formula
~(p > ~q) > (r > (~s > t)) is false for exactly
one assignment to p, q, r, s and t. Find this assignment
WITHOUT constructing a truth table.
Determine the number of strings over {a,b,c} of length
100 that have exactly 98 a's.
Suppose that you are working on a TrueFalse test with 10
questions. Let p_i be the probability that you get answer i
correct. Assume that the probabilities are independent.
 What is the probability of getting all of the answers wrong
(expressed as a formula involving p_1, p_2, ... , p_10).

If p_i = 1 2^{i}, what is your expected number of
correct answers.
Give an example of a relation which is not reflexive, not
symmetric, not antisymmetric, and not transitive. (You are to give
one relation that lacks all of these properties, not separate
relations for each property.)
Justify your answer.
Give three different equivalence relations on the set {a,b,c,d}.
Let G be a directed graph with n vertices. Show that if G has a
path of length greater than n, then G has a cycle.
Give a pair of nonisomorphic undirected
graphs each with six vertices where every vertex has degree exactly
two.
The following terms are used in the propositional calculus. Give a
one sentence definition for each of the terms.
 Contingency
 Contrapositive
 Converse
Give logical expressions for the following statements. Use
quantifiers, connectives, and the predicates P(x) and H(x) which
mean
``x passed the class'' and ``x turned in all of the homework''.

Every student that passed the class turned in all of the
homework.

There was a student that passed the class, but did not turn
in all of the homework.
Consider the English alphabet, which consists of 5 vowels and 21
consonants.
 How many strings of length 10
consist of 5 vowels followed by 5 consonants?
 How many strings of length 10 consist of 5 distinct vowels
followed
by 5 distinct consonants. (In other words, the string has no repeated
characters.)
You may express your answers as products of integers.
Suppose that
propositions p_1, p_2, ... , p_{n+1} are independently assigned
random truth
values, where the probability that p_i is true is 1/2.
 What is the probability that the compound proposition
p_1 AND p_2 AND ... AND p_n is true?
 What is the probability that the compound proposition
(p_1 AND p_2 AND ... AND p_n) > p_{n+1} is true?
Let A={x, y, z}, B={1, 2, 3 ,4}, and C={a, b, c}.
Let R be the following relation from A to B:
R={(x,1), (x,2), (y,2), (y,3), (z,3)}, and S be the following
relation from B to C:
S={(1,a), (2,a), (2,b), (3, b), (4,b), (4,c)}.
Compute the composition of R and S.
Suppose R_1 and R_2 are transitive relations on a set A. Is the
relation R_1 UNION R_2 necessarily a transitive relation? Justify
your answer.
Suppose R is the relation on the integers where xRy if and only if
x = y+1. Describe the relation that is the transitive closure of R.
Let the relation L be defined on the integers
by x L y if x < y or (x = y and x <= y).
 List the elements of {4, 3, 2, 1, 0, 1, 2, 3, 4}
under the L ordering.
 Argue that this ordering relation is total.
Let G=(V,E) be the undirected
graph that has as its vertices the set of integers, and
edges: E = {(x,x+3) x is an integer}.
Describe the connected components of G.
How many edges do the following undirected graphs contain.
 K_n, the complete graph on n vertices.
 K_{n,m}, the complete bipartite graph between n vertices
and m vertices.
 Q_n, the n dimensional hypercube. (Q_n has 2^n vertices.)
Translate the following English sentences into predicate
logic where
the universe is the set of people and the allowable predicates are:
S(x) : x is a student
F(x,y) : x and y are friends
O(x,y) : x is older than y
Suppose that n >= 3 and p_1,..., p_n are propositions that are
true or false independently with probability exactly 1/2. Justify your answers.
 What is the probability that (p_1 v p_2)> p_3 is true?
 What is the probability that (p_1 v ... v p_{n1}) > p_n is true?
 What is the expected number of propositions p_i that are true?
In each of the following questions a relation R is defined. Assume
that each R is defined over some natural set A.
For each of the following properties, circle ALL those properties that
ALWAYS apply and X out those properties that do NOT
apply at least some of the time.
[R] Reflexive
[S] Symmetric
[A] Antisymmetric
[T] Transitive
You do not need to justify your answers.
 xRy iff
there is a path of length at least 0 from vertex x to vertex y in
undirected graph G.
 xRy iff
there is a path of length at least 0 from vertex x to vertex y in directed graph G.
 The relation R defined on undirected graphs where
(G_1,G_2) is in R iff G_1 is isomorphic to G_2.
 The relation R defined on the set of nonnegative real numbers
where xRy if and only if x<= y.
 The relation R defined on the natural numbers where
xRy iff x = y (mod 51).
 The relation R defined on the natural numbers where
xRy iff x = (y+1) ( mod 51).
 The relation R defined on the set of people where
xRy iff x is a grandparent of y.
 xRy iff x=y.
 xRy iff x is a subset of y.
 xRy iff positive integer x divides positive integer y.

Here is a recursive definition of a "forest",
a kind of undirected graph.
 A graph with one or more nodes and no edges is a forest.
 If G=(V,E) is a forest then for any nodes x and y of G that are
not connected by a path in G the graph H consisting of G plus the
edge {x,y} is also a forest.
 (A graph is a forest only if it can be constructed using the
above two rules.)
Prove by induction that every forest with v vertices and e edges
has exactly ve connected components.

Suppose that R is a relation on a set A.
Prove or disprove:
If R^2 is reflexive then R must be reflexive.
 Let R be the relation { (3,2), (3,4), (1,3), (2,1)}
defined on the set {1,2,3,4,5}.
 Draw the graph of R.
 Draw the graph of the transitive closure of R.
 Draw the graph of the reflexivetransitive closure of R.

Let n be a positive integer. A perfect matching on a set of 2n
vertices is an undirected graph with n edges, such that each vertex has
degree exactly 1.
For example,
there is one perfect matching on any set of two vertices
(with edge set {{1,2}} if the vertices are {1,2}), and three distinct
perfect matchings on four
vertices (with edge sets {{1,2},{3,4}}, {{1,3},{2,4}}, and {{1,4},{2,3}} if
the vertices are {1,2,3,4}).
Prove by induction that the number of perfect matchings on 2n vertices is the
product of the odd numbers less than 2n (so for n=2 it is 1x3).
As part of its effort to make U.S. paper money harder to counterfeit,
the U.S. Treasury has decided to redesign the 1, 5, 10, 20, and 50 dollar
bills. However, people have grown tired of seeing boring
presidents on the bills so the Treasury Department is looking for more appealing
candidates to appear on these 5 different bills.
They have narrowed the field of available candidates to seven actors
{a_1,...,a_7}, eight basketball players {b_1,...,b_8},
six cartoon characters {c_1,...,c_6},
and five disc jockeys {d_1,...,d_5}. (These four sets are pairwise
disjoint, so there are 26 candidates in all.)
Please JUSTIFY your answers for each of the following questions about the
possible choices the Treasury Department might make.
(Answers in the form of
arithmetic expressions involving only +,*,,/ and !, are acceptable for
full credit.)
 In how many ways can the Treasury Department decide which five
candidates appear on the bills, without worrying about which bill they
will appear on? (An example choice is {a_3, a_6, c_3, c_8, d_4}.)
 In how many ways can the Treasury department make the same choice
as in part (a) if they are required to choose at least one candidate from
each of the 4 categories?
 If the Treasury chooses the candidates for the five bills randomly,
so that each sequence of five distinct candidates has equal probability, what
is the probability of the assignment ``c_2 on $1, d_4 on $5,
b_5 on $10, c_6 on $20, and a_1 on $50''?
 If the Treasury chooses the candidates randomly as in part (c), what is
the probability that cartoon characters appear on the $5 and $10 bills but
not on the $50 bill?
 How many different undirected graphs are there on vertices {1,2,3}?
Explain your answer.
 How many of these are connected?
 How many have exactly two connected components?
 How many have Euler tours?
 How many {\em nonisomorphic} undirected graphs are there on 3 vertices?
(That is, if G and G' are isomorphic then we only count one of them.)
Draw one of each.
To qualify for championships in certain games or sports there are
sometimes "roundrobin tournaments" in which each team plays a exactly one
game against each other team. Suppose that n>= 2 teams played a
roundrobin tournament and assume that there were no ties (i.e. each game had
a winner.)
 If we define relation R on the set of teams by xRy if and only if x won
its game against y which of the following properties does R always have:
Reflexive, Irreflexive, Symmetric, Antisymmetric, Transitive?
(EXPLAIN why or why not for each of the 6 cases.)
 Consider the directed graph G_{R} representing relation R
from part (a). What is the
sum of the indegrees of all the vertices in G_{R}? What is the sum of the
outdegrees? Explain your answers.

Prove that there is a team that won at least [(n1)/2] games where [x]
means the smallest integer >= x.
In stud poker (as opposed to draw poker), 4 of the 5 cards in
the poker hand are dealt 'face up' so that everyone can see them and one card is
'face down' so that nobody can see it. Suppose that we start with a perfectly
shuffled deck so that the cards are equally like to be in any order.
EXPLAIN your answers to each of the following questions:
 If only one hand is dealt, what is the probability that this is a
'full house' (recall that's 3 cards of one rank and 2 of another)?
 What is the conditional probability of that hand being a full house given
that the four `face up' cards are 2 pairs (i.e. 2 cards of each of two ranks)?
 What is the conditional probability of that hand being a full house
given that the four `face up' cards contain 3 of one rank and 1 of another?
 If 4 players are dealt poker hands from this perfectly shuffled deck
what is the expected number of players who have full houses?
In the land of Garbanzo, the unit of currency is the bean. They only
have two coins, one worth 2 beans and the other worth 5 beans.
 Give a recursive definition of the set of positive integers S such that
x is in S if and only if one can make up an amount worth x beans using
at most one 5bean coin and any number of 2bean coins.
 Prove by strong induction that every integer >= 4 is in S.
(You do NOT need a recursive proof here.)
Let R be the relation { (1,2), (3,4), (1,3), (2,1) }
defined on the set {1,2,3,4,5}.
 Draw the graph of R.
 Draw the graph of the transitive closure of R.
 Draw the graph of the reflexivetransitive closure of R.
If R is a relation on a set A then we say that
R is {\em total} if and only if
FORALL x in A THERE EXISTS y in A, xRy.
Prove that if R is symmetric and total then its transitive
closure is also reflexive, i.e. R^+=R^*.
 For each n>= 0 define T_n>, the
'complete 3ary tree of height n' as follows:
 T_0 is an undirected graph consisting of a single vertex called
the root of T_0.
 For n>= 0, T_{n+1} is an undirected graph consisting of a new
vertex of degree 3 joined to the roots of 3 disjoint copies of T_n.
The new vertex is called the root of T_{n+1}.
Prove by induction that for each n>= 0, T_n has exactly
(3^{n+1}1)/2 vertices.
 Suppose that you have a rectangular cake which you need to
cut into n rectangles of equal size by successively cutting the cake into
chunks. Show that no matter
how you do it you need to make exactly n1 cuts in the cake (where a
single cut is a straight line cut of one chunk, i.e. you are NOT allowed to line
up several chunks and cut them at once.)
(Hint: induction may help.)