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

 

 

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

 

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ

 

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

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

 

Составитель:

Вахитов Р.Х, доцент, кандидат физико-математических наук, доцент

 

Воронеж

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

Тема: Операции над высказваниями

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

Цель: решение задач на построение таблицы истинности.

Задачи. 1. Докажите, что формула Aº (pÞ q)Þ ((qÞ r)Þ (pÞ r)) является тавтологией, а формула Bº ((pÞ q)Þ (qÞ r))Þ (pÞ r) – нет.

Доказательство для A провести двумя способами: построением полной таблицы истинности и методом рассуждения от противного.

Для формулы B построить сокращенную таблицу истинности.

2. Докажите построением полной таблицы истинности один из двух законов де Моргана (второй – самостоятельно).

3. Докажите построением сокращенной таблицы истинности один из двух законов дистрибутивности (второй – самостоятельно).

4. Исходя из условий PÚ Q=1, QÙ R=0, RÞ S=0, Ø SÛ T=1, определите истинностные значения высказываний P, Q, R, S, T. Найдите самое короткое решение.

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

1. Решение. 1) Доказать, что формула A – тавтология, можно двумя способами: построением таблицы истинности или методом от противного.

а) Построим таблицу истинности для формулы A:

p	q	r	pÞ q	qÞ r	pÞ r	(qÞ r)Þ (pÞ r)	A

 

При любом наборе истинностных значений переменных p, q, r формула A принимает значение 1, значит, A – тавтология.

б) Пусть A – не тавтология, т.е. Aº 0 для некоторых значений переменных p, q, r. Тогда для импликаций со значениями 0 последовательно получим: pÞ qº 1 и (qÞ r)Þ (pÞ r)º 0; qÞ rº 1 и pÞ rº 0; pº 1 и rº 0. Далее для импликаций со значениями 1 последовательно получим: qº 1 и rº 1. Ввиду полученного противоречия, нельзя предполагать, что A – не тавтология.

2) B – не тавтология, так как Bº 0, если pº 1, qº 0 и rº 0.

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

4. По определению импликации из RÞ S=0 следует R=1 и S=0. По определению отрицания Ø S=1. По определению эквивалентности из Ø SÛ T=0 и Ø S=1 следует T=0. По определению конъюнкции из QÙ R=0 и R=1 следует Q=0. По определению дизъюнкции из PÚ Q=1 и Q=0 следует P=1. Ответ: (P, Q, R, S, T)=(1, 0, 1, 0, 0).

 

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

1. Докажите двумя способами (при помощи таблицы истинности и методом доказательства от противного), что формула X – тавтология. Решение 2-м способом постройте так, чтобы на каждом шаге истинностное значение определялось бы однозначно.

 

	X=[(AÚ B)Ù (AÚ C)]Þ [AÚ (BÙ C)]
	X=[(AÚ C)Ù (BÚ C)]Þ [(AÙ B)Ú C]
	X=[AÙ (BÚ C)]Þ [(AÙ B)Ú (AÙ C)]
	X=[(AÚ B)Ù C]Þ [(AÙ C)Ú (BÙ C)]
	X=[AÞ (BÚ C)]Þ [(AÞ B)Ú (AÞ C)]
	X=[(AÞ B)Ú (AÞ C)]Þ [AÞ (BÚ C)]
	X=[(AÙ B)Þ C]Þ [(AÞ C)Ú (BÞ C)]
	X=[(AÞ C)Ú (BÞ C)]Þ [(AÙ B)Þ C]
	X=[(AÞ B)Ù (AÞ C)]Þ [AÞ (BÙ C)]
	X=[(AÞ C)Ù (BÞ C)]Þ [(AÚ B)Þ C]

2. Исходя из данных условий, определите истинностные значения высказываний P, Q, R, S, T. Найдите самое короткое решение.

	Ø PÚ Q=1	QÙ Ø R=0	Ø RÞ S=0	SÛ Ø T=0
	Ø PÚ Q=0	Ø QÙ R=0	Ø RÞ S=1	SÛ T=1
	PÚ Ø Q=1	QÙ Ø R=1	Ø RÞ S=1	Ø SÛ Ø T=0
	PÚ Ø Q=1	Ø QÙ R=0	RÞ Ø S=0	SÛ Ø T=1
	PÚ Ø Q=0	QÙ Ø R=0	Ø RÞ S=1	Ø SÛ T=0
	Ø PÚ Q=1	Ø QÙ R=1	RÞ S=1	SÛ Ø T=1
	PÚ Q=1	QÙ Ø R=0	Ø RÞ Ø S=0	SÛ T=0
	Ø PÚ Ø Q=0	QÙ R=0	Ø RÞ S=1	Ø SÛ Ø T=1
	Ø PÚ Ø Q=1	QÙ Ø R=1	Ø RÞ S=1	Ø SÛ T=0
	Ø PÚ Ø Q=1	Ø QÙ R=0	RÞ S=0	SÛ Ø T=1

 

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

Тема: Запись предложений на языке пропозициональной логики

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

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

Задачи. 1. Построить все пропозициональные формулы, состоящие в точности из следующих символов (не считая скобок):

а) пропозициональные переменные p, q, связки Ø, Þ;

б) пропозициональные переменные p, q, r, связки Ù, Þ.

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

3. Приведите примеры диъюнкций и конъюнкций из арифметики.

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

5. Приведите примеры дизъюнкции и разделительной дизъюнкции.

Указания к решению задач. 2 (f). Необходимым условием сходимости последовательности s является ограниченность s.

Решение. Обозначим: «s сходится» через p, «s ограничена» через q. Тогда данное предложение можно записать в виде формулы pÞ q.

Самостоятельно: приведите примеры импликаций и эквивалентностей из арифметики и геометрии.

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

1234Следующая ⇒

Поделиться: