ДМ_МУ_практ(1 часть)

Для функції двох змінних f (x, y) маємо чотири набори змінних: (0, 0), (0,1), (1, 0), (1,1) , для яких відношення часткового порядку встановлюється

так:	(0, 0) (0, 0); (0, 0) (0,1); (0, 0) (1, 0); (0, 0) (1,1);			(0,1) (0,1); (0,1) (1,1);
(1, 0)	(1, 0); (1, 0) (1,1); (1,1) (1,1) .	Розглянуті	набори є порівнянними, а
набори (0,1) і (1, 0) не є порівнянними.
	Завдання 3. Провести	дослідження	на	монотонність функції
f (x, y) x y .

Розв’язок. Для функції f (x, y) запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:

(0, 0) (0,1), (0,0) (1,0), (0,0) (1,1), (0,1) (1,1), (1,0) (1,1),

f (0, 0) 0, f (0,0) 0, f (0,0) 0, f (0,1) 0, f (1,0) 0,

f (0,1) 0,	f (0, 0) f (0,1)
f (1,0) 0,	f (0,0) f (1,0)
f (1,1) 1,	f (0,0) f (1,1)
f (1,1) 1,	f (0,1) f (1,1)
f (1,1) 1,	f (1, 0) f (1,1)

Функція f (x, y) x y є монотонною.

Завдання 4. Провести дослідження на монотонність функції

(x, y) x y .

Розв’язок. Для функції (x, y) запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:

(0, 0) (0,1),	(0, 0) 0,	(0,1) 1,		(0, 0) (0,1) .
(0, 0) (1, 0),	(0, 0) 0,	(1, 0) 1,		(0, 0) (1, 0) .
(0,0) (1,1),	(0,0) 0,	(1,1)	0,	(0,0) (1,1) .
(0,1) (1,1),	(0,1) 1,	(1,1) 0,		(0,1) (1,1) .
Функція (x, y) x y		не є монотонної, тому що при			(0,1) (1,1) не
виконується умова (0,1) (1,1) .
Завдання	5. Побудувати		поліном Жегалкіна		для функції
f (x, y, z) (x y)(y z) .

Розв’язок. Побудуємо поліном Жегалкіна, скориставшись наступним методом: 1) побудуємо еквівалентну формулу, використовуючи операцію кон’юнкції і заперечення; 2) замінимо x на x 1 і розкриємо дужки у формулі, користуючись законом дистрибутивності x ( y z) x y x z . Дійсно

виконуються такі рівності (x y) x y x y , ( y z) y z y z , звідки

51

P(x, y, z) f (x, y, z) x y( y z) (x( y 1) 1)(y 1)(z 1) (xy x 1)

( yz y z 1) x yz x y x yz x y x yz x y xz x yz y z 1,

Оскільки x x 0, то P(x, y, z) x yz x y xz yz x y z 1.

Завдання 6. Використовуючи метод невизначених коефіцієнтів побудувати поліном Жегалкіна для булевої функції трьох змінних, яка задається таким чином: f (x, y, z) (01101000) .

Розв’язок. Поліном Жегалкіна для функції будемо шукати у вигляді:

P(x, y, z) 0 1 x 2 y 3 z 4 xy 5 xz 6 yz 7 xyz , де i {0,1}, i 1,7 .

Коефіцієнти i ( i 1,7) визначаються із рівності P(x, y, z) f (x, y, z) для довільного припустимого набору (x, y, z) :

(x, y, z) (0,0,0),

0 0 ;

(x, y, z) (0,0,1),

1 3 ;

(x, y, z) (0,1,0),

1 2 ;

(x, y, z) (0,1,1),

0 2 y 3 z 6 yz 2 3 6

1 1 6 6 , тому

6 0 ;

(x, y, z) (1, 0,0),

1 1 ;

(x, y, z) (1, 0,1),

0 1 x 3 z 5 xz 1 3 5 1 1 5

5 , тому 5 0 ;

(x, y, z) (1,1, 0),

0 1 x 2 y 4 xy 1 1 4 4 , отже 4

0 ;

(x, y, z) (1,1,1),

0 1x 2 y 3 z 4 xy 5 xz 6 yz 7 xyz 1 1 1 0 7 .

