Exam COPY Flashcards

1
Q

t is free for x in φ

A

if no free x leaf in φ occurs in the scope of ∀y or ∃y for
any variable y occurring in t.

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

Draw parse tree of following formula and give which variabels are bound or free

∀x ((P (x) → Q(x)) ∧ S(x, y))

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

What is the meaning of following notation

φ[t/x]

A

replacing all free occurrences of x in φ
by t

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

2017 - 1b

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Free and bound variable

∀x ((P (x) → Q(x)) ∧ S(x, y))

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

establishing the validity of the sequent

Premiss x + 1 = 1 + x

Premiss (x + 1 > 1) → (x + 1 > 0)

Conclusion (1 + x) > 1 → (1 + x) > 0

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

Premiss ∀x (P (x) → Q(x))

Premiss ∃x P (x)

Conc. ∃x Q(x)

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

Prove folowing sequent

Premiss ∀x (P (x) → Q(x))

Premiss ∀x P (x)

Conc. ∀x Q(x)

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

Prove following sequent

Premiss P (t)

Premiss ∀x (P (x) → ¬Q(x))

Conc. ¬Q(t)

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

Prove the following sequent

Premiss ∀x .(P (x ) →Q (x ))

Conc. ∀x .¬Q (x ) →∀x .¬P (x )

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

Show general proof for

  1. For all introduction
  2. For all elimination
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Exercise 1.2.1 - c

Premiss (p ∧ q) ∧ r

Conc p ∧ (q ∧ r)

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

Exercise 1.2.1 - e

Premiss q → (p → r)

Premiss ¬r

Premiss q

Conc. ¬p

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

Exercise 1.2.1 - f

Conc (p ∧ q) → p

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

Exercise 1.2.1 - h

Premiss p

Conc. (p → q) → q

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

Exercise 1.2.1- i

Premiss (p → r) ∧ (q → r)

Conc p ∧ q → r

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

Exercise 1.2.1 - j

Premiss q → r

Conc (p → q) → (p → r)

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

Exercise 1.2.1 - l

Premiss p → q

Premiss r → s

Conc p ∨ r → q ∨ s

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

Exercise 1.2.1 - n

Premiss (p ∨ (q → p)) ∧ q

Conc p

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

Exercise 1.2.1 - o

Premiss p → q, r → s

Conc p ∧ r → q ∧ s

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

Exercise 1.2.1 - r

Premiss p → q ∧ r

Conc (p → q) ∧ (p → r)

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

Exercise 1.2.1 - v

Premiss p ∨ (p ∧ q)

Conc p

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

Exercise 1.2.1 - x

Premiss p → (q ∨ r)

Premiss q → s

Premiss r → s

Conc p → s

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

Exercise 1.2.1 - y

Premiss (p ∧ q) ∨ (p ∧ r)

Conc p ∧ (q ∨ r)

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

Exercise 1.2.2 - a

Premiss ¬p → ¬q

Conc q → p

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

Exercise 1.2.2 - b

Premiss ¬p ∨ ¬q

Conc ¬(p ∧ q)

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

Exercise 1.2.2 - c

Premiss ¬p

Premiss p ∨ q

Conc q

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

Exercise 1.2.2 - d

Premiss p ∨ q

Premiss ¬q ∨ r

Conc p ∨ r

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

Exercise 1.2.2 - e

Premiss p → (q ∨ r)

Premiss ¬q

Premiss ¬r

Conc ¬p

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

Exercise 1.2.2 - f

Premiss ¬p ∧ ¬q

Conc ¬(p ∨ q)

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

Exercise 1.2.2 - g

Premiss p ∧ ¬p

Conc ¬(r → q) ∧ (r → q)

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

Exercise 1.2.2 - i

Premiss ¬(¬p ∨ q)

Conc p

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

exercise 1.2.3 - d

Conc ¬p → (p → (p → q))

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

Exercise 1.2.3 - n

Premiss p ∧ q

Conc ¬(¬p ∨ ¬q)

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

Prop logic - Semantics Exercise 1.4.2 - c

