MTH 114: Logic, Linear Algebra - ND

• MTH 114 covers Logic and Linear Algebra
• The lecture notes are for ND (National Diploma) students
• The date of the lecture notes is November 20, 2016
• The author of this lecture not is Umar Ashafa Sulaiman, Department of Mathematics and Statistics, Federal Polytechnic Nasarawa

Course outline

• Logic and abstract thinking are part of this course
• Permutation and Combination are part of this course
• Binomial Theorem of Algebraic Expressions are part of this course
• Matrices and Determinants are part of this course

Logic and Abstract Thinking

• This is the first chapter of the lecture notes and is an introduction to Logic and Linear Algebra

Logic Basics

• Logic is the study of formal reasoning using statements or propositions
• The basic principles of logic are based on two laws

Laws of Logic

• The law of contradiction states a statement cannot be true and false
• The law of excluded middle states a statement must be either true or false

Linear Algebra

• This is the branch of mathematics dealing with the theory of systems of linear equations,vector spaces, matrices, determinants and linear transformations.

Logic

• Chapter 2 covers logical and non-logical statements

Basic Concepts of Logic

• A statement (or Proposition) is a meaningful declarative sentence
• Can be either True (T) or False (F)

Examples of Simple Logical Statements

• "I am in ND 1"
• "The phone is ringing"
• "3 + 5 = 30"
• "The color of the pen is red"
• "I am eating"
• "6/3 = 2"

Non-Logical Statements

• Statements can't be either true or false

Examples of Non-Logical Statements

• "How are you?"
• "Is he a boy?"

Truth Value of a Statement

• This is the state in which the statement is either True (T) or False (F)
• If the statement is True, then its truth value is T
• If a statement is false, then its truth value is F
• Statements are usually represented by symbols or letters

Symbolic representation of a Statement

• p := The sky is black
• The truth value of the above statement is F since the sky is not black

Connectives

• A logical connective is a symbol or word used with a statement or connects two or more statements
• Essential connectives are commonly used

Common Connectives are

• Negation (NOT) - symbol: ~
• Conjunction (AND) - symbol: ∩
• Disjunction (OR) - symbol: U
• Implication (IF...THEN...) - symbol: →
• Bi-implication (...IFF...) - symbol: ↔

Compound Statement

• This is statement consisting of a combination of statements and connectives

Examples of Compound Statements

• "The colour of the car is NOT red" symbolized by ~p
• "2 + 3=5 AND 7/3 = 4" symbolized by p ∩ q
• "All Nigerians are tall OR All Nigerians are happy" symbolized by p U q

Statement to Symbols Form and Meaning

Negation

• Emeka is not tall, symbol ~p
• Assumption : p := Emeka is tall
• She id not ugly, symbol ~q
• Assumption: q:= She is ugly

Conjunction

• Assumption: p := 41 is prime, q := 41 is even
• 41 is prime but not even, symbol p ∩ q

Disjunction

• He is at home or work, symbol p U q
• Assumption: p := He is at home, q := He is at work

Implication

• If 2 can divide 8, then 8 is even, symbol p → q
• Assumption: p := 2 can divide 8, q := 8 is even

Converse, Inverse and Contrapositive

• These are based on a conditional statement p→q
• In the statement p → q, p is called the hypothesis
• q is called the conclusion of the statement

Converse of a Conditional Statement

• A statement obtained by interchanging the positions of the hypothesis and the conclusion.
• The converse of p → q is q → p

Inverse of a Conditional Statement

• It is a statement obtained by negating both the hypothesis and the conclusion without changing their positions
• The inverse of p → q is ~p → ~q

Contrapositive

• A statement obtained by finding both the converse and inverse of the statement.
• Interchanging the positions of both hypothesis and conclusion and also taking the negation of both.
• The contrapositive of p → q is ~q → ~p

Parenthesis

• Parenthesis are useful when it comes to logical statements
• Used to prevent ambiguity in a statement
• Used to show the order of operations
• Example: p ∩ q U r could mean "(p and q) or r" or "p and (q or r)"
• Grouping with parenthesis helps clarify the intended meaning