Отже, 0 7 1 і 7 1.

Звідси поліном буде мати вигляд P(x, y, z) x y z x yz .

Завдання

7. Провести

дослідження

на

лінійність

функції

f (x, y, z) (x y) z .

Розв’язок. Побудуємо поліном Жегалкіна функції

f (x, y, z) (x y) z ,

використовуючи такі тотожності:

x y x y , x y xy x y .

f (x, y, z) (x y) z (x y) z (x y)z (x y) z

(xy x y 1)(z 1) (xy x y 1) z 1

xyz xz yz 1 z xy 1 x 1 y 1 1 1 xy x y 1 z 1

xyz xz yz z xy x y 1 xy x y 1 z 1 xyz xz yz 1.

Функція f (x, y, z) (x y) z не є лінійною, оскільки її поліном Жегалкіна містить кон’юнкції змінних.

52

Завдання 8. Системи 3 {x1 | x2 } (штрих Шеффера) і 4 {x1 x2 }

(стрілка Пірса) функціонально повні. Довести повноту систем 1 {x1 , (x1 x2 )}

і 2 {x1 , (x1 x2 )}.

Розв’язок. Проведемо такі перетворення: x1 x2 x1 | x2 (x1 | x2 ) | (x1 | x2 ) ,

	x1 x1 | x1 x1 x1 ;							x1 x2 x1 x2			(x1		x2 ) (x1 x2 ) . Тому			3	{x1 | x2 }
зводиться до 1					{x1 , (x1 x2 )}, а 4						{x1		x2 } зводиться до 2 {x1 , (x1				x2 )}.
			Завдання 9. Перевірити на слабку функціональну повноту систему , що
складається з однієї функції f1 , яка задана таблицею істинності (табл. 7.1).
			Таблиця 7.1 − Таблиця істинності функції f1
			x1		x2			x3		f1
			0		0			0	0
			0		0			1	1
			0		1			0	0
			0		1			1	1
			1		0			0	1
			1		0			1	0
			1		1			0	0
			1		1			1	1
			Розв’язок. Функція f1						немонотонна, тому що (0,0,1) (1, 0,1) .

Побудуємо її поліном Жегалкіна:

f1 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1x2 x3 (x1 1)(x2 1)x3 (x1 1)x2 x3 x1 (x2 1)(x3 1) x1x2 x3 x1x2 x1 x3 .

Поліном Жегалкіна містить кон’юнкцію змінних, отже, функція f1 нелінійна і система є функціонально повною в слабкому розумінні.

Завдання 10. Довести функціональну повноту системи {x, x y}. Розв’язок. Операцію заперечення можна представити поліномом

Жегалкіна у вигляді x x 1, отже, функція заперечення лінійна. Функція заперечення є самодвоїстою, не зберігає 0, не зберігає 1 (це визначається з використанням таблиці істинності), немонотонна. Імплікація є нелінійною функцією, тому що її поліном Жегалкіна має вигляд x y xy x 1, вона несамодвоїста, не зберігає 0, зберігає 1 (можна визначити з таблиці істинності функції), немонотонна. Отже, для кожного класу Поста в даній системі є хоча б одна функція, що цьому класу Поста не належить. За теоремою Поста така система булевих функцій є функціонально повною.

53

8 ЛОГІКА ТА ОБЧИСЛЕННЯ ВИСЛОВЛЕНЬ

8.1 Мета заняття

Ознайомлення c основними поняттями логіки та обчислення висловлень. Вивчення на практичних прикладах способів побудови та інтерпретації висловлень, методів перевірки правильності міркувань.

8.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: елементарні висловлення (атоми); логічні зв’язки і формули логіки висловлень; логіка висловлень та її закони, ізоморфність алгебри логіки і логіки висловлень; пріоритет операцій алгебри висловлень; інтерпретація формул логіки висловлень, правильні міркування; логічна еквівалентність і логічний наслідок; обчислення висловлень (мова, система аксіом і правила висновку); повнота і несуперечність обчислення висловлень; вивідність в обчисленні висловлень (дедуктивний висновок, правила підстановки і відділення); різні аксіоматизації обчислення висловлень; деякі прийоми доведення в обчисленні висловлень.

