Brainscape's Knowledge GenomeTM

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


See full index

logic > logic notes > Flashcards

logic notes Flashcards

1
Q

¬

A

not, negation

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

not

A

¬

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

∧

A

And, conjunction

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

and

A

∧

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

conjunction

A

∧

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

negation

A

¬

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

∨

A

or, disjunction

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

or

A

∨

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

disjunction

A

∨

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

→

A

if … then, implication

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

if … then

A

→

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

implication

A

→

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

↔

A

if and only if, iff, equivalence

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

if and only if

A

↔

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

equivalence

A

↔

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

not premise p

A

_

p

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

_

p

A

not premise p

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

He has an Ace if he does not have a Knight or a Spade

A

¬(k ∨ s) → a
or
(¬k ∨ s) → a

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

exclusive disjunction

A

⊕

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

⊕

A

exclusive disjunction

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

define the Language of propositional logic

A

Let P be a set of proposition letters and let p ∈ P

ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ → ϕ) | (ϕ ↔ ϕ)

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

syllogism

A

a logical argument where a quantified statement of a specific form (the conclusion) is inferred from two other quantified statements (the premises).

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

4 corners of Square of Opposition

A

All A are B
……..No A are B

Some A are B
……..Not all A are B

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

syllogistic Q N V

A

Q: quantifier
N: noun
V: verb

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

well known tautologies

A

Double Negation
De Morgan laws
Distribution laws

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

Double Negation

A

¬¬ϕ ↔ ϕ

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

De Morgan laws

A

¬(ϕ ∨ ψ) ↔ (¬ϕ ∧ ¬ψ)

¬(ϕ ∧ ψ) ↔ (¬ϕ ∨ ¬ψ)

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

Distribution laws

A

(ϕ ∧ (ψ ∨ χ)) ↔ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ))

ϕ ∨ (ψ ∧ χ)) ↔ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)

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

aristotals inference pattern as human language

A

Q=Quantifier
NP = noun phrase
CN = Common Noun
VP = verb phrase (Q + CN)

Q1 CN1 VP1
Q2 CN2 VP2
__________
Q3 CN3 VP3

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

syllogistic form

A

2 predicates and a conclusion

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

middle term

A

the missing class that is in the predicates but not the conclusion

For all A then B
For all B then C
____________
for all A then C

the middle term is B

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

∈

A

“is an element of” operation

member of operation

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

a is an element of a set A

A

a ∈ A

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

a ∈ A

A

a is an element of a set A

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

a is not an element of a set A

A

a ∉ A

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

a ∉ A

A

a is not an element of a set A

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

the set of those x that have the property described by ϕ.

A

{x | ϕ(x)}

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

the set of all those x in U for which ϕ holds

A

{x ∈ U | ϕ(x)}

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

a set of elements sharing multiple properties ϕ1, . . . , ϕn

A

{x | ϕ1(x), . . . , ϕn(x)}

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

(Bill Clinton, Hillary Clinton) ∈ A

, (Hillary Clinton,Bill Clinton) ∉ A

A

A = {(x, y) | x is in the list of presidents of the US , y is married to x}

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

A ∩ B

A

intersection

{x | x ∈ A and x ∈ B}

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

{x | x ∈ A and x ∈ B}

A

A ∩ B

intersection

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

intersection

A

A ∩ B

{x | x ∈ A and x ∈ B}

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

A ∪ B

A

union

{x | x ∈ A or x ∈ B}

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

{x | x ∈ A or x ∈ B}

A

union

A ∪ B

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

union

A

A ∪ B

{x | x ∈ A or x ∈ B}

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

A \ B (set)

A

difference

{x | x ∈ A and x ∉ B}

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

{x | x ∈ A and x ∉ B}

A

difference

A \ B

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

difference (set)

A

A \ B

{x | x ∈ A and x ∉ B}

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

complement (set)

A

_
A

{x ∈ U | x ∉ A}

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

{x ∈ U | x ∉ A}

A

complement
_
A

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

_

A

A

complement

{x ∈ U | x ∉ A}

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

_

A ∩ B

A

A \ B

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

_
_
A

A

A

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

de morgans law (in set operations)

A

______
A ∪ B = A ∩ B
______
A ∩ B = A ∪ B

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

distributive equations (in set operations)

A

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

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

definition of a union of 2 sets (using negatives)

A

______
__ __
A ∪ B = A ∪ B = A ∩ B

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

number of predicate forms in a sylogism

A

3

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

venn diagram inference steps

A

1) draw skeleton
2) Universal step - cross out All and No
3) Existential step - ◦ in Some and Not all (where not removed by Universal step)
4) Check conclustion, if existential and universal are where they are meant to be then valid, otherwise a counter argument can exist

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

A syllogism with only universal premises and an existential conclusion is
always invalid, because ..

A

the situation with all classes empty is a counterexample

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

predicate logic is the most important system in logic because …

A

it is a universal language for talking about structure

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

a,b,c (predicate) are ..

A

constant / proper names

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

x,y,z (predicate) are …

A

variable / indefinite names

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

A,B,C (predicate) are …

A

predicate letters

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

1-place predicate

A

a predicate with 1 argument , e.g. intransitive verbs (walk) common nouns (boy)

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

2-place predicate

A

a predicate with 2 arguments - transitive verbs (see)

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

3-place predicate

A

a predicate with 3 arguments - distributive verbs (give(

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

unary predicates

A

1-place predicates

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

binary predicates

A

2-place predicates

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

ternary predicates

A

3-place predicates

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

sentence combination operators (predicate)

A

¬, ∧, ∨, →, ↔,∀x,∃x

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

∃x

A

Existential operator - “there exists an x”

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

“there exists an x”

A

∃x

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

Existential operator

A

∃x

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

∀x

A

universal operator - “for all x”

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

universal operator

A

∀x

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

“for all x”

A

∀x

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

natural language:John walks

A

W j

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

natural language:John is a boy

A

B j

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

natural language:He walks

A

W x

81
Q

natural language:John sees Mary

A

S jm

82
Q

natural language:John gives Mary the book

A

G jmb

83
Q

an atomic statements …

A

express basic properties of one or more objects together

84
Q

natural language: John sees her

A

Sjx

85
Q

natural language: He sees her

A

Syx

86
Q

natural language: This is less than that

A

x < y

87
Q

natural language: He sees himself

A

Sxx

88
Q

natural language: John does not see Mary

A

¬Sjm

89
Q

natural language: Three is not less than two

A

¬3 < 2, or abbreviated: 3 ≮ 2.

90
Q

natural language: John sees Mary or Paula

A

Sjm ∨ Sjp

91
Q

natural language: Three is less than three or three is less than four

A

3 < 3 ∨ 3 < 4

92
Q

natural language: x is odd (i.e., two does not divide x)

A

¬(2|x)

93
Q

natural language: If John sees Mary, he is happy

A

Sjm → Hj

94
Q

natural language: Someone walks

A

∃xW x

95
Q

natural language: Some boy walks

A

∃x(Bx ∧ W x)

96
Q

natural language: A boy walks

A

∃x(Bx ∧ W x)

97
Q

natural language: John sees a girl

A

∃x(Gx ∧ Sjx)

98
Q

natural language: A girl sees John

A

∃x(Gx ∧ Sxj)

99
Q

natural language: A girl sees herself

A

∃x(Gx ∧ Sxx)

100
Q

natural language: Everyone walks

A

∀xW x

101
Q

natural language: Every boy walks

A

∀x(Bx → W x)

102
Q

natural language: Every girl sees Mary

A

∀x(Gx → Sxm)

103
Q

natural language: Everyone sees someone

A

∀x∃ySxy

104
Q

natural language: Someone sees everyone

A

∃x∀ySxy

105
Q

natural language: Everyone is seen by someone

A

∀x∃ySyx

106
Q

natural language: Someone is seen by everyone

A

∃x∀ySyx

107
Q

domain of discourse

A

quantifiers range over all objects in some given set of relevant objects

108
Q

All A are B

A

∀x(Ax → Bx)

109
Q

No A are B

A

¬∃x(Ax ∧ Bx)

110
Q

Some A are B

A

∃x(Ax ∧ Bx)

111
Q

Not all A are B

A

¬∀x(Ax → Bx)

112
Q

translate in steps:

Every boy loves a girl.

A

1) All B are . . .:
∀x (Bx → ϕ(x))

2) “Some C are D”, where C represents the class of girls and D the class of those objects which are loved by x:
∃y (Gy ∧ Lxy)

3) substitute ϕ(x):
∀x (Bx → ∃y (Gy ∧ Lxy))

113
Q

translate in steps:

No girl who loves a boy is not loved by some boy

A

1) “No A are B”:
¬∃x (ϕ(x) ∧ ψ(x))
- ϕ(x) who are girls who love some boy
- ψ(x) class of those x who are loved by no boy

2) x is a girl and x loves a boy:
(Gx ∧ ϕ1(x))

3) substitute with ϕ(x)
¬∃x ((Gx ∧ ϕ1(x)) ∧ ψ(x))

4) “x loves a boy:
∃y (By ∧ Lxy)

5) substitute
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ψ(x))

6) No boy loves x:
¬∃z (Bz ∧ Lzx)

7) substitute:
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ¬∃z (Bz ∧ Lzx))

114
Q

translate: “Someone can fool some people some of the time”

A

∃x(P x ∧ ∃y(P y ∧ ∃z(T z ∧ F xyz)))

115
Q

translate: ”Someone cannot fool all people all of the time”

A

¬∃x(P x ∧ ∀y(P y → ∀z(T z → F xyz)))

116
Q

monadic predicate logic

A

“unary properties”, with atomic statements involving one object only.

e.g: ∀x(Ax → Bx), ∀x(Bx → Cx) imply ∀x(Cx → Ax)

117
Q

Not all A are B =

A

Some A are not B

118
Q

All A are not B =

A

there are no A that are also B

119
Q

There are no A that are also B =

A

All A are not B

120
Q

Some A are not B =

A

Not all A are B

121
Q

¬∀x(Ax → Bx) is equivalent to

A

∃x¬(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)

122
Q

∃x¬(Ax → Bx) is equivalent to

A

¬∀x(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)

123
Q

∃x(Ax ∧ ¬Bx) is equivalent to

A

¬∀x(Ax → Bx)
and
∃x¬(Ax → Bx)

124
Q

∀x(Ax → ¬Bx) is equivalent to

A

¬∃x¬(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)

125
Q

¬∃x¬(Ax → ¬Bx) is equivalent to

A

∀x(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)

126
Q

¬∃x(Ax ∧ Bx) is equivalent to

A

¬∃x¬(Ax → ¬Bx)
and
∀x(Ax → ¬Bx)

127
Q

¬∀xϕ is equivalent to

A

∃x¬ϕ,

128
Q

¬∃xϕ is equivalent to

A

∀x¬ϕ

129
Q

∀xϕ is equivalent to

A

¬∃x¬ϕ

130
Q

∃xϕ is equivalent to

A

¬∀x¬ϕ

131
Q

what is epistemic logic

A

logic of knowledge as based on information, including changes in knowledge which result from observations of facts, or communication between agents knowing different things

132
Q

main sources of information

A

observation
inference
communication

133
Q

functions V valuations

A

V (ϕ) = 1, means ϕ is true in V, V ⊨ ϕ

V (ϕ) = 0 means ϕ is false in V, V ⊭ϕ

134
Q

Truth table: Logical True

A

p
T T
F T

135
Q

Truth table: Logical False

A

p
T F
F F

136
Q

Truth table: logical Identity

A

p
T T
F F

137
Q

Truth table: negation

A

p ¬p
T F
F T

138
Q

Truth table: Logical Conjunction

A 
p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F
139
Q

Truth table: Logical Disjunction

A 
p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F
140
Q

Truth table: Logical implication

A 
p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T
141
Q

Truth table: Logical Equality

A 
p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T
142
Q

Truth table: Exclusive Disjunction

A 
p	q	p ⊕ q
T	T	F
T	F	T
F	T	T
F	F	F

(p ∧ ¬q) ∨ (¬p ∧ q)

143
Q

Truth table: Logical NAND

A 
p	q	p ↑ q
T	T	F
T	F	T
F	T	T
F	F	T

¬(p ∧ q)

144
Q