Compute the complete truth table of the formula

p ∨ (¬(q ∧ (r → q)))

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

Prop logic - semantic 1.4.4 - b

Compute the truth value on the formula’s parse tree, or specify the corresponding
line of a truth table where

p evaluates to F, q to T and the formula is

p → (¬q ∨ (q → p))

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

Prop logic - semantic 1.4.4 - c

Compute the truth value on the formula’s parse tree, or specify the corresponding
line of a truth table where
the formula is

¬((¬q ∧ (p → r)) ∧ (r → q))

p evaluates to F, q to T and r evaluates to T

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

Prop logic - semantic - 1.4.5

A formula is valid if all its valuations evaluate to true. A formula is satisfiable if it evaluates to true for at least one of its valuations.

Is the following formula valid ? Is it satisfiable ?

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

Prop logic - semantic 1.4.12

Premiss p → (q → r)

Conc p → (r → q)

Show that the above sequent is not valid by finding a valuation in which the truth values of the premiss formulas are true but the formula for conclusion is false

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

prop logic - semantic 1.4.13 a

Premiss p ∨ q

Conc p ∧ q

give examples of natural language
declarative sentences for the atoms p and q such that the premises are true,
but the conclusion false

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

prop logic - semantic 1.4.13 b

Premiss ¬p → ¬q

Conc ¬q → ¬p

give examples of natural language
declarative sentences for the atoms p and q such that the premises are true,
but the conclusion false

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

Prop logic - deduction 1.2.3 q

Conc (p → q) ∨ (q → r)

Using LEM

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Exercise 2.3.9 - a

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∃x (S → Q(x)) |− S → ∃x Q(x)

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

Exercise 2.3.9 - d

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∀x P (x) → S |− ∃x (P (x) → S)

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

Exercise 2.3.9 - k

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∀x (P (x) ∧ Q(x)) |− ∀x P (x) ∧ ∀x Q(x).

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

Exercise 2.3.9 - l

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

Premiss ∀x P (x) ∨ ∀x Q(x)
Conc ∀x (P (x) ∨ Q(x)).

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

Exercise 2.3.9 - m

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∃x (P (x) ∧ Q(x)) |− ∃x P (x) ∧ ∃x Q(x).

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

Exercise 2.3.9 - n

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∃x F (x) ∨ ∃x G(x) |− ∃x (F (x) ∨ G(x))

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

Exercise 2.3.9 - p

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

¬∀x ¬P (x) |− ∃x P (x).

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

Exercise 2.3.9 - q

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

∀x ¬P (x) |− ¬∃x P (x)

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

Exercise 2.3.9 - r

Prove the validity of the following sequents in predicate logic, where F , G, P ,
and Q have arity 1, and S has arity 0 (a ‘propositional atom’)

¬∃x P (x) |− ∀x ¬P (x)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
90
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
91
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
92
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
93
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
94
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
95
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
96
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
97
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
98
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
99
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
100
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
101
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
102
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
103
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
104
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
105
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
106
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
107
Q
A
108
Q
A
109
Q
A
110
Q
A
111
Q
A
112
Q

Give all temporal connectives and some examples of formulas

A
  • neXt
  • Future state
  • all future states (Globally)
  • Until
  • Release
  • Weak-until
113
Q

2016 - 1a

Premiss p → q

Premiss q → r

Premiss p → s

Conc p → (r ∧ s)

A
114
Q

2016 - 1c

Premiss p ∨ q

Conc ¬q → p

A
115
Q
A
116
Q

Show examples of LTL connectives

A

Weak until - requires that a remains true until b becomes true, but does not
require that b ever does becomes true (i.e. a remains true
forever). It follows the expansion law of until.

117
Q

2016 - 4b

Let P , S and M be unary predicates and R a binary predicate. Decide for each of the sequents below whether they are valid or not, i.e., give a
proof in natural deduction or a counter-model.

Premiss ∀x¬R(x, x)

Conc ∀x ∀y (R(x, y) → ¬R(y, x))

A
118
Q

2016 - 4c

