КОНТРОЛЬНАЯ № 2

Вариант 1

1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Для того, чтобы x было нечетным, достаточно, чтобы x было простым";

При каких значениях переменных x, y, z формула

((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

3. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

4. Доказать выполнимость формулы Ø(pÉØp).

5. Пусть даны предикаты на множестве целых чисел

E(x) º "x - четное число" и D(x,y) º "y делится на x"

Переведите на обычный язык формулу

$x(E(x)ÚD(6,x)).

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если x делится на y и y делится на z, то x делится на z";

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"система уравнений

x + y = 1

2x + 2y = 0

не имеет решения";

8. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"для любых действительных чисел x и y, если x<y и y¹0, то x/y<1".

Вариант 2

1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Если идет дождь, то дует ветер".

2. Доказать, что A~B º ØA~ØB.

3. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

При каких значениях переменных x, y, z формула

((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

I(x,y) º "x равно y";

P(x) º "x - простое число".

Переведите на обычный язык формулу

"x (ØI(1,x)É$y (P(y)&D(y,x))).

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если d - наибольший общий делитель a и b, то a и b делятся на d и d делится на любой общий делитель a и b".

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"существует ровно одно положительное значение квадратного корня из положительного число".

8. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"x - простое число";

Вариант 3

1. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

2. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

3. Что можно сказать об истинностном значении высказывания

(Øp&Øq)~(pÚq), если pÉq ложно?

4. Доказать, что A~B º ØA~ØB.

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x (P(x)É ØD(2,x));

и ответьте истинны они или нет.

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"если произведение двух чисел равно 0, то хотя бы один из сомножителей равен 0";

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"существует такое целое x, что x² - 4 = 0";

8. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"a и b - взаимно простые числа".

Вариант 4

1. Что можно сказать об истинностном значении высказывания (Øp&Øq)~(pÚq), если pÉq ложно?

2. Выразить AÚB через A,B и символ É.

3. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

4. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x "y (ØP(x)É D(x,y))

и ответьте истинны они или нет.

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

б) "система уравнений

x + y = 1

2x + 2y = 0

не имеет решения";

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"для любых действительных чисел x и y, если x<y и y¹0, то x/y<1".

8. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать формулу с двумя свободными переменными - истинную тогда и только тогда, когда x и y являются простыми числами-близнецами.

Вариант 5

1. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

2. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

3. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Если идет дождь, то дует ветер".

4. Выразить AÚB через A,B и символ É.

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если x делится на y и y делится на z, то x делится на z";

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"существует ровно одно положительное значение квадратного корня из положительного число".

7. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"x - простое число";

8. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать предложение, выражающее не существование 1.

Вариант 6

1. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

2.

3. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Для того, чтобы x было нечетным, достаточно, чтобы x было простым";

4. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если d - наибольший общий делитель a и b, то a и b делятся на d и d делится на любой общий делитель a и b".

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"существует такое целое x, что x² - 4 = 0";

7. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"a и b - взаимно простые числа".

8. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать высказывание, выражающее бесконечность множества простых чисел-близнецов.

Вариант 7

1. Доказать выполнимость формулы Ø(pÉØp).

2. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

3. Подозреваются в совершении преступления Жан и Пьер. На суде выступили четыре свидетеля со следующими заявлениями:

а) Пьер не виноват;

б) Жан не виноват;

в) из первых двух показаний по меньшей мере одно истинно;

г) показания третьего свидетеля ложны.

Следствие установило, что четвертый свидетель прав. Кто преступники?

4. Преобразовать к ДНФ формулу Ø(xÚy)&(xÉy).

5. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"если произведение двух чисел равно 0, то хотя бы один из сомножителей равен 0";

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"для любых действительных чисел x и y, если x<y и y¹0, то x/y<1".

7. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать формулу с двумя свободными переменными - истинную тогда и только тогда, когда x и y являются простыми числами-близнецами.

8. Пусть на некотором универсальном множестве U задан предикат Q(x,y) º "x Í y". Запишите, что "множество x есть пересечение множеств y и z".

Вариант 8

1. При каких значениях переменных x, y, z формула ((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

2. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Для того, чтобы x было нечетным, достаточно, чтобы x было простым";

3. Преобразовать к ДНФ формулу Ø(xÚy)&(xÉy).

4. Подозреваются в совершении преступления Жан и Пьер. На суде выступили четыре свидетеля со следующими заявлениями:

Пьер не виноват;

Жан не виноват;

из первых двух показаний по меньшей мере одно истинно;

показания третьего свидетеля ложны.

Следствие установило, что четвертый свидетель прав. Кто преступники?

5. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

б) "система уравнений

x + y = 1

2x + 2y = 0

не имеет решения";

6. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"x - простое число";

7. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать предложение, выражающее не существование 1.

8. Пусть даны предикаты на множестве целых чисел

E(x) º "x - четное число" и D(x,y) º "y делится на x"

Переведите на обычный язык формулу

$x(E(x)ÚD(6,x)).

Вариант 9

1. Доказать, что A~B º ØA~ØB.

2. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

3. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

4. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Для того, чтобы x было нечетным, достаточно, чтобы x было простым";

5. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"существует ровно одно положительное значение квадратного корня из положительного число".

6. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"a и b - взаимно простые числа".

7. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать высказывание, выражающее бесконечность множества простых чисел-близнецов.

8. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

I(x,y) º "x равно y";

P(x) º "x - простое число".

Переведите на обычный язык формулу

"x (ØI(1,x)É$y (P(y)&D(y,x))).

Вариант 10

1. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

2. Что можно сказать об истинностном значении высказывания (Øp&Øq)~(pÚq), если pÉq ложно?

3. Выразить AÚB через A,B и символ É.

4. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Если идет дождь, то дует ветер".

5. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"существует такое целое x, что x² - 4 = 0";

6. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать формулу с двумя свободными переменными - истинную тогда и только тогда, когда x и y являются простыми числами-близнецами.

7. Пусть на некотором универсальном множестве U задан предикат Q(x,y) º "x Í y". Запишите, что "множество x есть пересечение множеств y и z".

8. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x (P(x)É ØD(2,x));

и ответьте истинны они или нет.

Вариант 11

1. Выразить AÚB через A,B и символ É.

2. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

3. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

4. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

5. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"для любых действительных чисел x и y, если x<y и y¹0, то x/y<1".

6. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать предложение, выражающее не существование 1.

7. Пусть даны предикаты на множестве целых чисел

E(x) º "x - четное число" и D(x,y) º "y делится на x"

Переведите на обычный язык формулу

$x(E(x)ÚD(6,x)).

8. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x "y (ØP(x)É D(x,y))

и ответьте истинны они или нет.

Вариант 12

1. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

2. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

3. Доказать, что A~B º ØA~ØB.

4. Что можно сказать об истинностном значении высказывания (Øp&Øq)~(pÚq), если pÉq ложно?

5. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"x - простое число";

6. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать высказывание, выражающее бесконечность множества простых чисел-близнецов.

7. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

I(x,y) º "x равно y";

P(x) º "x - простое число".

Переведите на обычный язык формулу

"x (ØI(1,x)É$y (P(y)&D(y,x))).

8. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если x делится на y и y делится на z, то x делится на z";

Вариант 13

1. Преобразовать к ДНФ формулу Ø(xÚy)&(xÉy).

2. Доказать выполнимость формулы Ø(pÉØp).

3. При каких значениях переменных x, y, z формула ((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

4. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

5. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"a и b - взаимно простые числа".

6. Пусть на некотором универсальном множестве U задан предикат Q(x,y) º "x Í y". Запишите, что "множество x есть пересечение множеств y и z".

7. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x (P(x)É ØD(2,x));

и ответьте истинны они или нет.

8. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если d - наибольший общий делитель a и b, то a и b делятся на d и d делится на любой общий делитель a и b".

Вариант 14

1. Подозреваются в совершении преступления Жан и Пьер. На суде выступили четыре свидетеля со следующими заявлениями:

а) Пьер не виноват;

б) Жан не виноват;

в) из первых двух показаний по меньшей мере одно истинно;

г) показания третьего свидетеля ложны.

Следствие установило, что четвертый свидетель прав. Кто преступники?

