Linear Algebra: Logic
Discrete Mathematics: propositions, tautologies, contradictions, and/or/xor, logical equivalences, proofs. Proof by induction, proof by contradiction. Links: laws of logic (associative, commutative, de morgan's)
52 flashcards · Mathematics · by lakesare
How is statement that is either TRUE or FALSE called?
A proposition. "Two plus two equals four" is a proposition, and it's true. "x + y > 0" is not a proposition because for some values of x and y the sentence is true, whereas for others it is false.
Proposition that's always true? Proposition that's always false?
always true: tautology always false: contradiction
Show that proposition: p ∨ ∼p is a tautology p ∧ ∼p is a contradiction
Prove ∼(∼p ∧ q) ∧ (p ∨ q) ≡ p.
When is a XOR b true?
When either a or b is true - but not both.
Write a XOR b by means of ∧ and ∨.
a XOR b = (~a ∧ b) ∨ (a ∧ ~b)
Simplify all (those are considered axioms, however not parsimoniuous): a ∨ (a ∧ b) a ∨ 0 a ∧ 1 a ∨ (b ∧ c) a ∨ ¬a a ∧ ¬a
a ∨ (a ∧ b) = a a ∨ 0 = a a ∧ 1 = a a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∨ ¬a = 1 a ∧ ¬a = 0
Solve: a XOR a (XOR is also sometimes denoted as ^)
a XOR a = (!a && a) || (a && !a) = 0.
Shakespeare wrote: “Neither a borrower nor a lender be,” Say it simpler.
“Do not be a borrower and do not be a lender.”
Write each of the following sentences symbolically, letting h = “It is hot”, and s = “It is sunny.” It is not hot but it is sunny. It is neither hot nor sunny.
!h ∧ s !h ∧ !s
Name signs for conjunction and disjunction.
conjunction: ∧ disjunction: ∨
Is ∨ inclusive or exclusive?
∨ is meant in the inclusive sense: p, or q, or both The symbol ∨ comes from the Latin word vel, which means or in its inclusive sense.
What is inclusive and exclusive or?
In ordinary language or is sometimes used in an exclusive sense (p or q but not both), and sometimes in an inclusive sense (p or q or both). ∨ is meant in the inclusive sense.
When are two statement forms logically equivalent (≡)?
If, and only if, they have identical truth values in a truth table for each possible substitution of statements for their statement variables.
Negate: John is 6 feet tall and he weighs at least 200 pounds.
John is NOT 6 feet tall OR he does NOT weigh at least 200 pounds.
Negate: The bus was late or Tom’s watch was slow
The bus was NOT late AND Tom’s watch was NOT slow
Use De Morgan’s laws to write the negation of −1 < x ≤ 4.
!((-1 < x) AND (x < 4 OR x = 4)) !(-1 < x) OR !(x < 4 OR x = 4) (-1 >= x) OR (!(x < 4) AND (x != 4)) (-1 >= x) OR (x >= 4 AND x != 4) (-1 >= x) OR (x > 4) x <= -1 OR x > 4
Conditional statement has the form of: hypothesis -> conclusion. Under what circumstances can it be considered false?
The only combination of circumstances in which you would call a conditional sentence false occurs when the hypothesis is true AND the conclusion is false.
Construct a truth table for p → q:
What's a vacuously true conditional statement?
A conditional statement that is truy by the virtue of its hypothesis being false, for example: If 0 = 1 then 1 = 2. A conditional statement that is true by virtue of the fact that its hypothesis is false is often called vacuously true or true by default. Thus the statement “If you show up for work Monday morning, then you will get the job” is vacuously true if you do not show up for work Monday morning. In general, when the “if” part of an if-then statement is false, the statement as a whole is…
Either you get to work on time or you are fired. Rewrite this sentence in 2 symbolic forms, where: p is 'you get to work on time' q is 'you are fired'
!p → q p ∨ q These are equivalent. p → q ≡ ∼p ∨ q.
∼(p → q) ≡ rewrite using ANDs and ORs
∼(p → q) ≡ p ∧ ∼q By definition, p → q is false if, and only if, its hypothesis, p, is true and its conclusion, q, is false. It follows that: The negation of “if p then q” is logically equivalent to “p and not q.”
Write negations for each of the following statements: If my car is in the repair shop, then I cannot get to class. If Sara lives in Athens, then she lives in Greece.
My car is in the repair shop, AND I CAN get to class Sara lives in Athens, AND she does NOT live in Greece
What's a contrapositive?
In a conditional statement: switching the hypothesis and conclusion negating both. A conditional statement is logically equivalent to its contrapositive.
Give the contrapositive of "If it is raining then the grass is wet".
"If the grass is not wet then it is not raining."
How to construct a truth table for p -> q e.g.?
theory statement: it's raining -> grass is wet but in real world: p q p -> q T T T (=> if it's indeed raining, and grass is indeed wet - then this statement was true) T F F (=> if it's indeed raining, but grass is NOT wet - then this statement was false) So the truth table means 'actual value the statement would acquire if p/q are true or false'.
Give an example of a statement.
2 + 2 = 4 (true statement) A statement (or proposition) is a sentence that is true or false but not both.
Rewrite p only if q into a conditional statement.
!q → !p, or: p → q
Rewrite p iff q into a conditional statement.
p if q AND p only if q, or: q → p AND p → q, or: p ↔ q
Construct a truth table for p ↔ q:
T F F T
Parent says: “You will get dessert only if you eat your dinner.” What do they mean in math speak?
They mean “You will get dessert if and only if you eat your dinner.”. They do guarantee that: you eat -> you get desert, they just don't mention it.
“R is a sufficient condition for S” means “if _____ then _____.”
if R then S.
“R is a necessary condition for S” means “if _____ then _____.”
if !R then !S => if S then R.
“R only if S” means “if _____ then _____.”
“R only if S” means S is a necessary condition for R, => if !S then !R => if R then S.
Proposition VS proposition form?
Proposition form is made up of proposition variables (such as p, q, and r) and logical connectives (such as ∼, ∧, and ∨) that becomes a proposition when actual statements are substituted for the component statement variables. The truth table for a given proposition form displays the truth values that correspond to all possible combinations of truth values for its component statement variables.
When is argument form considered valid? (premises ∴ conclusion)
Only when if the premises are all true, conclusion is also true. To say that an argument form is valid means that no matter what particular statements are substituted for the statement variables in its premises, if the resulting premises are all true, then the conclusion is also true.
Is this argument form valid? p → q ∨ ∼r q → p ∧ r ∴ p → r
What's syllogism?
An argument form consisting of two premises and a conclusion. An instance of a form of reasoning in which a conclusion is drawn from two given or assumed propositions (premises);
Explain 2 forms of syllogism, modus ponens (method of affirming) modus tollens (method of denying)
modus ponens If p then q. p ∴ q modus tollens If p then q. ∼q ∴ ∼p
p ∨ q; ∼q ∴ ___ p ∨ q; p → r; q → r ∴ ___
p ∨ q; ∼q ∴ p p ∨ q; p → r; q → r ∴ r
How are symbols ∀ and ∃ read?
∀ - for all ∃ - there exists
Negate: ∀ people p, if p is blond then p has blue eyes. ∀ x in D, ∃ y in E such that P(x, y). ∃ x in D such that ∀ y in E, P(x, y).
∃ person p, p is blond AND p doesn't have blue eyes ∃ x in D such that ∀ y in E, ∼P(x, y) ∀ x in D, ∃ y in E such that ∼P(x, y)
The reciprocal of a real number a is a real number b such that ab = 1. The following two statements are true. Rewrite them formally using quantifiers and variables: Every nonzero real number has a reciprocal. There is a real number with no reciprocal.
∀ nonzero real numbers u, ∃ a real number v such that uv = 1. ∃ a real number c such that ∀ real numbers d, cd != 1.
Write a definition of a limit of a function an.
Given any positive number ε, we can find an integer N such that whenever n is larger than N, the number an sits between L − ε and L + ε on the number line. Symbolically: ∀ε > 0, ∃ an integer N such that ∀ integers n, if n > N then L − ε < a(n) < L + ε.
Rewrite statements formally using quantifiers (∀, ∃) and variables (x, y): Everybody loves somebody. Somebody loves everybody.
∀ people x, ∃ a person y such that x loves y. ∃ a person x such that ∀ people y, x loves y.
What is: constructive proof of existence VS nonconstructive proof of existence?
Proof of existence: ∃x ∈ D such that Q(x) constructive proof: find an x that makes Q(x) true nonconstructive proof: a) prove that existence of x is guaranteed by an axiom b) prove that assumption that there is no such x leads to a contradiction The disadvantage of a nonconstructive proof is that it may give virtually no clue about where or how x may be found. The widespread use of digital computers in recent years has led to some dissatisfaction with this aspect of nonconstructive proofs and to…
Construct a Boolean expression for this truth table:
(P ∧ Q ∧ R) ∨ (P ∧ ∼Q ∧ R) ∨ (P ∧ ∼Q ∧ ∼R) For each row with 1 as the output (in this case, 1, 2, 4 rows), construct an AND expression: that produces a 1 for the exact combination of input values for that row, and a 0 for all other combinations of input values. For example, the expression for the first row is P ∧ Q ∧ R because P ∧ Q ∧ R is 1 if P = 1 and Q = 1 and R = 1, and it is 0 for all other values of P, Q, and R. The expression for the third row is P ∧ ∼Q ∧ R because P ∧ ∼Q ∧ R is 1 if P…
What is another name for a disjunctive normal form?
Sum-of-products form.
Give an example of a boolean expression in a disjunctive normal form.
Formulas in DNF: (A and !B and !C) or (!D and F) (A and B) or C A and B A Formulas not in DNF: !(A or B), since an OR is nested within a NOT A or (B and (C or D)), since an OR is nested within an AND All logical formulas can be converted into an equivalent disjunctive normal form.
What are NAND and NOR gates?
NAND: AND-gate, followed by a NOT-gate. NOR: OR-gate, followed by a NOT-gate.
Find a Boolean expression that corresponds to this circuit:
(P ∧ ∼Q) ∨ R
Construct a circuit for this truth table:
First we find a disjunctive normal form (sub of products form): And then we construct a truth table: