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