Тема: Логически общезначимые формулы

Продолжительность 2 часа

Цель: закрепить умение работать с формулами с кванторами, решать задачи логически общезначимые и выполнимые формулы.

Задачи. 1. Докажите, что формула ($xAÞ " xB)Þ " x(AÞ B) общезначима (для краткости предполажим, что A есть предикат P(x) и B есть предикат Q(x)).

2. Упражнения 1-2 на стр. 63 по книге [1].

Указания к решению задач.

1. Решение. Докажем методом от противного. Допустим, что (($xAÞ " xB)Þ " x(AÞ B))_Iº Л в некоторой интерпретации I. Тогда:

($xAÞ " xB)_Iº И и (" x(AÞ B))_Iº Л по определению импликации,

(P(i)Þ Q(i))_Iº Л для некоторого iÎ I по смыслу квантора общности,

(P(i))_Iº И и (Q(i))_Iº Л по определению импликации,

($xA)_Iº И по смыслу квантора существования,

(" xB)_Iº Л по смыслу квантора общности,

($xAÞ " xB)_Iº Л по определению импликации.

Получается противоречие: ($xAÞ " xB)_Iº И и ($xAÞ " xB)_Iº Л.

Значит, данная формула не может быть ложной в произвольной интерпретации I. Она истинна в любой интерпретации I, т.е. общезначима.

Задача для самостоятельной работы (по вариантам).

Докажите, что формула общезначима (для простоты предполагаем, что A есть предикат P(x) и B есть предикат Q(x)):

 

вариант	формула
	(" xAÞ " xB)Þ $x(AÞ B)
	($xAÞ $xB)Þ $x(AÞ B)
	(" xAÞ $xB)Þ $x(AÞ B)
	" x(AÚ B)Þ (" xAÚ $xB)
	" x(AÚ B)Þ ($xAÚ " xB)
	(" xAÙ $xB)Þ $x(AÙ B)
	" x(AÞ B)Þ (" xAÞ " xB)
	" x(AÞ B)Þ (" xAÞ $xB)
	" x(AÞ B)Þ ($xAÞ $xB)
	$x(AÞ B)Þ (" xAÞ $xB)

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №19

Тема: Отрицание формул

Продолжительность 2 часа

Цель: научиться решать задачи на построение отрицания формул.

Задачи. 1. Постройте отрицание формулы $x$yAÞ " x" yA (знак Ø должна располагаться только перед буквой A).

Докажите, что ни сама формула, ни ее отрицание не являются общезначимыми.

2. Упражнение 9.51 (а)-(д) на стр. 195 книги [2].

Указания к решению задач.

1. Решение. 1) Отрицание формулы преобразуем при помощи известных эквивалентностей:

 

эквивалентные формулы	используемые формулы
Ø ($x$yAÞ " x" yA)
отрицание импликации Ø (AÞ A)º AÙ Ø A
$x$yAÙ Ø " x" yA
отрицание квантора общности Ø " xPº $xØ P
$x$yAÙ $xØ " yA
отрицание квантора общности Ø " xPº $xØ P
$x$yAÙ $x$yØ A

Ответ: $x$yAÙ $x$yØ A.

2) Пусть A есть x=y, I – любое множество, содержащее не менее двух элементов, i, j – различные элементы из I. Тогда:

(i=i)_Iº И по смыслу отношения равенства,

($y i=y)_Iº И по смыслу квантора существования,

($x$yA)_Iº И по смыслу квантора существования,

(i=j)_Iº Л по смыслу отношения равенства,

(" y i=y)_Iº Л по смыслу квантора общности,

(" x" yA)_Iº Л по смыслу квантора общности,

($x$yAÞ " x" yA)_Iº Л по определению импликации.

Следовательно, данная формула не общезначима.

3) Пусть A есть x=yÙ x≠ y, I – любое непустое множество. Тогда:

(i=jÙ i≠ j)_Iº Л –противоречие (по таблице истинности) для всех i, jÎ I,

($y(i=yÙ i≠ y))_Iº Л по смыслу квантора существования,

($x$yA)_Iº Л по смыслу квантора существования,

($x$yAÙ $x$yØ A)_Iº Л по определению конъюнкции.

Следовательно, отрицание данной формулы не является общезначимой формулой.

Задача для самостоятельной работы (по вариантам).

Постройте отрицание формулы (знак Ø должна располагаться только перед буквой A). Докажите, что ни сама формула, ни ее отрицание не являются общезначимыми:

вариант	формула
	" x$yAÞ $x" yA
	$x" yAÞ " x$yA
	" x$yAÞ " y$xA
	$x" yAÞ $y" xA
	" x$yAÙ " y$xØ A
	$x" yAÙ $y" xØ A
	" x$yAÚ " y$xØ A
	$x" yAÚ $y" xØ A
	" x" yAÙ " x" yØ A
	$x$yAÚ $x$yØ A

 

Используемая литература для практических занятий

 

1. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976. – 320 с.

2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2007. – 304 с.

 

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

 

Кафедра информатики и методики преподавания математики

 

 

Комплект учебно-методических материалов к учебной дисциплине:

 

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

для направления 540200 «Физико-математическое образование»

Профиль «Информатика»

 

ЗАДАЧИ К ЭКЗАМЕНУ

1. Докажите, что одна из формул является тавтологией, а вторая – нет:

;

.

2. Докажите, что одна из формул является тавтологией, а вторая – нет:

;

.

3. Докажите, что одна из формул является тавтологией, а вторая – нет:

;

.

4. Докажите, что одна из формул является тавтологией, а вторая – нет:

;

.

5. Докажите, что одна из формул является тавтологией, а вторая – нет:

;

.

6. Является ли тавтологией формула ?

7. Является ли тавтологией формула ?

8. Является ли тавтологией формула ?

9. Является ли тавтологией формула ?

10. Является ли тавтологией формула ?

11. Является ли тавтологией формула ?

12. Равносильны ли формулы и ?

13. Выразите импликацию в терминах отрицания и конъюнкции.

14. Выразите конъюнкцию в терминах отрицания и импликации.

15. Верно ли, что из формулы следует формула ?

16. Верно ли, что из формул и следует формула ?

17. Верно ли, что из формул и следует формула ?

18. Выразите множество истинности предиката через множества истинности предикатов и .

19. Выразите множество истинности предиката через множества истинности предикатов и .

20. Является ли формула логически общезначимой?

21. Является ли формула логически общезначимой?

22. Является ли формула логически общезначимой?

⇐ Предыдущая1234

Поделиться: