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