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

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

систем управления и радиоэлектроники (ТУСУР)
Контрольная работа № 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)      Является ли формула

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

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

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

(подставили в формулы значения q, r и t )
Желая избежать противоречия примем , получим
, противоречия нет.

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

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

 ложна?





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

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

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

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

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

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

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

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

(подставили в формулы значения Л, r и t )
Так как  и , то  подставим и получим
- противоречие.

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

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

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

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

2.      Докажем теперь, что и . Пусть  выполнено, докажем, что и  . Поскольку требуется доказать включение множеств, то возьмем произвольный элемент , однозначно . Значит  и тогда . Аналогично для B. Доказательство закончено.
9)      Проверить, что
Это выражение верно, так как согласно  не существует элемента , который не входил бы в . Следовательно, для , . Обратное не верно.
10)  Проверить тождество
Решение. Построим диаграмму Эйлера для левого множества в четыре этапа.

Диаграмма для множества	Диаграмма для множества

Диаграмма для множества	Диаграмма для множества

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



     

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