Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Prelims > Logic Definitions > Flashcards

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
Q

A sentence is logically true iff

A

It is true under any interpretation

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

A sentence is a contradictiom iff

A

It is false under all interpretations

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

Sentences are logically equivalent iff

A

They are true under the exact same interpretations

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

Syntax

A

Expressions of language bare of their meanings (grammar)

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

Semantics

A

Meanings of the expressions of language

30
Q

Sentence letters

A

P, Q, R…

31
Q

Sentence of L1

A

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
Q

Dropping brackets

A

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
Q

An L1 structure

A

Is an assignment of exactly one truth value to every sentence of L1

34
Q

A sentence 🦄 of L1 is logically true iff

A

🦄 is true in all L1 structures (only T-s in main column)

35
Q

A sentence 🦄 is a contradiction iff

A

🦄 is not true in any L1 structure (only F-s in the main column)

36
Q

Sentences 🦄 and 🌷 are logically equivalent iff

A

🦄 and 🌷 are true in exactly the same L1 structures

37
Q

Tautology

A

A logically true sentence

38
Q

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

A

There is no L1 structure in which all sentences in 🌵 are true and 🦄 is false

39
Q

If 🦄 and all sentences of 🌵 are L1 sentences in 🌵then
🌵 I= 🦄 (🌵 logically implies 🦄 ) iff

A

The set containing all sentences in 🌵 and not 🦄 are inconsistent

40
Q

An L1 structure is a counterexample to the argument which has 🌵 as a set of premisses and 🦄 as a conclusion iff

A

There is an L1 structure where all premisses are true but the conclusion is false

41
Q

A set 🌵 of L1 sentences is semantically consistent iff

A

There is an L1 structure A such that under that structure the truth value of all sentences in 🌵 is true

42
Q

Truth functionality (characterisation)

A

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
Q

Ambiguity

A

There can be multiple correct formalizations for one sentence

44
Q

An English sentence is a tautology iff

A

Its formalization in propositional logic is true (iff its formalization is a tautology, its formalization is propositionally valid)

45
Q

An English sentence is a propositional contradiction iff

A

Its formalization in propositional logic is a contradiction

46
Q

A set of English sentences is propositionally consistent iff

A

The set of all their formalizations in propositional logic is semantically consistent

47
Q

An argument in English is propositionally valid iff

A

Its formalization in L1 is valid
Every propositionally valid argument is also valid but not every valid argument is propositionally valid

48
Q

Predicate letter

A

All expressions of the form Pnk are predicate letters where n and k are either missing or are numerals

49
Q

Arity

A

Value of the upper index of a predicate letter

50
Q

Constants

A

a, b, c…

51
Q

Variables

A

x, y, v

52
Q

Atomic formulae of L2

A

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
Q

Quantifier

A

An expression Av or Ev where v is a variable

54
Q

Formulae of L2

A

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
Q

Free and bound occurences of variables

A

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
Q

A variable occurs freely in a formula iff

A

There is at least one free occurrence of the variable in the formula

57
Q

Sentence of L2

A

A formula of L2 where no variable occurs freely in the formula

58
Q

L2 structure

A

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
Q

A variable assignment over an L2 structure A

A

Assigns an element of thr domain DA of A to each variable

60
Q

Universal quantifier is true iff

A

It is true for all variable assignments beta over A differing from alpha in v at most

61
Q

Some quantifier is true iff

A

It is true for at least one variable assignment beta over A differing from alpha in v at most

62
Q

For a (L2) formula to be true

A

The variable(s) or constant(s) had to be members of the set of the n-ary predicate letter

63
Q

Adequacy

A

Soundness (if single turnstyle then double turnstyle) + completeness (if double turnstyle then single turnstyle)

64
Q

A set of L2 sentences is syntactically consistent iff

A

It is not the case that any sentence whatsoever can be proved from the premisses in the set

65
Q

A set of sentences in L2 are semantically consistent iff

A

They are syntactically consistent

66
Q

Scope of a quantifier or connective in a sentence of L2

A

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
Q

Extensionality

A

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
Q

Atomic formulae of L=

A

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
Q

Double turnstyle

A

Valid argument
Logically implies
(Syntax)

70
Q

Single turnstile

A

It is provable from
(Semantics)

71
Q

Connective

A

Expressions that can be used to combine or modify english sentences to form a sentence

Prelims (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions