Типовые практические задания

Теоретические вопросы

1. Определение высказывания. Определение таблицы истинности. Конъюнкция, дизъюнкция, строгая дизъюнкция, эквиваленция, импликация, отрицание высказываний, их определения, обозначения и таблицы истинности.

2. Тождественно-истинные и тождественно-ложные формулы; равносильные формулы.

3. Законы алгебры логики (с доказательством).

4. Понятие булевой функции. Булевы функции одной и двух переменных. Количество булевых функций n переменных.

5. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ). Методика представления булевой функции в виде совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

6. Минимизация СДНФ и СКНФ с помощью карт Карно. Правила объединения единиц (нулей) в контуры.

7. Предикаты. Логические операции над предикатами. Кванторные операции над предикатами.

8. Понятие множества, пустого множества, универсума.

9. Графическое изображение множеств (диаграммы Эйлера-Венна).

10. Способы задания множеств.

11. Сравнение множеств. Подмножество множества.

12. Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность) и их связь с логическими операциями.

13. Свойства (законы) операций над множествами.

14. Мощность множества. Принцип включения-исключения.

15. Декартовое (прямое) произведение множеств. Декартова степень множества.

16. Отношения на множествах. Бинарное отношение на множестве.

17. Матрица отношения. Граф отношения.

18. Виды бинарных отношений на множестве (тождественное, обратное, дополнение, универсальное).

19. Свойства бинарных отношений на множестве (рефлексивное, антирефлексивное, симметричное, антисимметричное, транзитивное, полное, отношение эквивалентности, отношение порядка).

20. Композиция отношений. Степень отношения. Ядро отношения.

21. Функция. Область определения функции. Область значения функции.

22. Свойства функции: инъективность, сюръективность, биективность.

23. Метод математической индукции.

Типовые практические задания

1. Выберите высказывания, которые является истинными, если высказывание P-истинно, а высказывание Q -ложно?

PÙQ, PÚQ, P®Q, P«Q.

2. Выберите высказывания, которые является истинными, если высказывания P и Q ложны?

P Q, PÚQ, Q®P, P«Q.

3. Выберите высказывания, которые является истинными, если высказывания P и Q истинны?

PÙQ, PÚQ, Q®P, P Q.

4. Составьте таблицу истинности для функции, найти ее СДНФ и СКНФ, минимизировать полученные СДНФ и СКНФ с помощью карт Карно:

5. Составьте таблицу истинности для функции, найти ее СДНФ и СКНФ, МДНФ и МКНФ:

6. Для функции найти СДНФ и СКНФ, минимизировать полученные СДНФ и СКНФ с помощью карт Карно.

7. Для функции найти СДНФ и СКНФ, МДНФ и МКНФ.

8. Формализуйте высказывание «Если мало спать и пить много кофе, то наутро будет болеть голова», найдите СДНФ и СКНФ, минимизировать полученные СДНФ и СКНФ с помощью карт Карно.

9. Запишите с помощью формулы логики высказывание «Импликация высказываний А и В примет значение «ложь», тогда и только тогда, когда высказывание А примет значение «истина» и высказывание В примет значение «ложь», найдите СДНФ и СКНФ, МДНФ и МКНФ.

10. Пусть Р(х) — предикат: «число х — делится на два». Выразите словами высказывания $ х Р(х), " х Р(х).

11. Определить, истинными или ложными являются высказывания, построенные из предикатов:

a) ,

b) ,

c) ,

d) ,

e) ,

где

P(x): x – отрицательное число,

Q(x, y): x > y (х и у числа ),

R(x, y): студент x изучает дисциплину y.

12. Q(x, y): студент x учится в колледже y. Запишите на естественном языке высказывания и определите их истинность:

a) ,

b) ,

c) ,

d) ,

e) ,

f) .

13. По каналу связи передаются 3 сообщения, каждое из которых может быть правильно принято, независимо от других. Запишите с помощью формул алгебры логики высказывания, если -«сообщение i принято правильно», i=1..3;:

a) В-«все сообщения будут искажены»;

b) С-«будет искажено только первое сообщение»;

c) D-«одно сообщение будет искажено»;

d) E-«хотя бы одно сообщение будет искажено».

14. Определите значение истинности выражения:

a) (NOT (Истина AND Ложь) OR (NOT Истина)) ХOR Истина

b) NOT ( (Истина ХOR Ложь) AND( Истина OR Истина))

15. Определите значение истинности выражения ((x ≠ 3) OR (x > 6)) AND (NOT (x ≤ 4))) при заданных значениях переменной:

a) при x = 5

b) при x = 4

c) при x = 2

16. Составьте предикат (логическое выражение), которое примет значение true, если будет выполнено условие:

a) Среди чисел а, b, с есть хотя бы одна пара взаимно противоположных.

b) Данные числа х, у являются координатами точки, лежащей в первой координатной четверти.

c) Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).

d) Число d является корнем только одного из уравнений и .

e) число, введенное с клавиатуры, больше 100 и делится нацело на 3;

f) хотя бы одно из трех чисел a, b, c введенных с клавиатуры больше 100.

17. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

18. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

19. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

20. Даны два множества A = {§, ©, ª}, B = {©, ¨, ·}. Что представляет собой множества А \ В, А È В, А Ç В, В \ А, ВΔА?

21. Найдите (B È А)\ C, A Ç (B \ C), (C Ç А) D B, если , , .

22. A=[-2,4], B=(0,3), C=[2,7), D=[1,5). Найти (BDD)\C, (AÇ B) È C.

23. Три множества A, В и С изображены кругами Эйлера. Запишите множество, которое соответствует закрашенной области:

a) b)

24. Изобразите множества кругами Эйлера:

a) , если , , ;

b) , если , , ;

c) , если , , .

25. Определите мощность множества. Задайте множество перечислением элементов.

a) .

b) .

26. Из 105 опрошенных человек 38 любят смотреть по телевизору фильмы ужасов, 29 − мелодрамы, 65 − комедии, смотрят фильмы ужасов или мелодрамы − 56, смотрят комедии или мелодрамы − 81, смотрят фильмы ужасов или комедии − 91, не смотрят телевизор вообще 4 человека. Сколько человек смотрят только комедии?

27. На экзамене по дискретной математике из 45 человек группы первое задание выполнили 17 человек, второе – 20, третье – 20, первое и второе – 5, второе и третье – 7, первое и третье – 6, все три – 4. Сколько студентов не выполнили ни одного задания?

28. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» используется символ «&». Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

фрегат & эсминец 1000
фрегат 2000
эсминец 2500

Сколько страниц будет найдено по запросу

фрегат | эсминец

 

29. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» используется символ «&». Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

васильки & ландыши 650
ландыши & лютики 230
ландыши & (васильки | лютики) 740

Сколько страниц будет найдено по запросу

ландыши & васильки & лютики

30. Пусть , . Найдите , , .

31. Пусть , , . Задайте отношение R перечислением пар, постройте матрицу отношения, изобразите отношение графом. Определите свойства отношения. Найдите и ядро отношения Ker R. Пусть , , . По матрице отношения R, запишите отношение R перечислением пар, изобразите отношение графом. Определите свойства отношения.

32. Пусть , , , , , , . Найдите композицию отношений и .

33. Определите свойства отношения R, если , A –множество всех людей, .