2. При каких значениях переменных x, y, z формула ((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

3. Доказать выполнимость формулы Ø(pÉØp).

4. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

5. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать формулу с двумя свободными переменными - истинную тогда и только тогда, когда x и y являются простыми числами-близнецами.

6. Пусть даны предикаты на множестве целых чисел

E(x) º "x - четное число" и D(x,y) º "y делится на x"

Переведите на обычный язык формулу

$x(E(x)ÚD(6,x)).

7. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x "y (ØP(x)É D(x,y))

и ответьте истинны они или нет.

8. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"если произведение двух чисел равно 0, то хотя бы один из сомножителей равен 0";

Вариант 15

1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Если идет дождь, то дует ветер".

2. Доказать, что A~B º ØA~ØB.

3. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

4. Доказать выполнимость формулы Ø(pÉØp).

5. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать предложение, выражающее не существование 1.

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

I(x,y) º "x равно y";

P(x) º "x - простое число".

Переведите на обычный язык формулу

"x (ØI(1,x)É$y (P(y)&D(y,x))).

7. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

а) "если x делится на y и y делится на z, то x делится на z";

8. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"система уравнений

x + y = 1

2x + 2y = 0

не имеет решения";

Вариант 16

1. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

2. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

3. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

4. При каких значениях переменных x, y, z формула ((xÉ(y&z))É(ØyÉØx))ÉØy ложна?

5. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать высказывание, выражающее бесконечность множества простых чисел-близнецов.

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

а) "x (P(x)É ØD(2,x));

и ответьте истинны они или нет.

7. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если d - наибольший общий делитель a и b, то a и b делятся на d и d делится на любой общий делитель a и b".

8. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"существует ровно одно положительное значение квадратного корня из положительного число".

Вариант 17

1. Что можно сказать об истинностном значении высказывания (Øp&Øq)~(pÚq), если pÉq ложно?

2. Выразить AÚB через A,B и символ É.

3. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

4. Доказать, что A~B º ØA~ØB.

5. Пусть на некотором универсальном множестве U задан предикат Q(x,y) º "x Í y". Запишите, что "множество x есть пересечение множеств y и z".

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x "y (ØP(x)É D(x,y))

и ответьте истинны они или нет.

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"если произведение двух чисел равно 0, то хотя бы один из сомножителей равен 0";

8. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"x - простое число";

Вариант 18

1. Проверьте, что формула ((pÉq)&p) É q является тавтологией.

2. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

3. Обосновать метод доказательства "разбором случаев": для того, чтобы доказать формулу (A₁ÚA₂Ú…ÚA_n)ÉB необходимо и достаточно доказать формулу (A₁ÉB)&(A₂ÉB)&…&(A_nÉB).

4. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

5. Пусть даны предикаты на множестве целых чисел

E(x) º "x - четное число" и D(x,y) º "y делится на x"

Переведите на обычный язык формулу

$x(E(x)ÚD(6,x)).

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если x делится на y и y делится на z, то x делится на z";

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах: "система уравнений

x + y = 1

2x + 2y = 0

не имеет решения";

8. Используя только предикаты "x = y" и D(x,y)º"y делится на x", запишите при помощи логических символов следующие формулы от переменных, принимающих натуральные значения:

"a и b - взаимно простые числа".

Вариант 19

1. Является ли тавтологией формула ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)?

2. Преобразовать к ДНФ формулу Ø(xÚy)&(xÉy).

3. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Если идет дождь, то дует ветер".

4. Выразить AÚB через A,B и символ É.

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

I(x,y) º "x равно y";

P(x) º "x - простое число".

Переведите на обычный язык формулу

"x (ØI(1,x)É$y (P(y)&D(y,x))).

6. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

G(x,y,z) º "z - наибольший общий делитель x и y".

Запишите утверждения на языке логики предикатов:

"если d - наибольший общий делитель a и b, то a и b делятся на d и d делится на любой общий делитель a и b".

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"существует ровно одно положительное значение квадратного корня из положительного число".

8. Пусть на некотором универсальном множестве U задан предикат Q(x,y) º "x Í y". Запишите, что "множество x есть пересечение множеств y и z".

Вариант 20

1. Доказать выполнимость формулы Ø(pÉØp).

2. Подозреваются в совершении преступления Жан и Пьер. На суде выступили четыре свидетеля со следующими заявлениями:

а) Пьер не виноват;

б) Жан не виноват;