Truth table: Logical NOR

A 
p	q	p ↓ q
T	T	F
T	F	F
F	T	F
F	F	T

¬(p ∨ q)

145
Q

Build Truth table: for (¬ (p ∨ q) → r)

A 
(¬	(p	∨	q)	→	r)
·	0	0	0	·	0
·	0	0	0	·	1
·	0	1	1	·	0
·	0	1	1	·	1
·	1	1	0	·	0
·	1	1	0	·	1
·	1	1	1	·	0
·	1	1	1	·	1
(¬	(p	∨	q)	→	r)
1	0	0	0	·	0
1	0	0	0	·	1
0	0	1	1	·	0
0	0	1	1	·	1
0	1	1	0	·	0
0	1	1	0	·	1
0	1	1	1	·	0
0	1	1	1	·	1
(¬	(p	∨	q)	→	r)
1	0	0	0	0	0
1	0	0	0	1	1
0	0	1	1	1	0
0	0	1	1	1	1
0	1	1	0	1	0
0	1	1	0	1	1
0	1	1	1	1	0
0	1	1	1	1	1
146
Q

If p then q

A

p → q

147
Q

p if q

A

q → p

148
Q

p only if q

A

p → q

149
Q

p if and only if q

A

p ↔ q

150
Q

The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence

A

ϕ1, . . . , ϕk ⊨ ψ

151
Q

ϕ1, . . . , ϕk ⊨ ψ

A

The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence

152
Q

if ϕ ⊨ ψ and ψ ⊨ ϕ

A

ϕ and ψ are logically equivalent.

153
Q

ϕ and ψ are logically equivalent.

A

if ϕ ⊨ ψ and ψ ⊨ ϕ

154
Q

Modus Tollens

A 
(The simplest case of refutation)
(the way that denies by denying)
(denying the consequent)
If P, then Q.
Not Q.
Therefore, not P.
ϕ → ψ, ¬ψ ⊨ ¬ϕ
155
Q

Truth table: Modus Tollens

A 
ϕ     ψ  ϕ → ψ ¬ψ ¬ϕ
1	1	1	0	0
1	0	0	1	0
0	1	1	0	1
0	0	1	1	1
156
Q

Satisfiable

A

X (say, ϕ1, . . . , ϕk) is satisfiable if there is a valuation that makes all formulas in X true

157
Q

Consistent

A

A set of formulas that does not lead to a contradiction is called a consistent formula set
ϕ |= ψ if and only if {ϕ, ¬ψ} is not consistent

158
Q

inconsistent

A

there is no valuation where all formulas in the set are true simultaneously

159
Q

Tautology

A

A formula ψ that gets the value 1 in every valuation
⊨ ψ
ϕ1, . . . , ϕk |= ψ if and only if (ϕ1 ∧ . . . ∧ ϕk) → ψ is a tautology

160
Q

Logical Equivalences: Commutative

A

p ∧ q ⇐⇒ q ∧ p

p ∨ q ⇐⇒ q ∨ p

161
Q

Logical Equivalences: Associative

A

(p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r)

p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r

162
Q

Logical Equivalences: Distributive

A

p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r)

p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)

163
Q

Logical Equivalences: Identity

A

p ∧ T ⇐⇒ p

p ∨ F ⇐⇒ p

164
Q

Logical Equivalences: Negation

A

p ∨ ¬p ⇐⇒ T

p ∧ ¬p ⇐⇒ F

165
Q

Logical Equivalences: Double Negative

A

¬(¬p) ⇐⇒ p

166
Q

Logical Equivalences: Idempotent

A

p ∧ p ⇐⇒ p

p ∨ p ⇐⇒ p

167
Q

Logical Equivalences: Universal Bound

A

p ∨ True ⇐⇒ True

p ∧ False ⇐⇒ False

168
Q

Logical Equivalences: De Morgan’s

A

¬(p ∧ q) ⇐⇒ (¬p) ∨ (¬q)

¬(p ∨ q) ⇐⇒ (¬p) ∧ (¬q)

169
Q

Logical Equivalences: Absorption

A

p ∨ (p ∧ q) ⇐⇒ p

p ∧ (p ∨ q) ⇐⇒ p

