Практическое занятие №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