15

№2.35. А54 * А53 * Р3

№2.36. 495.

№ 2.37. 60,	~2		*~2 .
	с	5	с	4
№ 2.38. 1).	~к	т		к	. 2). к меньше m, тогда число способов получить запись из различных чисел	Аmк.
	А
	т

3.МАТЕМ. АТИЧЕСКАЯ ЛОГИКА

3.1.Основные равносильности.

1)р р.

Коммутативность:

2)р q q р.

3)р q q p .

Ассоциативность:

4)(р q) r р (q r).

5)( р q ) r р (q r).

Дистрибутивность:

6)р (q r). р q р r.

7)р (q r) (р q) (р r).

Законы де-Моргана:

8) p q p q .

9)p q p q .

Поглощение:

10)р р р.

11)р р р.

Операции с 0 и 1

12)р 0 0.

13)р 1 р .

14)р 0 р.

15)р 1 1.

Связь с отрицанием

16)р p 0.

17)р p 1.

Связь импликации и эквиваленции с другими операциями

18)р → q p q.

19)Р ↔ q ( р → q) ( q p ).

16

3.2.Высказывания

№3.2. 1. Ввести обозначения и записать в виде формул высказывания:

а) число делится на 2 и число делится на 3 или не делится на 6;	б) если диагонали параллелограмма
являются биссектрисами углов, то этот параллелограмм – ромб;
в) если число целое и положительное, то оно натуральное;

г) если число целое и положительное, и четное, то оно простое и больше 2; г) если одно слагаемое делится на 3 и сумма делится на 3, то другое слагаемое делится на 3;

д) если одно слагаемое делится на 3, а другое слагаемое не делится на 3, то и сумма не делится на 3; е) если число рациональное или иррациональное, то оно – вещественное;

ж) если число не является вещественны, то оно не является рациональным и не является иррациональным; з) если а = 0 или b = 0, то а* b = 0;

и) если а* b ≠ 0 , то а ≠ 0 и b ≠ 0; к) если а ≠ 0 и b ≠ 0, то а* b ≠ 0.

Какие из этих высказываний имеют одинаковую структуру?

№ 3.2. 2. Пусть имеются высказывания: p - это число положительно, q – это число целое, r – это число простое, s – это число делится на 3.

Прочитайте на русском языке высказывания, задаваемые формулами

а) p q;

б) p q;

в) p p ;

г) q

;

д) p r s;

е)

s;

q

r

ж) p s

;

з) (p qr) (r s);

и)

;

r

p

s

к) p q r s.

Л) p r

.

r

№ 3.2. 3. Записать в виде формулы высказывания:

а). Если основание пирамиды правильный многоугольник и высота проходит через центр основания или двугранные углы при основании равны, то пирамида – правильная.

б). Если основание пирамиды – прямоугольный треугольник, то боковая грань, проходящая через гипоте-

нузу, перпендикулярна основанию тогда и только тогда, когда высота пирамиды проходит через середину гипотенузы.

в). Если число целое или выражается обыкновенной дробью, или выражается конечной десятичной дробью, то оно представимо в виде бесконечной периодической десятичной дроби.

г). Если прямая а параллельна прямой b, а прямая b лежит в плоскости α, то прямая а параллельна плоскости α или прямая а лежит в плоскости α .

д). Если прямая а параллельна прямой b и а1 – параллельная проекция прямой а на плоскость α, и b1 – параллельная проекция прямой b на плоскость α, то а1 параллельна b1,, или а1 совпадает с b1.

№ 3.2. 4. Известно, что p = 0, q = 1, r = 1.		чему равны высказывания:
а) 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

к) p (q r) p q r?

№ 3.2. 5.. Составить таблицу истинности для высказывания

а) p q r , б)

p q r,

в) p q r ,

г) p q r,

д)

q

, е)

p

r, ж)

r,

з)

q) r,

p

r

q

(p q)

p

и)

p

,

к) p ↔ (

r).

(q r)

q

№ 3.2. 6. Решить логическое уравнение (найти значения высказываний, входящих в уравнение), не используя

таблицы истинности.

в) p

а) p ↔

r = 1 ,

б)

(p q)

r = 1 ,

= 0,

q

(q r)

г) (

q) r = 0 , д)

q r = 1 ,

е) p ↔ q

= 0,

p

p

r

ж)

↔ q

= 1,

з)

r = 0,

и) p ↔ (

r) = 0,

p

r

p

q

q

к) p ↔

r = 1,

л)

q

= 1

q

p

r

№ 3.2. 7.. Решить логические уравнения:

0)

p ↔

r = 1;

1)

r =1;

q

(p q)

2)

(

q) r = 0 ;

3)

q r = 1;

p

p

17

4)

p ↔ q

= 0 ;

5)

↔ q

= 1;

r

r

p

6)

r = 0 ;

7)

p ↔ (

r) = 0;

p

q

q

8)

p ↔

r = 1 ;

9) p ↔

= 0.

q

(q r)

№ 3.2. 8. Укажите такой набор значений переменных p и q, при котором формулы Ф1 и Ф 2 принимают различные значения

а) Ф1 = pq r и Ф 2 = p(q r) ;

б) Ф1 = p q r и Ф 2 = p (q r).

№ 3.2. 9. Заданы значения двух переменных p и q, а также значения функций от этих переменных Ф1, Ф2, Ф3. Какие значения могут принимать функции Ф4, Ф5, Ф6 …? Сколько таких функций? Заполните таблицу.

p	q	Ф1	Ф2	Ф3	Ф4	Ф5	Ф6	…
1	1	0	0	0
1	0	0	0	0
0	1	0	0	1
0	0	0	1	0

№ 3.2. 10. Путем преобразования формул доказать равносильности

а) p q ≡ q p ;

б) q r ≡ q r;

в) p q ≡

;

г) pq ≡

,

p

q

p

q

q ≡

д)

;

е)

≡ p

;

p

p

q

p q

q

ж) pq p

≡ p;

з) (p q)(p

) ≡ p;

q

q

и) pq

≡ p q. к) p

q ≡ p q;

p q

p

q

p

л) p (q

) ≡ p q;

м)

рq ≡

q;

p

p

p

н)

(р q) ≡

q.

p

p

№ 3.2. 11. Упростить формулы, используя основные равносильности:

а) p q pr qr q r;

б)

pq r r p q r p q ;

(p

)

в)

;

г) ( p q)(q

)

q

p q

p

(p q);

(

st)(

q rs t ) pq.

д)

е)

p

q

p

p

№ 3.2. 12. Мы ввели независимо друг от друга 5 логических операций , , , , . Можно было бы

обойтись и тремя (почему?) и даже двумя! Выделить такие пары и выразить все остальные операции через них. (указание: одна из них или ).

№3.2. 13. Имеется высказывание: «Если завтра будет хорошая погода, то мы отправимся в музей и посетим выставку современного дизайна или отправимся в лес за грибами». Составьте формулу, соответствующую этому высказыванию, составьте и сформулируйте отрицание этой формулы.

№3.2. 14. Методом математической индукции докажите законы де Моргана для n высказываний.

№3.2. 15. Имеется два высказывания:

1. Если одно слагаемое делится на 3 и сумма двух слагаемых делится на 3, то и второе слагаемое делится на

3.

2. Если первое слагаемое делится на 3, а второе слагаемое не делится на 3, то их сумма не делится на 5. Докажите их равносильность.

№ 3.2. 16 Упростить формулу логики высказываний. Получить её ДНФ и КНФ. Установить будет ли данная формула тождественно истинной, тождественно ложной или выполнимой.

а) p q p r q r q r;

б)

(p ↔ q) p q ;

в) (p q) (q

(p q) p;

);

г)

p

p

q

д)

↔ (q p r);

е)

p q

q r;

p

p r

ж) p

;

з)

q p q

pq

pq ;

и) p q

p;

к)

→ (

↔ p r);

p

q

p

q

л)

((p q) (p r)) (p (q r));

м) (p q) ((r q) (pr

));

q

н)

(p (q r)) ((p q) (p r));

о)