Let P , S and M be unary predicates and R a binary predicate. Decide for each of the sequents below whether they are valid or not, i.e., give a
proof in natural deduction or a counter-model.

Premiss ∀x ∀y (R(x, y) → ¬R(y, x))

Conc ∀z ¬R(z, z)

A
119
Q

2016 - 4d

Let P , S and M be unary predicates and R a binary predicate. Decide for each of the sequents below whether they are valid or not, i.e., give a
proof in natural deduction or a counter-model.

Conc ∀x∃y R(x, y) ∨ ∀x∃y ¬R(x, y)

A
120
Q
A
121
Q
A
122
Q
A
123
Q

2016- 5b

Let P, Q, and R be unary predicate symbols, and f a unary function
symbol. Give proofs in natural deduction of the following sequents

Premiss ∀x (f (f (x)) = x)
Conc ∀x∃y (x = f (y))

A
124
Q
A
125
Q
A
126
Q
A
127
Q
A
128
Q
A
129
Q
A
130
Q
A
131
Q
A
132
Q
A
133
Q
A
134
Q
A
135
Q
A
136
Q
A
137
Q
A
138
Q
A
139
Q
A
140
Q
A
141
Q
A
142
Q
A
143
Q
A
144
Q
A
145
Q
A
146
Q
A
147
Q
A
148
Q
A
149
Q
A
150
Q
A
151
Q
A
152
Q
A
153
Q
A
154
Q
A
155
Q
A
156
Q
A
157
Q
A
158
Q
A
159
Q
A
160
Q
A
161
Q
A
162
Q
A
163
Q
A
164
Q
A
165
Q
A
166
Q
A
167
Q
A
168
Q
A
169
Q
A
170
Q
A
171
Q
A
172
Q
A
173
Q
A
174
Q
A
175
Q
A
176
Q
A
177
Q
A
178
Q
A
179
Q
A
180
Q
A
181
Q
A
182
Q
A
183
Q
A
184
Q
A
185
Q
A
186
Q
A
187
Q
A
188
Q
A
189
Q
A
190
Q
A
191
Q
A
192
Q
A
193
Q
A
194
Q
A
195
Q
A
196
Q
A
197
Q
A
198
Q
A
199
Q
A
200
Q
A
201
Q
A
202
Q
A
203
Q
A
204
Q
A
205
Q
A
206
Q
A
207
Q
A
208
Q
A
209
Q
A
210
Q
A
211
Q
A
212
Q
A
213
Q
A
214
Q
A
215
Q
A
216
Q
A
217
Q
A
218
Q
A
219
Q
A
220
Q
A
221
Q
A
222
Q
A
223
Q
A
224
Q
A
225
Q
A
226
Q
A
227
Q
A
228
Q
A
229
Q
A
230
Q
A
231
Q
A
232
Q
A
233
Q
A
234
Q
A
235
Q
A
236
Q
A
237
Q
A
238
Q
A
239
Q
A
240
Q
A
241
Q
A
242
Q
A
243
Q
A
244
Q
A
245
Q
A
246
Q
A
247
Q
A
248
Q
A
249
Q
A
250
Q
A
251
Q
A
252
Q
A
253
Q
A
254
Q
A
255
Q
A
256
Q
A
257
Q
A
258
Q

Describe in text how to convert a truth table to

  • DNF
  • CNF
A
  • For DNF look at the rows where the expression becomes True, think of it as “the expression can be true at row x OR row 2 OR …..
  • For DNF look at the rows where the expression becomes False, think of it as “the expression cannot be false at row x and row 2 and …
259
Q
A
260
Q
A
261
Q
A
262
Q
A
263
Q
A
264
Q
A
265
Q
A
266
Q
A
267
Q

2016 - 4a

Let P , S and M be unary predicates and R a binary predicate. Decide for each of the sequents below whether they are valid or not, i.e., give a
proof in natural deduction or a counter-model.

Premiss ∃x (P (x) ∧ ¬M (x))

Premiss ∃y (M (y) ∧ ¬S(y))

Conc ∃z(P (z) ∧ ¬S(z))

A