Unit 1: Logic Flashcards
Define
Proposition
A proposition is:
a declarative sentence
(a sentence that declares a fact),
that is either true or false, but not both.
Define
Negation
The negation of p, denoted by ¬p, is the statement:
it is not the case that p
Define
Conjunction
The conjunction of p and q, denoted by ** p ∧ q**, is the proposition:
p and q
The conjuction p ∧ q is true when both p and q are true, and false otherwise.
Define
Disjunction
The disjunction of p and q, denoted by p ∨ q, is the proposition:
p or q
The disjunction p ∨ q is false when both p and q are false and true otherwise.
Define
Implication
The implication p → q, is the proposition:
if p then q
p → q is false when p is true and q is false, and true otherwise.
The implication, p is callsed the hypothesis.
And q is called the conclusion
Define
Converse
The proposition q → p is called the converse of p → q
Define
Contrapositive
The contrapositive of p → q is:
¬q → ¬p
Define
Biconditional statement
The biconditional statement p ↔ q, is the proposition:
p if and only if q
The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise.
Precedence of logical operators
¬-
∧and∨ -
→and↔
Define
(propositional) formula
A proposition or a compound proposition.
Define
Truth assignment
A truth assignment to a propositional formula is an assignment of truth values to each of the propositions that occur in the formula.
Define
Tautology
A formula that is true under every truth assignment.
Define
Logical equivalence
Formulats that have the same truth values under all possible truth assignments are called logically equivalent.
Defined:
Formulas p and q are logically equivalent, if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
The symbol ⇐⇒ is sometimes used instead of ≡ to denote logical equivalence.
Idempotent laws
(p ∧ p) ≡ p
(p ∨ p) ≡ p
Commutative laws
(p ∧ q) ≡ (q ∧ p)
(p ∨ q) ≡ (q ∨ p)
Associative laws
(logic)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Absorption laws
(logic)
p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p
Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Double negation
¬¬p ≡ p
De Morgan’s laws
¬(p ∧ q) ≡ (¬p ∨ ¬q)
¬(p ∨ q) ≡ (¬p ∧ ¬q)
Tertium non datur
(p ∧ ¬p) ≡ F
(p ∨ ¬p) ≡ T
Identity laws
(p ∧ T) ≡ p
(p ∨ F) ≡ p
Domination laws
(p ∨ T) ≡ T
(p ∧ F) ≡ F
Subject & Predicate
“x is greater than 3” has 2 parts:
- The first part, x, is the subject of the statement.
- The second part, the predicate, is greater than 3 refers to a property that the subject of the statement may or may not have.
Define
Universal Quantification
The universal quantification of P(x) is the statement:
P(x) for all values of x in the domain of x
- The notation
∀x P(x)denotes the universal quantification ofP(x). - The symbol
∀is called the universal quantifier.
Define
Existential Quantification
The existential quantification of P(x) is the statement:
There exists an element x in the domain such that P(x)
- The notation
∃x P(x)denotes the existential quantification ofP(x). - The symbol
∃is called the existential quantifier.
Define
Set
A set is an unordered collection of objects, called elements or members of the set.
A set is said to contain its elements.
x ∈ A denotes that x is an element of the set A.x ∈/ A denotes that x is not an element of the set A.
3 Fundamental Set Properties
- All elements in a set are distinct. (i.e. a value is either an element of a set, or it is not. It cannot occur multiple times in the set.)
- The elements of a set do not come with a fixed ordering.
- The same set can be described in different ways {1, 2, 3} = {1, 2, 2, 3} = {3, 1, 2} = {i | i integer, 0 < i ≤ 3}
6 Standard sets of numbers
N := {0,1,2,3,···} set of natural numbers
Z := {0,1,−1,2,−2,3,−3,···} set of integers
Z>0 := {1, 2, 3, · · · } set of positive natural numbers
Q := {ab | a,b ∈ Z,b ̸= 0} set of rational numbers
R := the set of real numbers
R>0 := the set of positive real numbers
Definition
Set equality
Two sets A and B are equal (A=B), if they contain the same elements, i.e.
- every x ∈ A satisfies x ∈ B and
- every x ∈ B satisfies x ∈ A.
Definition
Empty set
The empty set is the (uniquely determined) set that contains no element(s).
We denote it by ∅, or by {}.
Definition
Singleton set
A set with exactly one element.
Definition
Finite set
A set is called finite, if it contains only finitely many elements, i.e. if there is a number n ∈ N, such that the set contains exactly n elements.
Define
Cardinality
The cardinality of a set M is:
|M|: {
The number if elements in M, if M is finite,
∞, otherwise
Define
Subset
A is a subset of B
(short: A⊆B),
if every element of A is also an element of B.
Define
Proper Subset
A is a proper subset of B (short: A ⊊ B), if:A ⊆ B and A ≠ B.
Superset
A is a superset of B (short: A ⊇ B), if B ⊆ A
Proper Superset
A is a proper superset of B
(short: A ⊋ B), if
A ⊇ B and A ≠ B.
Define
Power set
The power set of a set S is the set of all subsets of S:
P(S) := { X |X ⊆ S}
E.g. P({a, b}) = { ∅, {a}, {b}, {a,b} }
Set operations
Intersection
A ∩ B := { x : x ∈ A and x ∈ B }
Set operations
Union
A ∪ B := { x : x ∈ A or x ∈ B }
Set operations
Difference
A − B := { x ∈ A : x ∉ B }
Set operations
Symmetric difference
A ⊕ B := (A−B) ∪ (B−A)
Complement of a set
We would like the complement of a set A, short A^, to be the set of all elements, that do not belong to A.
A^ := { x : x ∉ A},
Sets
Idempotent laws
A ∩ A = A and A ∪ A = A
Sets
Commutative laws
A ∩ B = B ∩ A and A ∪ B = B ∪ A
Sets
Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
and A ∪ (B ∪ C) = (A ∪ B) ∪ C
Sets
Absorption laws
A ∩ (A ∪ B) = A
andA ∪ (A ∩ B) = A
Sets
Distributive laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Sets
Double Complement
(A^)^ = A
De Morgan’s laws
(sets)
(A ∩ B)^ = A^ ∪ B^
and (A ∪ B)^ =A^ ∩ B^
Inverse laws
A ∩ A^ = ∅ and A ∪ A^ = U
Identity laws
A ∩ U = A and A ∪ ∅ = A
Cartesian product of two sets
A x B is the set of ordered pairs (a, b), where a belongs to A and b belongs to B.
A×B := { (a,b) | a ∈ A and b ∈ B }
Symmetric relation
A relation R on set A is called symmetric, if (a, b) ∈ R implies (b, a) ∈ R for all a, b ∈ A
Antisymmetric relation
A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a=b is called antisymmetric.
Properties of relations
transitive
A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R, for all a,b,c ∈ A.
Properties of relations
total
A relation R on a set A is called total if all a,b ∈ A satisfy: (a,b) ∈ R or (b, a) ∈ R.
Definition
Function
Let A and B be nonempty sets.
A function f from A to B is an assignment of exactly one element of B to each element of A.
f : A → B
Domain & Codomain
Let f : A → B be a function.
The set A is called the domain of the function f.B is called the codomain of the function f.
Image & Preimage
If f(a) = b, we say that:
b is the image of a,
and a is the preimage of b.
Definition
Injective function
A function f : A → B is said to be injective (or one-to-one), if and only if f(a) = f(b) implies that a = b for all a and b in the domain A of f.
Definition
Surjective function
A function f : A → B is said to be surjective (or onto), if and only if for every element b ∈ B there is an element a ∈ A with f(a) = b.
Definition
Bijective function
A function f is said to be bijective (or a one-to-one correspondence), if it is both injective and surjective.
We also say that the function is a bijection.
Definition
Inverse function
Let A, B be sets and f ⊆ A × B be a function.
If the relation{(b, a) | (a, b) ∈ f } ⊆ B × A is a function from B to A, then it is called the inverse function of f.
In this case, f is called invertible.
Definition
theorem
A theorem is a statement that can be shown to be true.
A theorem consists of assumptions (premises) and a conclusion.
Assumptions and a
conclusion are statements such that the following is true:
If all assumptions are satisfied, then the conclusion must be true.
Definition
proof
The proof of a theorem has to establish that the statement of the theorem is true.
The proof can use:
* the assumptions of the theorem
* definitions, known facts and known theorems
* statements, that are proved within the proof or have already been proved elsewhere
* logical rules of inference.
Definition
lemma
A less important theorem that is helpful in the proof of other results is often called a lemma.
Definition
corollary
A corollary is a theorem that follows immediately from a theorem or proposition that has been proved.
Definition
conjecture
A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, but a proof is still missing.
Proof by contraposition
In a proof by contraposition, a statement of the form p → q is proved by showing ¬q → ¬p.
This is correct, because the statements are logically equivalent.
Propose-and-reject algorithm
Gale-Shapley 1962
Initialize each person to be free;
while some man is free and has not proposed to every woman do
* choose such a man m;
* w ← 1st woman on m’s list to whom m has not yet proposed;
* if w is free then
* assign m to w;
* else if w prefers m to her fiance m′ then
* assign m to w, and m′ to be free;
* else
* w rejects m;
Equivalence relation
A binary relation that is:
- Reflexive
- Transitive
- Symmetric
Equivalence class
Let E be an equivalence relation over a set V.
For every v ∈ V we let:
[v]E := {v' ∈ V | (v, v') ∈ E }
denote the equivalence class of v with respect to E.
A set W ⊆ V is an equivalence class (of E) if there exists an element v ∈ V with W = [v]E.
The element v is then called a representative of its equivalence class W.
Preorder
Let E be a binary relation over a set V.
E is a preorder, if e is:
- Reflexive, and
- Transitive
Partial order
Let E be a binary relation over a set V.
E is a partial order, if E is:
- reflexive,
- transitive, and
- antisymmetric
Linear order
or
Total order
Let E be a binary relation over a set V.
E is a linear order or total order, if E is:
- reflexive,
- transitive,
- antisymmetric, and
- total.
Example of a linear order
≤ is a linear order on N (and Z, Q and R).
≥ is a linear order on N (and Z, Q and R).
Example of a partial order
For every set M, the relations ⊆ and ⊇ are partial orders on the power set P(M).
Real-valued / integer-valued function
A function is called real-valued if its codomain is the set of real numbers.
It is called integer-valued if its codomain is the set of integers.
Identity function
The identity function on A is the function A→A, given by ιA(x) := x for all x∈A
ι is a greek letter, pronounced ‘iota’
Direct proof
In a direct proof, the statement is proven ‘directly’, i.e. without any detours.
This is often by a chain of implications, leading us from the assumptions of the theorem to its conclusion;
or by a chain of equalities,
or a chain of equivalences.
Proof by contradiction
Suppose we want to show a statement of the form p is true.
Suppose we find a contradiction q such that ~p→q.
Because q is false, but ~p→q is true, we can conclude that ~p is false, which means p is true.
Proof by mathematical induction
**By N we denote the set of all natural numbers.
Let P(n) be a statement about a natural number n.
The aim is to prove that statement P(n) is true for every n ∈ N.
- In the first step, we prove that the statement
P(n)is true forn=0. We call this step basis of the induction. - In a second step, we prove for every natural number
n∈N: If statementP(n)is true, then statementP(n+1)is true as well. This step is called the inductive step.