Підготовка і виконання практичного заняття проводиться в два етапи. Перший етап пов’язаний з вивченням на практичних прикладах таких

основних понять і визначень: висловлення; атом; висловлювальна змінна; істиннісне значення; множина істиннісних значень; логічні зв’язки; формула логіки висловлень (молекула); заперечення висловлення; кон’юнкція, диз’юнкція, імплікація висловлень; засновок (умова, антецедент); логічний наслідок (висновок, консеквент); правильно побудована формула; логіка висловлень; інтерпретація висловлення; тотожно істинна формула; тотожно хибна формула; незагальнозначуща (несуперечлива) формула; правильне міркування; логічна еквівалентність; обчислення висловлень; мова обчислення висловлень; аксіоми обчислення висловлень; висновок в обчисленні висловлень; теорема дедукції; правила висновку; дедуктивний висновок; правило відділення; правило підстановки; несуперечливе логічне обчислення; незалежна система аксіом.

Під час виконання першого етапу практичного заняття студент, повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень логіки і обчислення висловлень.

54

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, які надаються у підрозділі 8.3, на основі запропонованих типових прикладів (див. підрозділ 8.4).

8.3 Контрольні запитання і завдання 8.3.1 Контрольні запитання

1.Який вид речень моделює формальна логіка?

2.Дайте визначення поняття «висловлення».

3.Дайте визначення поняття «алгебра логіки висловлень».

4.Які висловлення називаються атомами?

5.Що в логіці висловлень називають логічними зв’язками?

6.Що в логіці висловлень називають молекулами?

7.Дайте характеристику алфавіту логіки висловлень.

8.Що мають на увазі в логіці висловлень під правильно побудованою формулою?

9.Дайте визначення логічного наслідку одного (декількох) висловлень.

10.Покажіть, що алгебра логіки і логіка висловлень є ізоморфними.

11.Яка формула називається тавтологією, тотожно хибною формулою, несуперечливою формулою?

12.Яке міркування називається правильним?

13.Перелічить найбільш важливі тавтології.

14.Які формули називаються рівносильними? Наведіть приклади рівносильних формул.

15.Що являє собою обчислення висловлень?

16.Поясніть поняття мови, аксіом і правил висновку обчислення висловлень.

17.Наведіть приклади аксіом обчислення висловлень.

18.Яким чином будується дедуктивний висновок?

19.Дайте стислу характеристику основних правил дедуктивного

висновку.

20.Перелічить правила дедуктивних висновків логіки висловлень.

21.У чому полягає повнота і несуперечність обчислення висловлень?

22.Дайте визначення незалежної системи аксіом.

23.Сформулюйте теорему дедукції.

24.У чому полягає метод доведення від супротивного?

55

8.3.2 Контрольні завдання

Завдання 1.

У які дні тижня є істинними висловлення: «Якщо сьогодні вівторок, то завтра понеділок», «Якщо сьогодні понеділок, то завтра вівторок»?

Завдання 2.

Знайти висловлення серед зазначених нижче речень. Указати істиннісні значення висловлень:

а) «Котра година?»; б) «Ціле число 1 є найменшим позитивним цілим числом.»;

в) «Якщо x 3 , то x2 6 .»; г) «Бережися автомобіля!»;

д) «Південна Дакота південний штат.».

Завдання 3.

Визначити, які з даних речень є висловленнями. Указати істиннісні значення висловлень:

а) «Всі парні числа діляться на 2.»; б) «Завантажте пакети в машину.»;

в) «Це твердження не може бути істинним.»; г) «Юпітер найближча до Сонця планета.»;

д) «Не слід зберігати компакт-диски в мікрохвильовій печі.».

Завдання 4.

Нехай A, B, C позначають такі висловлення: A : «Мій комп'ютер – швидкодіючий.»; B : «Я закінчу проект вчасно.»; C : «Я здам іспит.».

Записати в символічній формі такі висловлення:

а) «У мене не швидкодіючий комп’ютер або я закінчу проект вчасно.»; б) «Невірно, що я закінчу проект вчасно і складу іспит.»;

