logic definitions

A set is a binary relation iff

A set is a binary relation iff

it contains only ordered pairs

A binary relation R is reflexive on a set S iff

for all elements d of S, the pair <d,d> is an element of R

A binary relation R is symmetric on a set S iff

for all elements d, e of S: if <d,e> is an element of R, then <e,d> is an element of R

A binary relation R is asymmetric on a set S iff

for no elements d, e of S: if <d,e> is an element of R and <e,d> is an element of R

A binary relation R is antisymmetric on a set S iff

for no two distinct elements d, e of S: if <d,e> is an element of R and <e,d> is an element of R

A binary relation R is transitive on a set S iff

for all all elements d, e, f of S: if <d,e> is an element of R and <e,f> is an element of R, then <d, f> is an element of R.

A binary relation R is symmetric/assymetric/antisymmetric/transitive iff

it is is symmetric/assymetric/antisymmetric/transitive on all sets

A binary relation R is an equivalence relation on S iff

R is reflexive on S, symmetric on S and transitive on S

A binary relation R is a function iff

for all d, e, f: if <d,e> is an element of R and <d,f> is an element of R, then e=f

The domain of a function R

{d : there is an e such that <d,e> is an element of R}

The range of a function R

{e : there is a d such that <d,e> is an element of R}

R is a function into set M iff

all elements of the range of the function are in M

Function notation

If d is 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 / n-place relation / relation of arity n

a set containing only n-tuples

an argument

a set of declarative sentences (premises) and a declarative sentence (conclusion) marked as the concluded sentence

An argument is logically valid iff

there is no interpretation under which the premises are all true and the conclusion is false

A set of sentences is logically consistent if

there is at least one interpretation under which all sentences of the set are true

A sentence is logically true iff

it is true under any interpretation

A sentence is a contradiction iff

it is false under all interpretations

Sentences are logically equivalent iff

they are true under exactly the same interpretations

Conditions for being an L1 sentence

(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 conventions

(i) the outer brackets may be omitted from a sentence that is not part of another sentence;

(ii) the inner set of brackets may be omitted from a sentence of the form ((φ ∧ ψ) ∧ χ) and analogously for ∨;

(iii) suppose £ ∈ {∧, ∨} and $ ∈ {→, ↔}. Then if (φ $ (ψ £ χ)) or ((φ £ ψ) $ χ) occurs as part of the sentence that is to be abbreviated, the inner set of brackets may be omitted.

An L1 structure

an assignment of exactly one truth value (T or F) to every sentence letter of L1

A sentence φ of L1 is logically true iff

φ is true in all L1 structures

A sentence φ of L1 is a contradiction iff

φ is false in all L1 structures

A sentence φ and a sentence ψ of L1 are logically equivalent iff

φ and ψ are true in exactly the same L1 structures

Let Γ be a set of sentences of L1 and φ a sentence of L1. The argument with all sentences in Γ as premisses and φ as conclusion is valid iff

there is no L1-structure in which all sentences in Γ are true and φ is false

A connective is truth-functional iff

the truth-value of the compound sentence cannot be changed by replacing a direct subsentence with another sentence having the same truth-value.

The scope of an occurrence of a connective in a sentence φ of L1

the occurrence of the smallest subsentence of φ that contains this occurrence of the connective

An English sentence is a tautology in propositional logic iff

its formalisation in propositional logic is logically true.

An English sentence is a contradiction in propositional logic iff

its formalization in propositional logic is a contradiction

A set of English sentences is consistent in propositional logic iff

the set of all their formalizations in propositional logic is semantically consistent.

An argument in English is propositionally valid iff

its formalisation in L1 is valid.

L2-structure

An L2-structure is an ordered pair <D,I> where D is some non-empty set and is a function from the set of all constants, sentence letters, and predicate letters such that:

the value of every constant is an element of D;

the value of every sentence letter is a truth value (T or F);

the value of every n-ary predicate letter is an n-ary relation.

A variable assignment over an L2-structure A

assigns an element of the domain DA of A to each variable

A sentence φ is true in an L2-structure A iff

|φ|^aA = T for all variable assignments a over A

A sentence φ of L2 is logically true iff

φ is true in all L2-structures

A sentence φ of L2 is a contradiction iff

φ is false in all L2-structures

Sentence φ and ψ of L2 are logically equivalent iff

φ and ψ are true in exactly the same L2-structures.

A set Γ of L2-setences is semantically consistent iff

there is an L2-structure A in which all sentences in Γ are true

A set of L2-sentences is semantically inconsistent iff

it is not semantically consistent

Let Γ be a set of sentences of L2 and φ a sentence of L2. The argument with all sentences in Γ as premisses and φ as conclusion is valid (Γ |= φ) iff

there is no L2 structure in which all sentences in Γ are true and φ is false

A set Γ of L2-sentences is syntactically consistent iff

there is a sentence φ such that Γ |/- φ

The scope of an occurrence of a quantifiers or a connective in a setence φ of L2

the occurrence of the smallest L2-formula that contains that occurrence of the quantifier or connective and is part of φ

An English sentence is logically true in predicate logic iff

its formalisation in predicate logic is logically true.

An English sentence is a contradiction in predicate logic iff

its formalisation in predicate logic is a contradiction

A set of English sentences is consistent in predicate logic iff

the set of their formalisations in predicate logic is semantically consistent

An argument in English is valid in predicate logic iff

its formalisation in the language L2 of predicate logic is valid

Atomic formulae of L=

(i) All atomic formulae of L2 are atomic formulae of L=;

(ii) if s and t are variables or constants then s = t is an atomic formula of L=.

Formulae of L=

(i)  All atomic formulae of L= are formulae of L=;

(ii)  If φ and ψ are formulae of L= then ¬φ, (φ∧ψ), (φ∨ψ), (φ → ψ) and (φ ↔ ψ) are formulae of L=;

(iii)  If v is a variable and φ is a formula then ∀vφ and ∃vφ are formulae of L=;

(iv)  Nothing else is a formula of L=