Математическая логика и теория алгоритмов

Томский межвузовский центр дистанционного образования

Томский государственный университет

систем  управления и радиоэлектроники (ТУСУР) 
 
 
 
 
 
 
 
 
 
 

Контрольная работа № 1

по дисциплине

«Математическая логика и теория алгоритмов» 
 

автор учебного пособия:

Зюзьков В.М. 
 
 
 
 
 

            Выполнил:

Студент ТМЦДО

специальности 220201 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Вариант №11

1. Перевести на формальный язык (обязательно указывая универсум):

«Некоторые лентяи на оптимисты, но жизнелюбы».

Универсум М ={люди}. Предикаты: L(x) ≡ «х – лентяй», O(x) ≡ «х – оптимист», Z(x) ≡ «х – жизнелюб».

Формула:

2. Перевести на формальный язык (обязательно указывая универсум):

«Два  философа сидят за столом и спорят»

Универсум М ={люди}. Предикаты: F(x) ≡ «х – философ», S(x) ≡ «х – сидит за столом», С(x,y) ≡ «х спорит с y»

Формула:

3. Перевести с формального языка на человеческий:

(R – Множество вещественных чисел).

Перевод: Для любого вещественного числа  есть большее, синус которого равен  нулю.

4. Перевести на формальный язык (обязательно указывая универсум):

«Ни один судья  не справедлив».

Универсум М ={люди}. Предикаты: J(x) ≡ «х – судья», S(x) ≡ «х – справедлив».

Формула:

5. Является ли формула

 тавтологией?

Использовать  метод доказательства от противного.

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

 
 

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

6. При каких значениях переменных формула

 ложна?

Переберём все  возможные комбинации.

1. Из утверждения получаем, что и одновременно невозможно.

2. Из утверждения  получаем, что и одновременно невозможно

3. Из утверждения получаем, что и одновременно невозможно

4. Возьмём  и , получаем (верно), (верно), (верно).

 выполняется.

Ответ: формула  ложна только при  и , других вариантов нет. 

7. Является  ли формула

 тавтологией?

 
 

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

8. Проверить, что  и 

 

Решение: Сначала следует попробовать  опровергнуть это утверждение, т.е. найти такие множества A, B и C, чтобы выполнялось отношение , но не выполнялось и  или, наоборот, выполнялось и  , но не выполнялось . После безуспешных попыток найти такие множества следует доказать данное утверждение.

      Доказательство  распадается на два этапа.

1. Докажем сначала, что и  . Пусть и  выполнено, докажем, что . Поскольку требуется доказать включение множеств, то возьмем произвольный элемент , следовательно (из ), значит и тем более . Аналогично для .
2. Докажем теперь, что и . Пусть выполнено, докажем, что и  . Поскольку требуется доказать включение множеств, то возьмем произвольный элемент , однозначно . Значит и тогда . Аналогично для B. Доказательство закончено.

 

9. Проверить, что 

 

Это выражение  верно, так как согласно не существует элемента , который не входил бы в . Следовательно, для , . Обратное не верно. 

10. Проверить тождество 

 

Решение. Построим диаграмму Эйлера для левого множества в четыре этапа.

 

 
 

Диаграммы Эйлера показывают, что тождество выполняется. Докажем это. Используя основные тождества алгебры множеств, преобразуем левую и правую части к одному множеству.

     

Преобразуем отдельно первое и второе множества.