в) «У мене швидкодіючий комп’ютер або я не закінчу проект вчасно і складу іспит.».

Завдання 5.

Записати складні висловлення у вигляді формул, використовуючи висловлювальні змінні для простих висловлень (атомів):

а) «Для того, щоб x було непарним, достатньо, щоб x було простим.»; б) «Якщо на небі хмари, то йде дощ.»; в) «Якщо йде дощ, то на небі хмари.»;

56

г) «Дощ йде тоді й тільки тоді, коли на небі хмари.»; д) «Невірно, що дощ йде тоді й тільки тоді, коли на небі немає хмар.».

Завдання 6.

Розставити всілякими способами дужки в наступних формулах:

а) A B C; б) A B C D.

Завдання 7.

Виключити якомога більше число дужок у формулах:

а) ((B) ~ ( (C))) (((A) (A)) ((B) (D))); б) (( ((A) (B))) ( ((C) (D))) (F)) .

Завдання 8.

Побудувати складні висловлення з використанням тільки зазначених операцій: а) еквівалентність; б) імплікація і кон’юнкція; в) заперечення, кон’юнкція і диз’юнкція.

Завдання 9.

Чи є наступні формули загальнозначущими, суперечливими або несуперечливими: а) ( A) A; б) A B B A ; в) A B A A;

г) A B A B .
Завдання 10.
Довести,	використовуючи	логіку	висловлень,	що

(A B) C (A C) (B C) , де A, B, C − множини.

Завдання 11.

Довести рівносильності:

а) A ( A B) A B ;

б) A (A B) (B C) ( A B) (A C) ;

в) A B (A B) (C C);

г) A B (A B) A (A B) B .

Завдання 12.

Побудувати таблиці істинності для формул: а) A (B C) ; б)

(A B) (A C) ; в) ((A B) ( A B)) A.

Завдання 13.

Довести, що (A B) ((C A) (C B)) − тавтологія.

Завдання 14.

Записати у вигляді диз’юнктивної нормальної форми (ДНФ) і кон’юнктивної нормальної форми (КНФ) такі формули:

57

а) (X1 X 2 ) ( X 2 X3 ) ; б) ( ( X1 X 2 ) (X 2 X1 )); в)

((X1 X 2 ) (X3 X1 )) ( X 2 X3 ) .

Завдання 15.

Записати у вигляді досконалої ДНФ і досконалой КНФ наступні

	формули: а) (X1 X 2 ) ( X1 X3 ) ;				б)	(X1 X 2 ) (X1 X 2 ); в)
	((X1 X 2 X3 ) (X1 X 2 )) X3 ; г) ( X1 X 2 ) ( X 2 X1 ) .
	Завдання 16.
	Перевірити правильність наступних висновків: а)						A B, A B		;
							B
	в)	A B, C B	; б)	A B, B C	; г)	A B, A C		.
		A C		C A		B C

Завдання 17.

Перевірити правильність наступного міркування. Якщо Таня не приходила додому до Валі, то або Валя розбила вазу, або Таня бреше. Якщо Валя не розбила вазу, то Таня приходила додому до Валі, або вазу розбили ще ранком. Якщо вазу розбили ще ранком, то або Валя її розбила, або Таня бреше. Отже, вазу розбила Валя.

Завдання 18.

Довести наступне твердження: «З тотожно хибної формули логічно виходить будь-яка формула».

8.4 Приклади аудиторних і домашніх завдань

Завдання 1. Визначити, які з даних речень є висловленнями:

1)«Волга впадає в Чорне море.»;

2)«Волга впадає в Каспійське море.»;

3)«Який сьогодні день?»;

4)«Відстань від Землі до Сонця дорівнює 150000000 км».

Розв’язок.

Перші два речення є висловленнями, причому перше є хибним

висловленням, а друге істинним. Третє речення висловленням не є (за визначенням), оскільки воно не оповідальне. Четверте речення також не є висловленням, тому що його істинність або хибність залежить від потрібної точності.

Завдання 2. Записати у вигляді формули логіки висловлень і визначити істиннісні значення наступних висловлень:

58

1)«Для того щоб 2 2 4 , необхідно і достатньо, щоб 2 2 4 .»;