в) из первых двух показаний по меньшей мере одно истинно;

г) показания третьего свидетеля ложны.

Следствие установило, что четвертый свидетель прав. Кто преступники?

3. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:

"Для того, чтобы x было нечетным, достаточно, чтобы x было простым";

4. Мальчик решил в воскресенье закончить чтение книги, сходить в музей или кино, а если будет хорошая погода - пойти на реку выкупаться. В каком случае можно сказать, что решение мальчика не выполнено? Запишите формулу истинную тогда и только тогда, когда решение мальчика не выполнено (отрицания должны содержаться лишь в простых высказываниях).

5. Пусть даны предикаты на множестве натуральных чисел:

D(x,y) º "y делится на x";

P(x) º "x - простое число".

Переведите на обычный язык формулы:

"x (P(x)É ØD(2,x));

и ответьте истинны они или нет.

6. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =) запишите на языке логики предикатов следующие высказывания о действительных числах:

"если произведение двух чисел равно 0, то хотя бы один из сомножителей равен 0";

7. Пользуясь знаками арифметических операций (+, ´) и отношений (<, =), каждое из следующих высказываний запишите при помощи логических символов, определите, истинное оно или ложное:

"существует такое целое x, что x² - 4 = 0";

8. На множестве натуральных чисел заданы предикаты S(x,y,z)º"x + y = z" и P(x,y,z)º"x ´ y = z".

Записать высказывание, выражающее бесконечность множества простых чисел-близнецов.

Содержание

Авторское предисловие …………………………………………………..
Глава 1. Основы теории множеств …………………………….
§1 Начальные понятия теории множеств ………………………….
§2 Операции над множествами. Диаграммы Венна ………………
§3 Отношения ……………………………………………………….
§4 Функции ………………………………………………………….
§5 Эквивалентность ………………………………………………...
§6 Порядок …………………………………………………………..
Глава 2. Логика высказываний …………………………………
§1 Зачем мы изучаем математическую логику? …………………..
§2 Высказывания ……………………………………………………
§3. Логические связки ………………………………………………
§4 Формулы логики высказываний ………………………………..
§5 Равносильность формул ………………………………………...
§6 Тождественно-истинные формулы ……………………………..
§7 Нормальные формы формул ……………………………………
§8 Разрешимость для логики высказываний ……………………...
Глава 3. Булевы алгебры ……………………………………………
§1 Абстрактное определение булевой алгебры …………………...
§2 Булевы функции. Теорема о нормальной булевой форме …….
§3 Полные системы булевых функций ……………………………
§4 Переключательные элементы …………………………………..
Глава 4. Логика предикатов ………………………………………
§1 Формулы логики предикатов …………………………………...
§2 Интерпретации …………………………………………………..
§3 Выполнимость и общезначимость ……………………………..
Глава 5. Исчисления …………………………………………………
§1 Формальные аксиоматические теории …………………………
§2 Исчисление высказываний ……………………………………...
§3 Исчисление предикатов …………………………………………
§4 Логический вывод ……………………………………………….
§5 Метод резолюций ………………………………………………..
§6 Неполнота математики ………………………………………….
Глава 6. Теория алгоритмов ………………………………………
§1 Понятие алгоритма и неформальная вычислимость …………..
§2 Частично-рекурсивные функции ……………………………….
§3 Ламбда-исчисление ……………………………………………...
§4 Машины Тьюринга ………………………………………………
§5 Тезис Чёрча ………………………………………………………
§6 Некоторые алгоритмически неразрешимые проблемы ……….
§7 Сложность алгоритмов ………………………………………….
Глава 7. Логические парадоксы ………………………………...
Глава 8. Многозначные логики ………………………………….
§1. Трехзначная система Я.Лукасевича …………………………...
§2. Логика Гейтинга ………………………………………………...
§3. Трехзначная система Бочвара Д.А. …………………………….
§4. К-значная логика Поста Е.П. …………………………………...
Литература ………………………………………………………………...
Методические указания по курсу "Математическая логика и теория алгоритмов" ……………………………………………………………….
Котрольные задания по курсу "Математическая логика и теория алгоритмов" ……………………………………………………………….
Контрольная работа №1 ………………………………………………….
Контрольная работа №2 ………………………………………………….