(pq r) (p (q r));

18

п) (p q q) (p q);

р) ( p p)p p.

№ 3.2. 17. По заданным таблицам истинности восстановить функции Ф1, Ф2, Ф3, Ф4, Ф5, Ф6.

p	q		r	Ф1	Ф2	Ф3	Ф4	Ф5	Ф6
1	1	1		0	0	0	1	1	1
1	1	0		0	1	1	1	1	0
1	0	1		1	0	1	1	1	1
1	0	0		0	1	1	1	1	0
0	1	1		1	0	0	1	1	0
0	1	0		1	1	0	0	0	0
0	0	1		0	0	1	0	0	0
0	0	0		1	1	0	1	0	1

№3.2. 18.Докажите, что тождественно ложные формулы не имеют СДНФ, а тождественно истинные формулы не имеют СКНФ.

№3.2 19. Приведением к СДНФ и СКНФ докажите равносильности

а) p q ( q p) ≡

p q p q;

б) p q ≡ p

q;

q

p

r) p ≡ pq

pr ≡ (p

r);

в) ( pq

p

r

r

) (

p

q

г) ( p q) p r ≡ p q p q p r ≡ (p q) ( p q r );

д) (p q )(q r) ≡ p r p q r ≡ ( p q )(p r) ( p r );

е) (p r ) ( q r) ≡ q r p q r ≡ ( p q) ( q r ).

№ 3.2. 20. Решить логические задачи:

Алгоритм:

1.Вводятся обозначения для элементарных высказываний.

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

3.Записываем конъюнкцию полученных формул и приравниваем её 1. (Характеристическое уравнение).

4.Приводим левую часть уравнения к ДНФ (СДНФ).

5.Каждый конъюнктивный член (независимо от других) приравниваем 1.

6.Решаем получившиеся уравнения. Каждое из решений характеристического уравнения является решением задачи.

Замечание. Можно строить формулы со значениями, равными 0. Тогда характеристическое уравнение получается как дизъюнкция этих формул, равная 0. Затем приводим к КНФ и приравниваем каждый её член 0.. Решаем получившиеся уравнения.

Задачи.

а). Левин, Матвеев и Набатов работают в банке. Если Набатов – кассир, то Матвеев – счетовод; если Набатов

– счетовод, то Матвеев бухгалтер; если Матвеев – не кассир, то Левин – не счетовод; если Левин – бухгалтер, то Набатов – счетовод. Кто кем работает?

б). Логик попал в плен к кибернетикам. Главный кибернетик сообщил Логику, что его будут охранять феи Наина, Ева и Эмма вдвоем или даже втроем. Возможно и отсутствие охраны. Логик пробудет в плену столько дней, сколько он приведет высказываний, чтобы угадать, кто из фей его охраняет. Число дней пребывания в плену в любом случае должно быть четным. Для каждого высказывания сообщается истинно оно или ложно.

-Начнем, сказал Логик.

– Если в охране не Наина, то уж точно Ева или Эмма, но не обе вместе. -Неверно!-

-Ну что ж. Больше двух дней в плену я не пробуду. Если в охране не Ева или Эмма, то в ней или Наина или, если не Наина и не Ева, то Эмма.

-Мудрено, но верно.

Кого Логик назвал в охране?

А кого бы он назвал, если бы второе высказывание было ложным?

в). Пятеро друзей А, Б, В,, Г, Д решили записаться в кружок любителей логических задач. Им сказали, что они должны приходить по возможности вечером, однако в разных сочетаниях с соблюдением условий:

1.Если А приходит вместе с Д, то присутствие Б обязательно.

2.Если Д отсутствует, то Б должен быть, а В пусть не приходит.

3.А и В не могут одновременно ни присутствовать, ни отсутствовать.

4.Если придет Д, то Г пусть не приходит.

19

5.Если Б отсутствует, то Д должен присутствовать, но это в том случае, если не присутствует В. Если же В присутствует, при отсутствии Б, то Д приходить не должен, а Г должен прийти.

Сколько вечеров и в каком составе друзья могут прийти? г). N хотел пригласить на обед друзей А, В, С, D, Е, F, G, Н. Оказалось:

