Logic Volker Definitions Flashcards
(74 cards)
Binary relation
A set is a binary relation iff it contains only ordered pairs.
Binary Relation: Reflective
reflective on a set S iff for all elements d of S the pair ⟨d, d⟩is an element of R
Binary Relation: Symmetric
symmetric on a set S iff for all elements d, e of S: if ⟨d, e⟩∈R then ⟨e, d⟩∈R
Binary Relation: Asymmetric
asymmetric on a set S iff for no elements d, e of S: ⟨d, e⟩∈R and ⟨e, d⟩∈R
Binary Relation: Antisymmetric
antisymmetric on a set S iff for no two distinct elements d, e of S: ⟨d, e⟩∈Rand ⟨e, d⟩∈R
Binary Relation: Transitive
transitive on a set S iff for all elements d, e, f of S: if ⟨d, e⟩∈R and ⟨e, f⟩∈R, then ⟨d, f⟩∈R.
Equivalence relation
A binary relation Ris an equivalence relation on S iff R is reflexive on S, symmetric on S and transitive on S
Function
A binary relation R is a function iff for all d, e, f: if ⟨d, e⟩∈R and ⟨d, f⟩∈R then e= f
Domain
The domain of a function R is the set {d : there is an e such that ⟨d, e⟩∈R}
range
The range of a function R is the set {e : there is a d such that ⟨d, e⟩∈R}
Function into a set
R is a function into the set M iff all elements of the range of the function are in M
Function notation
If dis in the domain of a function R one writes R(d) for the unique object e such that ⟨d, e⟩is in R
n-ary relation
An n-place relation is a set containing only n-tuples. An n-place relation is called
a relation of arity n
Argument
An argument consists of a set of declarative sentences (the premises) and a declarative sentence (the conclusion) marked as the concluded sentence
Logical validity
An argument is logically valid iff there is no interpretation under which the premises are all true and the conclusion false
Consistency
A set of sentences is logically consistent iff there is at least one interpretation under
which all sentences of the set are true
Logical truth
A sentence is logically true iff it is true under any interpretation.
Contradiction
A sentence is a contradiction iff it is false under all interpretations.
Logical equivalence
Sentences are logically equivalent iff they are true under exactly the same
interpretations.
Sentence letters
P, Q, R, P1, Q1, R1, P2, Q2, R2 and so on are sentence letters
Sentence of L1
(i) All sentence letters are sentences of L1.
(ii) If φ and ψ are sentences of L1, then¬φ, (φ∧ψ), (φ∨ψ), (φ→ψ) and (φ↔ψ) are sentences of L1.
(iii) Nothing else is a sentence of L1.
Bracketing Convention
1 The outer brackets may be omitted from a sentence that is not part of another sentence.
2 The inner set of brackets may be omitted from a sentence of the form ((φ∧ψ) ∧χ) and
analgously for ∨.
3 Suppose ⋄∈{∧, ∨}and ◦∈{→, ↔}. Then if (φ◦(ψ⋄χ)) or ((φ⋄ψ)◦χ) occurs as part of
the sentence that is to be abbreviated, the inner set of brackets may be omitted.
L1-structure
An L1-structure is an assignment of exactly one truth-value (T or F) to every
sentence letter of L1
Truth in an L1-structure
Let A be some L1-structure. Then |…|A assigns either T or F to
every sentence of L1 in the following way.
(i) If φ is a sentence letter, |φ|A is the truth-value assigned to φ by the L1-structure A
(ii) |¬φ|A = T iff |φ|A = F
(iii) |φ∧ψ|A = T iff |φ|A = T and |ψ|A = T
(iv) |φ∨ψ|A = T iff |φ|A = T or |ψ|A = T
(v) |φ→ψ|A = T iff |φ|A = F or |ψ|A = T
(vi) |φ↔ψ|A = T iff |φ|A = |ψ|A
