| Томский межвузовский центр дистанционного образования
Томский государственный университет
систем управления и радиоэлектроники (ТУСУР)
Контрольная работа № 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) Проверить тождество 
Решение. Построим диаграмму Эйлера для левого множества в четыре этапа.
| Диаграмма для множества 
|
Диаграмма для множества 
|
| 
|
|
| Диаграмма для множества 
|
Диаграмма для множества 
|
| 
|
|
Диаграммы Эйлера показывают, что тождество выполняется. Докажем это. Используя основные тождества алгебры множеств, преобразуем левую и правую части к одному множеству.
 
 
Преобразуем отдельно первое и второе множества.
 
|