1.А не придет, если пригласить В или С или, если одновременно пригласить D и Е.

2.D придет только в том случае если будет приглашен и Е.

3.Е не примет приглашение, если придет В.

4.Е наносит визиты только в сопровождении G.

5.Н не будет возражать против присутствия F только в том случае, если будет приглашен и А.

6.Если не будет приглашен F , то Н будет против приглашения Е.

7.Чтобы пришел G, необходимо пригласить D или Н.

8.G откажется от приглашения, если пригласят Е без А, а также в случае приглашения В или С.

Кто был приглашен на обед?.

д). На автоматизированном участке расположены 5 станков. Если работают первый и трети станки, то четвертый отключен при условии, если подключен пятый станок. Если же первый станок подключен без третьего или выключен пятый станок, то четвертый обязательно подключен. Если пятый станок работает вместе со вторым, при выключенном первом станке, то включен третий станок. Если выключены второй или пятый, то одновременно выключен и четвертый. Мы наблюдаем работу первого и четвертого станков. Что можно сказать о состоянии остальных станков?

е). На складе было совершено хищение. Преступник вывез награбленное на автомашине. Подозрение пало на А, В, С. Было установлено, что

1.Никто, кроме них не замешан в ограблении.

2.С не ходит на «дело» без А (возможно, и с В).

3.В не умеет водить машину.

Виновен ли А?

ж). Три преступника-рецидивиста А, В, С подозреваются в ограблении магазинчика. На допросе было выяснено, что

1.Каждый из них в этот день посещал магазинчик, и никто больше там не был.

2.Если А виновен, то у него был ровно один сообщник.

3.Если В не виновен, то С тоже не виновен.

4.Если виновны ровно двое подозреваемых, то А – один из них.

5.Если С не виновен, то В также не виновен.

Против кого выдвинуто обвинение?

№ 3.2. 21. Обосновать правила вывода:

Правило заключения

Ф1 ф2, ф1 ├ ф2

(ПЗ);

Правило отрицания

Ф1 ф2,

2 ├

1

(ПО);

Ф

Ф

Правило контрапозиции

Ф1 ф2 ├

2

1

(ПК);

Ф

Ф

Правило расширенной контрапозиции

Ф1 ф2 ф3 ├ Ф1

3

2

(ПРК);

Ф

Ф

Правило силлогизма Ф1 ф2, Ф2 ф3 ├ Ф1 ф3

(ПС);

Введение дизъюнкции

ф2, ф1 ├ Ф1 ф2

(ВД);

Удаление дизъюнкции

Ф1 ф2,

Ф

1 ├ ф2

(УД):

Введение конъюнкции

Ф1, ф2 ├ Ф1 ф2

(ВК);

Удаление конъюнкции

Ф1 ф2 ├ ф2

(УК).

№ 3.2. 22. Проверить правильность рассуждений путем их формализации и создания соответствующей формулы с последующим определения ее вида, а также путем построения вывода.

1.Если две стороны треугольника равны, то он равнобедренный. Если треугольник равнобедренный, то углы при основании равны. Данный треугольник не равнобедренный, следовательно, углы при основании не равны.

2.Если две стороны треугольника равны, то он равнобедренный. Если треугольник равнобедренный, то углы

при основании равны. В данном треугольнике нет равных сторон, следовательно, углы при основании не равны.

3.Если две стороны треугольника равны, то он равнобедренный. Если треугольник равнобедренный, то углы при основании равны. В данном треугольнике две стороны равных, следовательно, углы при основании равны.

4.Если две стороны треугольника равны, то он равнобедренный. Если треугольник равнобедренный, то углы при основании равны. В данном треугольнике углы при основании не равны, следовательно, в треугольнике нет равных сторон.

5.Если в четырехугольнике все стороны равны, то он ромб. У ромба диагонали взаимно перпендикулярны. В данном четырехугольнике диагонали не перпендикулярны, следовательно, он не ромб.

6.Придумайте рассуждения с аналогичными по форме посылками и заключениями