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'.
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).
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 True-False test with 10 questions. Let p_i be the probability that you get answer i correct. Assume that the probabilities are independent.
Give an example of a relation which is not reflexive, not symmetric, not anti-symmetric, 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 non-isomorphic undirected graphs each with six vertices where every vertex has degree exactly two.
Let G=(V,E) be an undirected graph. The complement of G, G' is defined as the graph G'=(V,E') where E'={(v,w) | v is in V, w is in V, v!= w, (v,w) is not in E}. Give an example of a graph G such that both G and G' contain Hamiltonian circuits.
Let G=(V,E) be a graph with |V| >= 5. Prove that if G is 2-colorable (bipartite), then G' (its complement) is not 2-colorable.
The following terms are used in the propositional calculus. Give a one sentence definition for each of the terms.
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''.
Consider the English alphabet, which consists of 5 vowels and 21 consonants.
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.
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).
For which values of n does K_n contain an Eulerian circuit. (K_n denotes the complete graph on n vertices, K_n is undirected.) Justify your answer.
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.
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
Write a predicate logic statement equivalent to the negation of each of the statements above that DOES NOT USE negation anywhere except immediately in front of the predicate symbols S, F, and O.
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.
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] TransitiveYou do not need to justify your answers.
Here is a recursive definition of a "forest", a kind of undirected graph.
Suppose that R is a relation on a set A. Prove or disprove: If R^2 is reflexive then R must be reflexive.
Let n be a positive integer. A
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.)
To qualify for championships in certain games or sports there are sometimes "round-robin tournaments" in which each team plays a exactly one game against each other team. Suppose that n>= 2 teams played a round-robin tournament and assume that there were no ties (i.e. each game had a winner.)
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:
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.
Let R be the relation { (1,2), (3,4), (1,3), (2,1) } defined on the set {1,2,3,4,5}.
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^*.