170
Q

Logical Equivalences: Conditional

A

(p =⇒ q) ⇐⇒ (¬p ∨ q)

¬(p =⇒ q) ⇐⇒ (p ∧ ¬q)

171
Q

Rules of Inference: Modus Ponens

A

p =⇒ q
If P, then Q.
P.
Therefore, Q.

172
Q

Rules of Inference: Modus Tollens

A

p =⇒ q
If P, then Q.
Not Q.
Therefore, not P.

173
Q

Rules of Inference: Elimination

A

p ∨ q
P or Q
Not Q
therefore P

174
Q

Rules of Inference: Transitivity

A 
p =⇒ q
q =⇒ r
if P then Q
if Q then R
therefore If P then R
175
Q

Rules of Inference: Generalization

A 
p =⇒ p ∨ q
q =⇒ p ∨ q
If P then P or Q
therefore 
If Q then P or Q
176
Q

Rules of Inference: Specialization

A 
p ∧ q =⇒ p
p ∧ q =⇒ q
If P and Q then P
therefore 
If P and Q then Q
177
Q

Rules of Inference: Conjunction

A

P
Q
therefore P or Q

178
Q

Rules of Inference: Contradiction Rule

A

¬p =⇒ False
If Not P then False
therefore P

179
Q

A proof

A

A proof is a finite sequence of formulas, where each
formula is either an axiom, or follows from previous formulas in the proof by a deduction
rule.

180
Q

theorem

A

A formula that occurs in a proof, typically as the last formula in the sequence

181
Q

axiomatization

A

A set of axioms and rules defines an axiomatization for a given logic

182
Q

axiomatization for propositional logic

A

(1) (ϕ → (ψ → ϕ))
(2) ((ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)))
(3) ((¬ϕ → ¬ψ) → (ψ → ϕ))
and modus ponens
if ϕ and (ϕ → ψ) are theorems, then ψ is also a theorem

183
Q

sound

A

If all theorems of an axiomatic system

are valid, the system is sound

184
Q

complete

A

if all valid formulas are provable theorems,the logic is called complete

185
Q

MOD(ϕ)

A

The information content of a formula ϕ is the set MOD(ϕ) of its models,
that is, the valuations that assign the formula ϕ the truth-value 1.

186
Q

The Sheffer stroke

A

nand (equivalent to the negation of the conjunction operation)

187
Q

conjunctive normal form

A

Every propositional logical formula is equivalent to a conjunction of disjunctions of propositions or their negations

188
Q

boolean tautalogies (in binary arithmatic for or)

A 
x + (y + z) = (x + y) + z
x + y = y + x
x + x = x
x + x = x
x + 0 = 0
x + 1 = 1
x + −x = 1
189
Q

boolean tautalogies (in binary arithmatic for and)

A 
x · (y · z) = (x · y) · z
x · y = y · x
x · x = x
x · 0 = 0
x · 1 = x
x · −x = 0
190
Q

boolean tautalogies (in binary arithmatic mixed and/or/not)

A 
x + (y · z) = (x + y) · (x + z)
x + (x · y) = x
−(x + y) = −x · −y
x · (y + z) = (x · y) + (x · z)
x · (x + y) = x
−(x · y) = −x + −y
− − x = x
191
Q

All A’s are B’s

A

(x)(Ax ⊃ Bx)

192
Q

No A’s are B’s

A

(x)(Ax ⊃ ¬Bx)

193
Q

Some A’s are B’s

A

(∃x)(Ax ⋀ Bx)

194
Q

Some A’s are not B’s

A

(∃x)(Ax ⋀ ¬Bx)

195
Q

All and only A’s are B’s

A

(∃x)(Ax ↔ Bx)

196
Q

Only A’s are B’s

A

(x)(Bx ⊃ Ax)

197
Q

Not all A’s are B’s

A

(∃x)(Ax ⋀ ¬Bx)

198
Q

All A’s are not B’s

A

(x)(Ax ⊃ ¬Bx)

199
Q

what is Rˇ

A

Rˇ is the relational converse of Rˇ

Rˇ = {(y, x) ∈ S^2 | (x, y) ∈ R}.

logic (4 decks)

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