Билет № 1

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 1

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → (C → B)), (D → A), C ├ (D → B).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("x)("y)("z)(P(xy, z) → (P(x, z) Ú P(y, z))) → Q(16)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø((("x)P(x, z)) → Q(y))) Ú ((($z)P(x, z)) & (Ø(($x)Q(x)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 2

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B), (A → C) ├ (A → (B & C)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(Q(k) Ú (("t)P(t, k))) → (($m)P(2t, k)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

Q(y , z) → ((Ø((("x)P(x)) → (($y)Q(x , y)))) & P( y) & (("y)Q(z, y))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 3

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B) ├ ((A → B) Ú B).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("m)($t)(t = m2)) → (($s)($t)P(s + t, t)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(($z)(Ø(P(x, z) → ("y)Q(y)))) Ú (("x)(Q(x) → (ØP(x, y)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 4

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(B → A) ├ ((A Ú B) → A).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("m)($t)(t = m2)) & (("s)("t)(ØP(s + t, t))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(($x)(P(x, y) & (Ø(("y)(Q(y) → P(y, z)))))) Ú (("z)(P(y, z) → Q(z))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 5

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B), (B → C) ├ (A → C).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

((P(m, n) & Q(n)) → Q(m)) Ú (($s)((s = t2) → Q(s))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø(P(x, y) → ("z)(ØQ(x)))) → (($y)(P(y, z) Ú (ØQ(z)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 6

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → (B → C)) ├ (B → (A → C)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

((P(m, s2) & Q(s)) → Q(m)) Ú (($t)("w)(w2 = t)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x, y) → Q(y, z)) Ú (Ø(("x)(P(x, z) Ú (ØQ(y, x))))) Ú (($z)(P(z, y) & (ØQ(z, x)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 7

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → (ØB)) ├ (B → (ØA)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("t)(P(s, t) → ((t = 1) Ú (t = s))) → ("m)(P(m, s2) → P(m, s)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø((($x)P(x, y)) & (Q(z) → (("y)P(y, z))))) Ú (($z)Q(z)).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 8

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((A → (ØB)) → (B → (ØA))).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("s)("t)((P(s, t) & P(u, t)) → P(s + u, t)) Ú ("m)($n)(m = n2).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Q(x) → (("y)P(x, y))) → (($z)(P(z, y) Ú ("x)Q(x))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 9

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((A Ú A) → A).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("m)("n)("p)((P(mn, p) & (("t)(P(p, t) → ((t = p) Ú (t = 1))))) → (P(m, p) Ú Ú P(n, p))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

((("x)($y)P(x, y)) → (ØQ(z))) Ú (P(x, z) → (("y)( ØQ(y)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 10

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

A, B ├ (B & A).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(($x)($y)($z)(z2 = x2 + y2)) → (("s)($t)(s = t2)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x, y) → (($x)Q(x))) → ("z)(Q(z) → (P(x, z) & (($y)(ØQ(y))))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 11

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(Ø(A Ú B)) ├ (ØA).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(Ø(($n)("m)(n3 = m))) Ú (($s)(P(s, t) → Q(s))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(($x)(Ø(("y)(Q(x, y) → (ØP(z)))))) & (("z)(Q(x, z) Ú P(z))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 12

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → (B → C)), (A → B) ├ (A → C).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("x)($y)(Ø(x = y2))) & (P(x, y) → (($y)Q(y))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

((P(x, y) Ú Q(y)) → (Ø(("z)(P(x, z) → (ØQ(z)))))) & (($x)((("y)Q(y)) → R(x))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 13

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B), (ØB) ├ (ØA).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("m)(P(p, m) → ((m = 1) Ú (m = p)))) → (("s)("t)(P(st, p) → (P(s, p) Ú P(t, p)))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(("x)(P(x, y) Ú ($z)Q(z))) & ((ØP(x, z)) → (($x)(ØQ(x)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 14

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(ØB) ├ ((A → B) → (ØA)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(($x)("y)P(y, x)) Ú (("y)($z)(y = z2)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø(P(x, y) Ú (("z)Q(z)))) → (($x)(Q(x) & (Ø(P(y, z) → Q(z))))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 15

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B) ├ ((B → C) → (A → C)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("s)($t)(((s = t2) & Q(t)) → Q(s))) Ú (("w) Q(w)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø((("x)Q(x)) Ú (($z)($y)P(x, y)))) → ((ØQ(x)) & P(x, x)).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 16

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B) ├ ((C → A) → (C → B)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("n)($m)(Ø(P(m, n) → Q(m))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x, y) & (ØQ(z))) Ú (Ø(($x)("y)(P(z, y) → (ØQ(z))))) Ú (("y) (Q(y))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 17

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B) ├ ((C & A) → B).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("x)("y)("z)(P(xy, z) → (P(x, z) Ú P(y, z)))) & (Ø(($t)("y)P(y, t))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(Ø(Q(y) → ($z)P(y, z))) & (("x)(P(x, y) → (($z)Q(z)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 18

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

((ØA) → B) ├ ((ØB) → A) .

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(P(s2, 2) → Q(s)) & (($u)("w)P(w, u)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x) Ú ($y)Q(x, y)) → (("z)(P(z) Ú (Ø(Q(x, z) & P(x))))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 19

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

((ØA) → (ØB)) ├ (B → A) .

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("x)("y)("z)(P(xy, z) → (P(x, z) Ú P(y, z)))) & (("s)($t)(t = s2)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x, y) → ("z)(ØQ(z))) Ú (($x)(P(x, y) & ("z)Q(z))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 20

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B), C ├ ((B → (C → D)) → (A → D)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("m)("n)(P(m, n2) → P(m, n))) & (("s)("t)((Q(s) & P(s, t)) → Q(t))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(("z)((P(x, y) → ($z)Q(z)) Ú P(x, z))) & (P(x, z) Ú ("y)Q(y)).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 21

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → B) ├ ((A Ú B) → B).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

((P(m, s) & P(n, t)) → P(m2 + n2, st)) → (("k)($l)(k = l2)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(("x)(P(x, y) & ($y)Q(y))) → ((ØQ(x)) Ú (($y)P(x, y))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 22

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(A → C) ├ (A → (C & C)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("x)("y)((Q(x2) → Q(x)) & (P(y, x) → P(y2, x))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(P(x, y) Ú (($z)Q(x, z))) → ((ØP(x, y)) & (("z)Q(z, x))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 23

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((Ø(A Ú B)) → (ØA)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("a)($b)(a = b2)) → (($g)($b)P(g – b, b)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

(($x)(P(x, y) → Q(y))) Ú (("y)((ØQ(y)) & P(x, y))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 24

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез. Можно пользоваться теоремой дедукции и её обращением.

(B → A) ├ (((A & B) Ú B) → A).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("y)($z)(y = z2)) → (($x)("y)P(x, y)).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

((ØP(x, y)) → Q(x)) & (("y)(P(y, z) Ú (ØQ(z)))).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 25

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((A → C) → (A → (A & C))).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

(("y)($z)(y = z3)) → (("s)("t)("q)((P(s, q) & P(t, q)) → P(s + t, q))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

Ø((("z)($x)P(z, x)) → (Q(t) Ú P(z, t))) & ($t)("z)(P(t, z) → Q(z)).

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 26

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((A → C) → ((B → C) → ((B Ú A) → C))).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

("x)("y)((Q(x2) → Q(x)) → ((Q(x + y) & Q(y)) → Q(x))).

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 27

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

├ ((A & B) → (A Ú B)).

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме:

Московский институт электроники и математики

ФЭ, ФПМ, 2 курс

Контрольная работа по математической логике (и теории алгорифмов)

(домашняя)

Осенний семестр 2009 года. . Комплект № 1

Билет № 28

1. Доказать нижеследующее утверждение, предъявив соответствующий формальный вывод из гипотез и не используя критерий выводимости. Можно пользоваться теоремой дедукции и её обращением.

2. Интерпретировать данную формулу исчисления предикатов. Когда она истинна? Построить отрицание данной формулы, пронеся отрицание через кванторы, так чтобы все знаки отрицания стояли непосредственно перед преди­катными символами. Интерпретировать эту новую формулу. Когда она ис­тинна?

Здесь предметная область (область действия) предикатов – множество N всех натуральных чисел; P(x, y) = ‛x делится на y’; Q(z) = ‛число z чётно’.

3. Данную формулу исчисления предикатов привести к предварённой нормальной форме: