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

3



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. Доказательство закончено.



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



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



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



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





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

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







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

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









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



      

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