2)« 2 2 5 рівносильно тому, що 3 3 8 .».

Розв’язок.
Введемо позначення		атомарних формул:	буквою A позначимо
« 2 2 4 »; буквою B	позначимо «3 3 8 »; буквою C позначимо « 2 2 4 »;
буквою D позначимо « 2 2 5 ». Висловлення 1)			відповідає формулі	A ~ C .
Висловлення 2) відповідає формулі D ~ B . Будемо вважати, що атоми				A і C
істинні ( I ), а атоми	B і D	− хибні ( X ). Визначимо істиннісні значення
складних висловлень:	A ~ C I ~ X X ; D ~ B X ~ X I .

Завдання 3. Записати у вигляді формули логіки висловлень і визначити істиннісні значення наступних висловлень:

1)«6 ділиться на 3, і 10 більше 5»;

2)«6 ділиться на 3, і 7 більше 10».

Розв’язок.

Виділимо атоми, їх три: A – «6 ділиться на 3», B		– «10 більше 5», C –
«7 більше 10».
Тоді висловлення 1)	буде відповідати формулі A B , висловлення 2)
буде відповідати формулі	A C . Будемо вважати, що	висловлення A і B
істинні, а висловлення	C хибне. Використовуючи	істиннісні значення

висловлень A, B, C , визначимо значення висловлень 1) і 2): A B I I I ;

A C I X X .

Завдання 4. Виключити якомога більше число дужок у формулах:

а) ( ((A) (C))) (B); б) (((A) (B)) (C)) ((A) ((B) (C))).

Розв’язок.

а) ( ((A) (C))) (B) (A C) B; б) (A B C) (A (B C)) .

Завдання 5. Довести, що A \ B A B , де A, B множини.

Розв’язок.

Доведемо рівність двох множин з використанням логіки висловлень.

Нехай X1 ,			X 2 висловлення:	X1 =« x A», X 2 =« x В »,. Тоді		висловлення
« x A \ B »			можна записати	у вигляді формули	X1 X 2 .	Висловлення
« A B » можна записати у вигляді формули X1 X 2 . Довести рівність двох
множин це довести, що ці формули еквівалентні: X1					X 2 X1	X 2 . Тому
що праворуч і ліворуч та сама формула, то формули еквівалентні.

59

Завдання 6. Довести рівносильність у логіці висловлень:

( A B) A B .

Розв’язок.

Доведемо рівносильність, використовуючи таблицю істинності для формули ( A B) і формули A B (табл. 8.1).

Таблиця 8.1 − Таблиця істинності для формул ( A B) і A B

	A	B	( A B)		( A B)			B		A B
	X	X	I		X			I		X
	X	I	I		X			X		X
	I	X	X		I			I		I
	I	I	I		X			X		X
	Формули приймають однакові істиннісні значення, отже, вони
рівносильні.
	Завдання 7. Показати, що			висловлення A B C						є логічним
наслідком висловлення A C .
	Розв’язок.							) ( A B C) є
	Досить	переконатися, що		формула		( A C
тавтологією.
	Використовуємо		тотожності	логіки		висловлень для				еквівалентних

перетворень, тобто x y x y . Тоді

A C A B C A C A B C A C A B CA A B C C A A B I I .

Таким чином доведено, що формула є тавтологією.

Завдання 8. Перевірити правильність наступного міркування. Якщо Джонс не зустрічав у цю ніч Сміта, то або Сміт був убивцею, або Джонс бреше. Якщо Сміт не був убивцею, то Джонс не зустрічав Сміта в цю ніч, і вбивство мало місце після опівночі. Якщо вбивство було здійснено після опівночі, то або Сміт був убивцею, або Джонс бреше. Отже, Сміт був убивцею.

Розв’язок.
Введемо наступні висловлювальні змінні:	A : «Джонс зустрічав у цю ніч
Сміта»; B : «Сміт − убивця»; E : «Джонс бреше»; F : «Убивство було після
опівночі». Позначимо складні висловлення відповідно P , P , P . Ці висловлення
	1	2	3
можна записати у вигляді формул:	P A (B E E B) ,
	1

P2 B ( A F) , P3 F (B E E B).

60