Реферат: Математическая логика и теория алгоритмов 2 - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

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

Рефераты по математике » Математическая логика и теория алгоритмов 2

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

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

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


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

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

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


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

Зюзьков В.М.


Выполнил:

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

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


Вариант №11

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

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

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

Формула:

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

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

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

Формула:

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

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

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

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

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

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

Формула:

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

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

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

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

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

Желая избежать противоречия примем , получим

, противоречия нет.


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

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

ложна?

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

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

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

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

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

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

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


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

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

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

Так как и , то подставим и получим

- противоречие.


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

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


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

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

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

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


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


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


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


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


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

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


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

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


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

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