Ax = 0 is a homogeneous system of linear equations. 0 represents the zero vector. Every homogeneous system of linear equations has at least one solution which is the trivial solution or in other words the zero vector. A homogeneous system of linear equations with a nontrivial solution can be thought of as a set of vectors that when summed together start at the origin and end at the origin. Ax = 0 has a nontrivial solution if and only if the equation has at least one free variable.
Monday, May 30, 2016
Friday, May 27, 2016
Linear Algebra (4)
A vector y is said to be a linear combination of a set of vectors v1, v2, ... , vn if there exists scalars c1, c2, ... , cn, such that y = c1(v1) + c2(v2) + ... + cn(vn). span{v1, v2, ... , vn} is the set of all linear combinations of v1, v2, ... , vn. A linear combination can be viewed as a product of a matrix and a vector. The vector is the set of scalars and the matrix the set of vectors. The product of a matrix A and a vector x is written Ax. Ax = b has a solution if and only if b is a linear combination of the columns of A.
Ax = [ a1 , a2 , ... , an ]x = x1(a1) + x2(a2) + ... + xn(an)
So, linear systems can be viewed in three different ways. As a matrix equation, a vector equation, or as a set of linear equations in an augmented matrix.
A very important matrix to understand is the identity matrix. It is any square matrix with 1's along the diagonal and zeros elsewhere.
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
is a 6 x 6 identity matrix.
If A is an m x n matrix, u and v are vectors in ℝ^n, and c is a scalar, then A(u + v) = Au + Av and A(cu) = c(Au).
So, linear systems can be viewed in three different ways. As a matrix equation, a vector equation, or as a set of linear equations in an augmented matrix.
A very important matrix to understand is the identity matrix. It is any square matrix with 1's along the diagonal and zeros elsewhere.
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
is a 6 x 6 identity matrix.
If A is an m x n matrix, u and v are vectors in ℝ^n, and c is a scalar, then A(u + v) = Au + Av and A(cu) = c(Au).
Linear Algebra (3)
A matrix with only one column is called a vector.
1
V = 2
3
V can also be expressed as V = [ 1 , 2 , 3 ]. Essentially, a vector is an ordered set of numbers. The set of all vectors with three entries is denoted by ℝ^3. Given two vectors u and v in ℝ^3, their sum u + v is a vector w obtained by adding the corresponding entries of u and v. For example, if u = [ 1 , 2 , 3 ] and v = [ 2 , 3 , 4 ], then w = u + v = [ 1 , 2 , 3 ] + [ 2 , 3 , 4 ] = [ 1 + 2 , 2 + 3 , 3 + 4 ] = [ 3 , 5 , 7 ].
Given a vector u and a real number c, the scalar multiple of u by c is the vector c(u) obtained my multiplying each entry in u by c. The number c in c(u) is called a scalar.
Geometric Descriptions of ℝ^2
The following is a graph of the set of all vectors in ℤ^2 which is a subset of ℝ^2 such that each vector is not a scalar multiple of any other vector in the set and their components are between -8 to 8. The vectors that are in the set are marked with a purple dot.
Vector addition geometrically amounts to the construction of a parallelogram.
1
V = 2
3
V can also be expressed as V = [ 1 , 2 , 3 ]. Essentially, a vector is an ordered set of numbers. The set of all vectors with three entries is denoted by ℝ^3. Given two vectors u and v in ℝ^3, their sum u + v is a vector w obtained by adding the corresponding entries of u and v. For example, if u = [ 1 , 2 , 3 ] and v = [ 2 , 3 , 4 ], then w = u + v = [ 1 , 2 , 3 ] + [ 2 , 3 , 4 ] = [ 1 + 2 , 2 + 3 , 3 + 4 ] = [ 3 , 5 , 7 ].
Given a vector u and a real number c, the scalar multiple of u by c is the vector c(u) obtained my multiplying each entry in u by c. The number c in c(u) is called a scalar.
Geometric Descriptions of ℝ^2
The following is a graph of the set of all vectors in ℤ^2 which is a subset of ℝ^2 such that each vector is not a scalar multiple of any other vector in the set and their components are between -8 to 8. The vectors that are in the set are marked with a purple dot.
Here are some algebraic properties of ℝ^n:
For all u, v, and w in ℝ^n and scalars c and d
1.) u + v = v + u
2.) (u + v) + w = u + (v + w)
3.) u + 0 = u
4.) u + (-u) = 0
5.) c(u + v) = cu + cv
6.) (c + d)u = cu + du
7.) c(du) = (cd)u
8.) 1u = u
Linear Algebra (2)
In a matrix a leading entry is the leftmost nonzero entry in a row. Consider the following matrix.
1 3 4 5 6
0 1 3 5 7
0 0 1 2 3
Rows 1, 2, and 3 have leading entries at columns 1, 2, and 3 respectively. A matrix is in row echelon form if all nonzero rows are above any rows of all zeros, each leading entry of a row is in a column to the right of the leading entry of the row above it, and all entries in a column below a leading entry are zeros.
If a matrix is in row echelon form and each nonzero row has a leading entry of 1 and each leading 1 is the only nonzero entry in its column, then the matrix is said to be in reduced row echelon form. For example,
1 0 0 5 6
0 1 0 5 7
0 0 1 2 3
A pivot position in a matrix is a location that corresponds to a leading 1 in the reduced echelon form of the matrix. A pivot column is a column that contains a pivot position.
The Row Reduction Algorithm
Step 1
Begin with the leftmost nonzero. This is a pivot column. The pivot position is at the top.
Step 2
Select a nonzero entry in the pivot column as a pivot. If necessary, interchange rows to move this entry into the pivot position.
Step 3
Use row replacement operations to create zeros in all positions below the pivot.
Step 4
Repeat steps 1 - 3 to the submatrix that remains until there are no more nonzero rows to modify.
Step 5
Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, use a scaling operation to make it 1.
1 3 4 5 6
0 1 3 5 7
0 0 1 2 3
Rows 1, 2, and 3 have leading entries at columns 1, 2, and 3 respectively. A matrix is in row echelon form if all nonzero rows are above any rows of all zeros, each leading entry of a row is in a column to the right of the leading entry of the row above it, and all entries in a column below a leading entry are zeros.
If a matrix is in row echelon form and each nonzero row has a leading entry of 1 and each leading 1 is the only nonzero entry in its column, then the matrix is said to be in reduced row echelon form. For example,
1 0 0 5 6
0 1 0 5 7
0 0 1 2 3
A pivot position in a matrix is a location that corresponds to a leading 1 in the reduced echelon form of the matrix. A pivot column is a column that contains a pivot position.
The Row Reduction Algorithm
Step 1
Begin with the leftmost nonzero. This is a pivot column. The pivot position is at the top.
Step 2
Select a nonzero entry in the pivot column as a pivot. If necessary, interchange rows to move this entry into the pivot position.
Step 3
Use row replacement operations to create zeros in all positions below the pivot.
Step 4
Repeat steps 1 - 3 to the submatrix that remains until there are no more nonzero rows to modify.
Step 5
Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, use a scaling operation to make it 1.
Thursday, May 26, 2016
Linear Algebra (1)
Any system of linear equations can be transformed into a row equivalent system of equations or in other words one with the same solution set by using elementary row operations.
Elementary Row Operations
1.) Interchange two rows.
2.) Scale a row by a non-zero constant.
3.) Add a multiple of row to another row.
Consider the following matrix
1 0 1
0 1 1
Here, x = 1 and y = 1. If the rows are switched then the solution remains the same. If I scale a row, say row two by a constant c, then cy = c which means that cy/c = c/c but c/c = 1. So, y = 1; the solution remains the same. Now if I add row 1 to row 2 and replace row 1 with the result, then
1 1 2
0 1 1
Row 1 is now x + y = 2. So, this line has a y-intercept of 2 and a slope of -1 but still intersects row 2 at (1,1) because 1 + 1 = 2; a solution to the equation. In fact, no matter the multiple c of row 2 when added to row 1, which results in x + cy = c + 1 will always ensure that (1,1) is a solution since (1) + c(1) = c + 1.
Elementary Row Operations
1.) Interchange two rows.
2.) Scale a row by a non-zero constant.
3.) Add a multiple of row to another row.
Consider the following matrix
1 0 1
0 1 1
Here, x = 1 and y = 1. If the rows are switched then the solution remains the same. If I scale a row, say row two by a constant c, then cy = c which means that cy/c = c/c but c/c = 1. So, y = 1; the solution remains the same. Now if I add row 1 to row 2 and replace row 1 with the result, then
1 1 2
0 1 1
Row 1 is now x + y = 2. So, this line has a y-intercept of 2 and a slope of -1 but still intersects row 2 at (1,1) because 1 + 1 = 2; a solution to the equation. In fact, no matter the multiple c of row 2 when added to row 1, which results in x + cy = c + 1 will always ensure that (1,1) is a solution since (1) + c(1) = c + 1.
Sunday, May 22, 2016
Linear Algebra (0)
A linear equation is an equation that can be written in the form
1 -2 1 0
0 2 -8 8
-4 5 9 -9
a1x1 + a2x2 + ... + anxn = b
where a1,a2,...,an and b are real or complex numbers. A linear system is a collection of one or more linear equations involving the same variables. A solution of a system is a list s1, s2, ..., sn of numbers that make each equation a true statement when the values of s1, s2, ... , sn are substituted for x1, x2, ... , xn, respectively. The set of all possible solutions is called the solution set of the linear system. Two linear systems are equivalent if they have the same solution set.
A system of linear equations has
1.) no solution, or
2.) exactly one solution, or
3.) infinitely many solutions.
A system of linear equations is said to be consistent if it has either one solution or infinitely many solutions; a system is inconsistent if it has no solution.
Matrix Notation
The equations
x - 2y + z = 0
2y - 8z = 8
-4x + 5y + 9z = -9
can be compactly recorded in the following ways. First, by using a coefficient matrix, and by using an augmented matrix.
1 -2 1
0 2 -8
-4 5 9
0 2 -8 8
-4 5 9 -9
Sunday, May 15, 2016
About Proofs
Definition: A sequent is an expression (A ⊢ C) where C is a statement called the conclusion of the sequent and A is a set of statements called the assumptions of the sequent. (A ⊢ C) is read 'A entals C' and means that there is a proof whose conclusion is C and whose undischarged assumptions are all in the set A. (⊢ C) means there is a proof of C relying on no undischarged assumptions.
Sequent Rule (∧I): If (A ⊢ C) and (B ⊢ D), then [(A ⋃ B) ⊢ (C ∧ D)].
Sequent Rule (∧E): If [A ⊢ (B ∧ C)], then (A ⊢ B) and (A ⊢ C).
Sequent Rule (⇒I): If [A ⋃ {b} ⊢ C], then [A ⊢ (b ⇒ C)].
Sequent Rule (⇒E): If (A ⊢ C) and [B ⊢ (C ⇒ D)], then [(A ⋃ B) ⊢ D]
Sequent Rule (∧I): If (A ⊢ C) and (B ⊢ D), then [(A ⋃ B) ⊢ (C ∧ D)].
Sequent Rule (∧E): If [A ⊢ (B ∧ C)], then (A ⊢ B) and (A ⊢ C).
Sequent Rule (⇒I): If [A ⋃ {b} ⊢ C], then [A ⊢ (b ⇒ C)].
Sequent Rule (⇒E): If (A ⊢ C) and [B ⊢ (C ⇒ D)], then [(A ⋃ B) ⊢ D]
Just Kidding
I found a more appropriate textbook than Hurley's. It's title is Mathematical Logic and it is written by Ian Chriswell.
Friday, May 13, 2016
Examples of Proofs with Quantifiers
∀x(Ax ⇒ Bx), ∀x(Bx ⇒ Cx) ⊢ ∀x(Ax ⇒ Cx)
1.) ∀x(Ax ⇒ Bx) Hyp
2.) Ax ⇒ Bx UI
3.) ∀x(Bx ⇒ Cx) Hyp
4.) Bx ⇒ Cx UI
5.) Ax ⇒ Cx Th5
6.) ∀x(Ax ⇒ Cx) UG
∀x(Bx ⇒ Cx), ∃x(Ax ∧ Bx) ⊢ ∃x(Ax ∧ Cx)
1.) ∃x(Ax ∧ Bx) Hyp
2.) ∀x(Bx ⇒ Cx) Hyp
3.) Ac ∧ Bc EI
4.) (Ac ∧ Bc) ⇒ Bc Th28
5.) (Ac ∧ Bc) ⇒ Ac Th29
6.) Bc mp 3,4
7.) Ac mp 3,5
8.) Bc ⇒ Cc UI
9.) Cc mp 6,8
10.) Ac ⇒ [ Cc ⇒ (Ac ∧ Cc)] Th30
11.) Cc ⇒ (Ac ∧ Cc) mp 7,10
12.) (Ac ∧ Cc) mp 9,11
13.) ∃x(Ax ∧ Cx) EG
1.) ∀x(Ax ⇒ Bx) Hyp
2.) Ax ⇒ Bx UI
3.) ∀x(Bx ⇒ Cx) Hyp
4.) Bx ⇒ Cx UI
5.) Ax ⇒ Cx Th5
6.) ∀x(Ax ⇒ Cx) UG
∀x(Bx ⇒ Cx), ∃x(Ax ∧ Bx) ⊢ ∃x(Ax ∧ Cx)
1.) ∃x(Ax ∧ Bx) Hyp
2.) ∀x(Bx ⇒ Cx) Hyp
3.) Ac ∧ Bc EI
4.) (Ac ∧ Bc) ⇒ Bc Th28
5.) (Ac ∧ Bc) ⇒ Ac Th29
6.) Bc mp 3,4
7.) Ac mp 3,5
8.) Bc ⇒ Cc UI
9.) Cc mp 6,8
10.) Ac ⇒ [ Cc ⇒ (Ac ∧ Cc)] Th30
11.) Cc ⇒ (Ac ∧ Cc) mp 7,10
12.) (Ac ∧ Cc) mp 9,11
13.) ∃x(Ax ∧ Cx) EG
Rules of Inference for Quantifiers
Universal Instantiation (UI)
The operation of deleting the universal quantifier and replacing every variable bound by that quantifier with a constant or a variable.
Universal Generalization (UG)
The operation of adding a universal quantifier to a formula possessing at least one occurrence of a variable to be quantified. This rule cannot be applied to constants.
Existential Instantiation (EI)
The operation of deleting the existential quantifier and replacing in each occurrence of the variable with a constant. The existential name or constant to be used must be a new name that has not occurred in any previous lines in the proof.
Existential Generalization (EG)
The operation of adding a existential quantifier to a formula possessing either a constant or a variable and replacing it with a new quantified variable.
Predicate Logic Translations (2)
19.) Whoever is a socialite is vain: ∀x(Sx ⇒ Vx)
20.) Any caring mother is vigilant and nurturing: ∀y[(Cy ∧ My) ⇒ (Vy ∧ Ny)]
21.) Terrorists are neither rational nor empathic: ∀z[Tx ⇒ (¬Rx ∧ ¬Ex)
22.) Nobody consumed by jealousy is happy: ¬∃y(Cy ∧ Hy)
23.) Everything is imaginable: ∀w(Iw)
24.) Ghosts do not exist: ¬∃z(Gz)
25.) A thoroughbred is a horse: ∀y(Ty ⇒ Hy)
26.) A thoroughbred won the race: ∃z(Tz ∧ Wz)
27.) Not all mushrooms are edible: ∃x(Mx ∧ ¬Ex)
28.) Not any horse chestnuts are edible: ∀w(Hw ⇒ ¬Ew)
29.) A few guests arrived late: ∃x(Gx ∧ Ax)
30.) None but gentlemen prefer blondes: ∀x(Px ⇒ Gx)
31.) A few cities are neither safe nor beautiful: ∃w[(Cw ∧ ¬Sw) ∧ ¬Bw]
32.) There are no circular triangles: ¬∃z(Cz ∧ Tz)
33.) Snakes are harmless unless they have fangs: ∀x[(Sx ∧ Fx) ⇒ ¬Hx]
34.) Some dogs bite if and only if they are teased: ∃y[(Dy ∧ By) ⇔ Ty]
35.) An airliner is safe if and only if it is properly maintained: ∀z[(Az ∧ Sz) ⇔ Pz]
20.) Any caring mother is vigilant and nurturing: ∀y[(Cy ∧ My) ⇒ (Vy ∧ Ny)]
21.) Terrorists are neither rational nor empathic: ∀z[Tx ⇒ (¬Rx ∧ ¬Ex)
22.) Nobody consumed by jealousy is happy: ¬∃y(Cy ∧ Hy)
23.) Everything is imaginable: ∀w(Iw)
24.) Ghosts do not exist: ¬∃z(Gz)
25.) A thoroughbred is a horse: ∀y(Ty ⇒ Hy)
26.) A thoroughbred won the race: ∃z(Tz ∧ Wz)
27.) Not all mushrooms are edible: ∃x(Mx ∧ ¬Ex)
28.) Not any horse chestnuts are edible: ∀w(Hw ⇒ ¬Ew)
29.) A few guests arrived late: ∃x(Gx ∧ Ax)
30.) None but gentlemen prefer blondes: ∀x(Px ⇒ Gx)
31.) A few cities are neither safe nor beautiful: ∃w[(Cw ∧ ¬Sw) ∧ ¬Bw]
32.) There are no circular triangles: ¬∃z(Cz ∧ Tz)
33.) Snakes are harmless unless they have fangs: ∀x[(Sx ∧ Fx) ⇒ ¬Hx]
34.) Some dogs bite if and only if they are teased: ∃y[(Dy ∧ By) ⇔ Ty]
35.) An airliner is safe if and only if it is properly maintained: ∀z[(Az ∧ Sz) ⇔ Pz]
Thursday, May 12, 2016
Predicate Logic Translations (1)
1.) Elaine is a chemist: Ce
2.) Nancy is not a sales clerk: ¬Sn
3.) Neither Wordsworth nor Shelley was Irish: ¬Iw ∧ ¬Is
4.) Rachel is either a journalist or a newscaster: (Jr ∨ Nr) ∧ ¬(Jr ∧ Nr)
5.) Intel designs a faster chip only if Micron does: Dm ⇒ Di
6.) Belgium and France subsidize the arts only if Austria or Germany expand museum holdings: (Ea ∨ Eg) ⇒ (Sb ∧ Sf)
7.) All maples are trees: ∀x(Mx ⇒ Tx)
8.) Some grapes are sour: ∃x(Gx ∧ Sx)
9.) No novels are biographies: ¬∃y(Ny ∧ By)
10.) Some holidays are not relaxing: ∃z(Hz ∧ ¬Rz)
11.) If Gertrude is correct, then the Taj Mahal is made of marble: Cg ⇒ Mt
12.) Gertrude is not correct only if the Taj Mahal is made of granite: Gt ⇒ ¬Cg
13.) Tigers exist: ∃z(Tz)
14.) Anything that leads to violence is wrong: ∀x(Lx ⇒ Wx)
15.) There are pornographic art works: ∃u(Pu ∧ Au)
16.) Not every smile is genuine: ¬∀x(Sx ⇒ Gx)
17.) Every penguin loves ice: ∀z(Pz ⇒ Lz)
18.) There is trouble in River City: ∃u(Tu ∧ Ru)
2.) Nancy is not a sales clerk: ¬Sn
3.) Neither Wordsworth nor Shelley was Irish: ¬Iw ∧ ¬Is
4.) Rachel is either a journalist or a newscaster: (Jr ∨ Nr) ∧ ¬(Jr ∧ Nr)
5.) Intel designs a faster chip only if Micron does: Dm ⇒ Di
6.) Belgium and France subsidize the arts only if Austria or Germany expand museum holdings: (Ea ∨ Eg) ⇒ (Sb ∧ Sf)
7.) All maples are trees: ∀x(Mx ⇒ Tx)
8.) Some grapes are sour: ∃x(Gx ∧ Sx)
9.) No novels are biographies: ¬∃y(Ny ∧ By)
10.) Some holidays are not relaxing: ∃z(Hz ∧ ¬Rz)
11.) If Gertrude is correct, then the Taj Mahal is made of marble: Cg ⇒ Mt
12.) Gertrude is not correct only if the Taj Mahal is made of granite: Gt ⇒ ¬Cg
13.) Tigers exist: ∃z(Tz)
14.) Anything that leads to violence is wrong: ∀x(Lx ⇒ Wx)
15.) There are pornographic art works: ∃u(Pu ∧ Au)
16.) Not every smile is genuine: ¬∀x(Sx ⇒ Gx)
17.) Every penguin loves ice: ∀z(Pz ⇒ Lz)
18.) There is trouble in River City: ∃u(Tu ∧ Ru)
Wednesday, May 11, 2016
Textbook Found
I finally found a textbook that I can trust. I've been through quite a few. The predicate logic presented in this textbook is user friendly and more for philosophy but is just as valid as any mathematical presentation. So, I'm going to go with my new textbook and trust it. Besides it's from Patrick J. Hurley. He's been writing textbooks for decades.
Subscribe to:
Posts (Atom)