Logic Definitions Flashcards

1
Q

Set

A

Collection of ‘objects’, objects in the collection are elements of that set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

When are two sets identical?

A

They have the same elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Ordered pair

A

Two components with a specific and fixed order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A binary relation R is reflexive on a set S iff…

A

For all elements d of set S the pair <d,d> is an element of R (loop arrow)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

A binary relation R is symmetric on a set S iff

A

For all elementd d, e of S: if <d,e> is an element of R then <e,d> is an element of R (two way arrows)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A binary relation R is assymetric on a set S iff

A

For no elements d, e of set S: <d,e> is an element of R and <e,d> is an element of R (no two way arrows)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

A binary relation R is antisymmetric on a set S iff

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

A binary relation R is transitive on a set S iff

A

For all elements d, e, f of S: if <d, e> and <e, f> are elements of R, then <d,f> is an element of R (shortcut)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

A binary relation R is symmetric iff

A

It is symmetric on all sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

A binary relation R is asymmetric iff

A

It is asymmetric on all sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

A binary relation R is antisymmetric iff

A

It is antisymmetric on all sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A binary relation R is transitive iff

A

It is transitive on all sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A binary relation R is an equivalence relation on S iff

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Binary relation R is a function iff

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Domain of a function R

A

Is the set {d: there is an e such that <d, e> is an element of R}
Elements of the domain are inputs or arguments of the function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

The range of a function R

A

Is the set {e: there is a d such that <d, e> is an element of R}
Elements of the range are outputs or values of the function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

R is a function into the set M iff

A

All elements of the range of the function are in M

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Binary relation

A

Is a set containing only ordered pairs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Declarative sentence

A

A sentence that is true or false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Argument

A

Declarative sentences (premises) + declarative sentence (conclusion)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

An argument is logically valid iff

A

There is no interpretation under which the premisses are all true and the conclusion is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Interpretation

A

Assigning meaning to the subject-specific terms (logical terms are untouched)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Argument is propositionally valid iff

A

there is no (re-interpretation) under which the sentences in the argument such that all premisses are true and yet the conclusion is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

A set of sentences is logically consistent iff

A

There is at least one interpretation under which all sentences in the set are true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
A sentence is logically true iff
It is true under any interpretation
26
A sentence is a contradictiom iff
It is false under all interpretations
27
Sentences are logically equivalent iff
They are true under the exact same interpretations
28
Syntax
Expressions of language bare of their meanings (grammar)
29
Semantics
Meanings of the expressions of language
30
Sentence letters
P, Q, R…
31
Sentence of L1
All sentence letters are sentences of L1 If 🦄 and 🌷are sentences of L1 then their negation, conjunction, disjunction etc are sentences of L1 Nothing else is a sentence of L1 🦄 and🌷have to be replaced by sentences of L1
32
Dropping brackets
Outer brackets may be ommitted if the sentence is not part of another sentence Inner brackets may be ommitted if (1) the order does not matter or (2) and+or are stronger than if+iff
33
An L1 structure
Is an assignment of exactly one truth value to every sentence of L1
34
A sentence 🦄 of L1 is logically true iff
🦄 is true in all L1 structures (only T-s in main column)
35
A sentence 🦄 is a contradiction iff
🦄 is not true in any L1 structure (only F-s in the main column)
36
Sentences 🦄 and 🌷 are logically equivalent iff
🦄 and 🌷 are true in exactly the same L1 structures
37
Tautology
A logically true sentence
38
Let 🌵 be a set of sentences of L1 and 🦄 a sentence of L1. The argument with the 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
39
If 🦄 and all sentences of 🌵 are L1 sentences in 🌵then 🌵 I= 🦄 (🌵 logically implies 🦄 ) iff
The set containing all sentences in 🌵 and not 🦄 are inconsistent
40
An L1 structure is a counterexample to the argument which has 🌵 as a set of premisses and 🦄 as a conclusion iff
There is an L1 structure where all premisses are true but the conclusion is false
41
A set 🌵 of L1 sentences is semantically consistent iff
There is an L1 structure A such that under that structure the truth value of all sentences in 🌵 is true
42
Truth functionality (characterisation)
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 (no question marks in truth table)
43
Ambiguity
There can be multiple correct formalizations for one sentence
44
An English sentence is a tautology iff
Its formalization in propositional logic is true (iff its formalization is a tautology, its formalization is propositionally valid)
45
An English sentence is a propositional contradiction iff
Its formalization in propositional logic is a contradiction
46
A set of English sentences is propositionally consistent iff
The set of all their formalizations in propositional logic is semantically consistent
47
An argument in English is propositionally valid iff
Its formalization in L1 is valid Every propositionally valid argument is also valid but not every valid argument is propositionally valid
48
Predicate letter
All expressions of the form Pnk are predicate letters where n and k are either missing or are numerals
49
Arity
Value of the upper index of a predicate letter
50
Constants
a, b, c…
51
Variables
x, y, v
52
Atomic formulae of L2
If Z is a predicate letter of arity n and each of t1, t2…tn is a variable or constant then Zt1..tn is an atomic formula of L2
53
Quantifier
An expression Av or Ev where v is a variable
54
Formulae of L2
1) All atomic formulae of L2 are formulae of L2 2) if 💐 and 🌹 are formulae of L2 then adding conjunction, disjunction, arrow etc to them makes the new thing makes also formula of L2 3) if v is a variable and 💐 is a formula then adding a quantifier to the atomjc formula makes the new thing a formula of L2
55
Free and bound occurences of variables
1) all occurrences of variables in atomic formulae are free 2) The occurrences of a variable that are free in formulae are also free in the conjunction, disjunction etc of those formulae 3) in a formula with a quantifier no occurrence of the variable v is free, all occurrences of variables other than v that are free in the original formula are also free in the new one
56
A variable occurs freely in a formula iff
There is at least one free occurrence of the variable in the formula
57
Sentence of L2
A formula of L2 where no variable occurs freely in the formula
58
L2 structure
An L2 structure is an ordered pair (D,I) where D is some non-empty set and I is a function from a 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 and the value of every n-ary predicate letter is an n-ary relation
59
A variable assignment over an L2 structure A
Assigns an element of thr domain DA of A to each variable
60
Universal quantifier is true iff
It is true for all variable assignments beta over A differing from alpha in v at most
61
Some quantifier is true iff
It is true for at least one variable assignment beta over A differing from alpha in v at most
62
For a (L2) formula to be true
The variable(s) or constant(s) had to be members of the set of the n-ary predicate letter
63
Adequacy
Soundness (if single turnstyle then double turnstyle) + completeness (if double turnstyle then single turnstyle)
64
A set of L2 sentences is syntactically consistent iff
It is not the case that any sentence whatsoever can be proved from the premisses in the set
65
A set of sentences in L2 are semantically consistent iff
They are syntactically consistent
66
Scope of a quantifier or connective in a sentence of L2
Is the occurrence of the smallest L2 formula that contains the occurrence of the quantifier or connective and is a part of that sentence
67
Extensionality
If constants, sentence letters and predicate letters are replaced in an L2 sentence by other constants, sentence letters and predicate letters (respectively) that have the same extension in a given L2 structure then the truth-value of the sentence in that L2 structure does not change
68
Atomic formulae of L=
All atomic formulae of L2 are atomic formulae of L=. Furhtermore, if s and t are variables or constant, then s=t is an atomic formula of L=
69
Double turnstyle
Valid argument Logically implies (Syntax)
70
Single turnstile
It is provable from (Semantics)
71
Connective
Expressions that can be used to combine or modify english sentences to form a sentence