Тема: Тавтологии. Законы логики

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

Цель: научиться решать задачи на законы алгебры логики – в виде тавтологий и эквивалентных формул.

Задачи. 1. Упражнение 1 на стр. 25 по книге [1].

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

3. Упражнение 7 (a) – (f), (n) на стр. 26 по книге [1].

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

1, 2. С целью доказательства тавтологии, постройте таблицу истинности или примените метод рассуждения от противного. С целью опровержения тавтологии, укажите те значения пропозициональных переменных, при которых формула равна 0.

3. С целью доказательства эквивалентности двух формул, постройте их таблицы истинности или докажите, что левая формула равна 1 (0) Û правая формула равна 1 (соответственно, 0).

Самостоятельно проверьте выполнение законов дистрибутивности операций Ù, Ú, Û, Ü относительно операции разделительного «или» и законов дистрибутивности операции разделительного «или» относительно операций Ù, Ú, Û, Ü.

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

Тема: Логическое следование

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

Цель: научиться решать задачи на проверку логических следований.

Задачи. 1. Упражнение 1.36 (а) – (д) на стр. 26 по книге [2].

2. Упражнение 1.37 (а) – (д) на стр. 27 по книге [2].

Указания к решению задач. Применить таблицы истинности

1. Посмотреть решение1.36 (л) на стр. 27 по книге [2].

2. Посмотреть решение1.37 (л) на стр. 28 по книге [2].

Самостоятельно. 1. Упражнение 1.36 (е) – (л) на стр. 26 по книге [2].

2. Упражнение 1.37 (е) – (л) на стр. 27 по книге [2].

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

Тема: Равносильность формул

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

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

Задачи. 1. Упражнение 1.56 (а) – (д) на стр. 33 по книге [2].

2. Упражнение 1.57 (а) – (д) на стр. 27 по книге [2].

Указания к решению задач. Применить таблицы истинности

1. Посмотреть решение1.56 (л) на стр. 27 по книге [2].

2. Посмотреть решение1.57 (л) на стр. 28 по книге [2].

Самостоятельно. 1. Упражнение 1.56 (е) – (л) на стр. 26 по книге [2].

2. Упражнение 1.57 (е) – (л) на стр. 27 по книге [2].

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

Тема: Дизъюнктивные и конъюнктивные нормальные формы

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

Цель: научиться строить СДНФ и СКНФ пропозициональных формул, научиться решать задачи на применение СДНФ и СКНФ.

Задачи. 1. Используя таблицу истинности, найдите СДНФ и СКНФ (от переменных p, q, r) формулы Aº ((pÙ q)Þ Ø r)Û (Ø qÙ r).

2. Докажите, что все следствия СКНФ f₁Ù …Ù f_m, где f₁, …, f_m - совершенные дизъюнкции пропозициональных переменных, содержатся среди формул f₁, …, f_m их всевозможных конъюнкций.

3. Упражнение 2.34 (а) – (д) на стр. 58 по книге [2].

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

1. Решение.Построим таблицу истинности формулы A:

p	q	r	pÙ q	Ø r	(pÙ q)Þ Ø r	Ø q	Ø qÙ r	A
			л
			л
			л
			л
			л
			л

Выделим строки, в которых Aº 1, и применим рассуждение, проведенное в ходе доказательства теоремы 1.

.

Следовательно, (pÙ qÙ r)Ú (pÙ Ø qÙ r)Ú (Ø pÙ Ø qÙ r) – СДНФ A.

Выделим строки, в которых Aº 0, и аналогично находим СДНФ Ø A:

(pÙ qÙ Ø r)Ú (pÙ Ø qÙ Ø r)Ú (Ø pÙ qÙ r)Ú (Ø pÙ qÙ Ø r)Ú (Ø pÙ Ø qÙ Ø r).

Далее, находим СКНФ A, используя законы де Моргана:

Aº Ø ((pÙ qÙ Ø r)Ú (pÙ Ø qÙ Ø r)Ú (Ø pÙ qÙ r)Ú (Ø pÙ qÙ Ø r)Ú (Ø pÙ Ø qÙ Ø r))º

º Ø ((pÙ qÙ Ø r)Ù Ø (pÙ Ø qÙ Ø r)Ù Ø (Ø pÙ qÙ r)Ù Ø (Ø pÙ qÙ Ø r)Ù Ø (Ø pÙ Ø qÙ Ø r))º

º (Ø pÚ Ø qÚ r)Ù (Ø pÚ qÚ r)Ù (pÚ Ø qÚ Ø r)Ù (pÚ Ø qÚ r)Ù (pÚ qÚ r).

2. Решение упражнения 2.33 на стр. 58 по книге [2].

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

Используя таблицу истинности, найдите СДНФ и СКНФ (от переменных p, q, r) формулы A

№№	А
	(RÞ (Ø SÚ Ø T))Û ((RÙ S)Þ T)
	RÞ Ø (SÞ ((RÚ T)Þ Ø (SÙ T)))
	(RÙ Ø (SÚ T))Þ ((RÙ S)Û Ø T)
	(Ø (RÞ (RÚ S))Þ (Ø TÙ S))Ù T
	(RÛ Ø (SÚ T))Þ (Ø (RÞ S)Ù T)
	(RÞ Ø (SÙ T))Û ((Ø RÚ S)Þ T)
	RÞ Ø (SÞ (Ø (RÚ T)Þ (SÙ T)))
	(Ø (RÙ S)Ú T)Þ ((RÚ S)Û Ø T)
	(Ø (RÞ (RÙ S))Þ (TÚ S))Ú Ø T
	(RÛ Ø (SÙ T))Þ Ø ((RÞ S)Ú T)

 

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

⇐ Предыдущая1234Следующая ⇒

Поделиться: