- 3.1.1: For a real number x, consider the open sentence P(x): (x1)2 > 0. St...
- 3.1.2: State the following as a quantified statement: If n is an integer, ...
- 3.1.3: For an odd integer n, let P(n): 7n+4 is odd. Express the quantified...
- 3.1.4: Express the following in symbols: There is some integer n such that...
- 3.1.5: Let S denote the set of odd integers and consider the open sentence...
- 3.1.6: Describe a set S and define an open sentence R(x) of your own for x...
- 3.1.7: State the negations of the following quantified statements. (a) For...
- 3.1.8: State the negations of the following quantified statements. (a) For...
- 3.1.9: State the negations of the following quantified statements. (a) For...
- 3.1.10: Express the following quantified statements in symbols. (a) For eve...
- 3.1.11: State the negations of the following quantified statements. (a) For...
- 3.1.12: State the negations of the following quantified statements. (a) For...
- 3.1.13: State the negations of the following quantified statements. (a) Onc...
- 3.1.14: Consider the following quantified statement: For every even integer...
- 3.1.15: Consider the following quantified statement: There exist an even in...
- 3.1.16: Consider the following quantified statement: For every real number ...
- 3.1.17: Consider the following quantified statement: There exists an intege...
- 3.1.18: State the negation of the quantified statement below. For every int...
- 3.1.19: State the negation of the quantified statement below. For every int...
Solutions for Chapter 3.1: Quantified Statements
Full solutions for Discrete Mathematics | 1st Edition
Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!
Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.
Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).
Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].
Diagonal matrix D.
dij = 0 if i #- j. Block-diagonal: zero outside square blocks Du.
Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra -eij in the i, j entry (i #- j). Then Eij A subtracts eij times row j of A from row i.
Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).
Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.
Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .
Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A - AI) if no eigenvalues are repeated; always meA) divides peA).
Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b - Ax) = o.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.
Permutation matrix P.
There are n! orders of 1, ... , n. The n! P 's have the rows of I in those orders. P A puts the rows of A in the same order. P is even or odd (det P = 1 or -1) based on the number of row exchanges to reach I.
The diagonal entry (first nonzero) at the time when a row is used in elimination.
Rank r (A)
= number of pivots = dimension of column space = dimension of row space.
R = [~ CS ] rotates the plane by () and R- 1 = RT rotates back by -(). Eigenvalues are eiO and e-iO , eigenvectors are (1, ±i). c, s = cos (), sin ().
Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!
Constant down each diagonal = time-invariant (shift-invariant) filter.
Tridiagonal matrix T: tij = 0 if Ii - j I > 1.
T- 1 has rank 1 above and below diagonal.
Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.