Truth Table

• Each logical statement has a truth value which is either True (T) or False (F)
• The truth value of a compound statement can also be found and this depends on the truth values of each component statement
• The truth table of a statement is a diagram (usually arranged in rows and columns) that shows all truth values of the statement from all possible combinations of the truth values of its component statements

Truth table for Negation

• p, ~p
• T, F
• F, T

Truth table for Conjunction

• p, q, p ∩ q
• T, T, T
• T, F, F
• F, T, F
• F, F, F

Truth table for Disjunction

• p, q, p U q
• T, T, T
• T, F, T
• F, T, T
• F, F, F

Truth table for Implication

• p, q, p → q
• T, T, T
• T, F, F
• F, T, T
• F, F, T

Truth table for Bi-implication

• p, q, p → q, q → p, (p → q) ∩ (q → p)
• T, T, T, T, T
• T, F, F, T, F
• F, T, T, F, F
• F, F, T, T, T

Tautology

• A compound statement is called a tautology if its truth value is always true no matter the truth values of its components
• To know whether a statement is a tautology, its truth table should be obtained and the truth values of the last column has to be true

Contradiction

• A compound statement called a contradiction has a truth value that is always F no matter the truth values of its components
• To know whether a statement is a contradiction, its truth table should be obtained and all the truth values of the last column are false to confirm it

Logical Equivalence

• Two or more statements are equivalent if have the same truth tables.
• The last column of both truth tables of the statements should be same i.e p = q
• Therefore, the truth tables need to be obtained and compared.

Cummutative Laws

• p U q = q U p
• p ∩ q = q ∩ p

Associative Laws

• (p U q) U r = p U (q U r)
• (p ∩ q) ∩ r = p ∩ (q ∩ r)

Distributive Laws

• p U (q ∩ r) = (p U q) ∩ (p U r)
• p ∩ (q U r) = (p ∩ q) ∪ (p ∩ r)

Identity

• p U F = p
• p ∩ T = p

Complement Properties

• p U ~p = T
• p ∩ ~p = F

Double Negation

• ~(~p) = p

Idempotent Laws

• p U p = p
• p ∩ p = p

Demorgan's Laws

• ~(p U q) = ~p ∩ ~q
• ~(p ∩ q) = ~p U ~q

Universal Bound Laws (Domination)

• p U T = T
• p ∩ F = F

Absorption Laws

• p U (p ∩ q) = p
• p ∩ (p U q) = p

Quantifiers

• A predicate can be defined as a statement that contains a variable for example
• "x is greater than 5"
• "The colour of y is white"
• "x is in ND 2"
• "x and y are both numbers" etc
• A Predicate with a variable x is usually represented by P(x)
• The truth value of a predicate can only be known if the variable in the predicate is known
• Thus, the truth value of the predicate P(x) := x is less than 5 is True if x=1, but false if x=10

atomic formula

• A predicate with variable(s) is also called

Quantification

• P(x) := x is greater than 7 is not a proposition because its truth value it is unknown
• If the value of x is given, say to 10, then the above predicate becomes now proposition and also a logical statement
• Another way to convert the predicates to statement id by restricting the values of the variables to a particular set.
• For example , if set of values is limited from 10 to 15 only, then the P(x) := x is greater than 7 now becomes a true statement
• The 2nd way above is called quantification

Types of quantifiers

• Universal and existential quantifiers

Universal Quantifier

• x + x + x = 3 × x (For every number x)
• ∀x: P(x) "for each x, (the predicate) P(x) holds"

Existential Quantifiers

• x + x = 20 "there exists" or "for some" ( For example, x = 10 makes it true)
• ∃x: P(x) is the notation for "there exists an x such that the predicate P(x) holds"

Negation

• The negation of a universal quantifier is the existential quantifier, and vice versa

Scope of a Quantifier

• The formula directly following the quantifier
• The scope is the extend of the application (effect) of the quantifier
• If x is universally quantified as ∀x: (F(x) ∩ P(x))
• Then (F(x) ∩ P(x)) is a scope of the universal quantifier
• If x is existentially quantified as ∃x: F(x) → P(y)
• Then the scope is F(x)

