Задачи для самостоятельного решения. 1). Доказать с помощью законов алгебры множеств следующие тождества:

1). Доказать с помощью законов алгебры множеств следующие тождества:

а)

б)

в) Æ.

2) Доказать, что из и следует =Æ

3) Доказать следующие соотношения для мощностей конечных множеств:

а)

б)

4) Доказать счётность множества рациональных чисел, указав способ их перечисления.

5). Установить взаимно однозначное соответствие между заданными множествами, указав соответствующую биекцию:

а) [0;1] и [0;2];

б) (-1;1) и (-∞; ∞).

6). Отношение R на множестве Z определяется следующим образом:

делится на 3.

Показать что R есть отношение эквивалентности, найти число классов эквивалентности и описать их.

7). На системе множеств {a},{a,b},{b,c},{a,c},{a,b,c} с частичным порядком по включению указать минимальные, максимальные, наименьший и наибольший элементы.

8).Показать, что отношение “х делит y” является отношением частичного порядка на множестве N.

9). Построить таблицу умножения в кольце классов вылетов:

а) по модулю 5;

б) по модулю 6.

В чём принципиальное различие колец а) и б)?

10). Булева функция от трёх переменных задана таблицей:

x1 x2 x3	F(x1 x2 x3)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Показать, что данная функция имеет две минимальные д. н. ф., Найдя их с помощью операций булевой алгебры и дав геометрическую интерпретацию на единичном кубе.

11).Построить таблицу истинности для высказывания:

а) (P ® (Q ® R)) ® ((P ® Q) ® (P ® R));

б) (P Ù (Q Ú )) Ù (( ® P) Ú Q).

12).Число А называется пределом функции y = f (x) при x ® a, если для любого сколь угодно малого ε > 0 существует δ > 0 такое, что при выполнении неравенства < δ выполняется неравенство

<ε.

Запишите это определение на языке предикатов и кванторов.

13). Проверить правильность следующего рассуждения. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжёт.

Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжёт. Следовательно, Смит был убийцей.

14). «Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

- Говорит Мегрэ. Есть новости?

- Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжёт. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать Валг, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет.

- Немедленно задержите Этьена.»

Логически обоснуйте действия комиссара Мегрэ, принимая во внимание наряду с полученной от инспекторов информацией также известный Мегрэ факт, что трезвый Франсуа никогда не лжет.

15). Среди n монет имеется одна фальшивая вес которой меньше. Результатом взвешивания является определение, что на одной из чашек весов находится больший или меньший вес, или веса одинаковы. Указать алгоритм, гарантирующий нахождения фальшивой монеты за не более ]log₃ n[ взвешиваний.

16). Выяснить, применима ли машина Тьюринга, задаваемая программой

q₁ 1 q₂ 1 R

q₁ 1 q₁ 0 R

q₂ 0 q₃ 1 R

q₂ 1 q₃ 0 L

q₃ 0 q₁ 0 R

q₃ 1 q₀ 1 C,

к слову Р.

а) Р=10³1

б) Р=[10]²1.

17). Построить в алфавите {0,1} машину Тьюринга, которая применима к словам вида и , но не применима к словам вида 1^2m01^2n-1 и 1^2n-101^2m . К словам иного вида машина может быть как применима, так и не применима.