Bound Variable

• It is a variable that is quantified in a statement
• For example in the statement ∀x: P(x) → F(y), the x is a bounded variable

Free Variable

• It is a variable that is not quantified in a statement
• For example in the statement ∀x: P(x) → F(y), the y is a free variable

Formula

• It is a statement,that consists of variables and connectives
• Has a truth value
• Can also be called a propositional expression, a sentence, or a sentential formula

Argument

• A list of statements also called the premises which can be used to arrive at the conclusion
• Every student in ND 1 does Maths
• Umar is in ND 1 (Therefore, Umar does Maths as a conclusion)
• An argument can be logically written that is in the form of premises and arriving at the conclusion

Validity of an Argument

• An argument (premises leading to conclusion) is said to be valid if the statement is a tautology
• In other words, the truth table of the statement gives True results in the last column

Permutation and Combination

• This is the third chapter in this document

Permutation

• Permutation of objects are all possible arrangements of of objects
• Key characteristic is that order is important
• A B C is one arrangement and A C B is a different one

Number Of Permutations

• A, B , C can be arranged in 6 ways

Formula Proof Statements

• N!, factorial permutation formula

Combination

• Combination of objects are all possible selections of objects
• The is the combination the order is not important
• Take four letters A, B, C and D and suppose we want to select 3 out of the four letters, then the selection can be made as follows
• АВС, АСВ, ВАС, ВСА, САВ and CBA are all counted as only 1 selection because the order is not important
• So therefore, for the selection of 3 out of the 4 letters we have only 4 selections, which are

Binomial Theorem of Algebraic Expressions

• This is the fourth Chapter

Mathematical Induction

• Way of proving things (statements, laws, theorems, formula)
• To establish things for all natural numbers
• There are three key steps

Steps For Math Induction

• Step 1: Prove that the statement/formula is true for the first number
• Step 2: Assume it is true for any number k
• Step 3: Then show that it is true for the next number after k i.e. k+1

Methods for Finding the Coefficients of a Particular Power

• Pascal's Triangle Method
• Binomial Theorem for Positive Integer Indices:
• Binomial Theorem for Negative and Fractional Indices

Application of Binomial Theorem to Approximation

• Expression like (1 + x)n can be approximated by using the first few terms for the expansion if x is sufficiently small because higher powers of x can be negligible Therefore if x is sufficiently small, the expansion of (a + x)n canhave the following approximations

Linear approximation

(a + x)n ≈ an + nan-1x

Quadratic approximation

(a + x)n ≈ an + nan-1x + n(n-1)an-2x2!

Matrices and Determinants

• This is the fifth and final chapter in this document

Matrix Definition

• A matrix is an ordered array of numbers arranged in rows and columns
• Each entry in the matrix called an element

Matrix Notation

• The subscript shows the position of the entry for example a45 mean the entry in 4th row and 5th column.

Order of a Matrix

• By convention, rows are listed first; and columns, second
• The order (or dimension) of a matrix is its dimensions represented as rows by its number of columns

Classifications of types of matrices

• Row Matrix: This is a matrix with only 1 row, for example (7 8 9)
• Column Matrix: This is a matrix with only 1 column

Types Of Matrices

Square Matrix

• This is a matrix in which its number of rows is equal to its number columns

Diagonal Matrix

• This is a square matrix in which all its entries are 0 except the leading diagonal entries

Identity Matrix:

• This is a diagonal matrix in which all its leading diagonal entries are 1

Upper Triangular Matrix:

• This is a square matrix in which all entries below its leading diagonal are 0

Lower Triangular Matrix:

• This is a square matrix in which all entries above its leading diagonal are 0

Transpose of a Matrix

• The transpose of a matrix A written as AT is obtained by changing all its rows to columns

Addition/Subtraction of Matrices

Addition/Subtraction of Matrices Rule

Only matrices with the same order or dimension can be added or subtracted