20

7.Если натуральное число делится на 6, то оно делится на 2 и 3. Число делится на 2, но не делится на 3, следовательно, оно не делится на 6.

8.Если число целое, то оно рациональное. Если число несократимая дробь, то оно не целое. Следовательно, если число несократимая дробь, то оно не рациональное.

9.Если число дробь, то оно рациональное. Если число целое, то оно рациональное. Следовательно, если число целое, то оно – дробь.

10.Если посылки истинны и рассуждение правильно, то и заключение истинно. Заключение ложно. Следовательно, посылки ложны или рассуждение неправильно.

11.Если целое число больше 1, то оно простое или составное. Если целое число больше 2, то оно больше 1. Если целое число больше 2 и четное, то оно не является простым. Следовательно, если целое число больше 2 и четное, то оно составное. (Использовать терему дедукции при построении вывода).

12.Прямые а и b или параллельны или пересекаются или скрещиваются. Две прямые лежат в одной плоскости и не пересекаются, следовательно, они параллельны.

13.Если целое число делится на 5, то оно оканчивается на 5 или на 0. Данное целое число делится на 5 и не оканчивается на 0, следовательно, оно оканчивается на 5.

14.Вещественное число – рациональное или иррациональное. Если вещественное число иррационально, то оно представимо в виде бесконечной десятичной непериодической дроби. Неверно, что вещественное число представимо в виде бесконечной десятичной периодической дроби и в виде бесконечной десятичной непериодической дроби. Следовательно, если вещественное число представимо в виде бесконечной десятичной перио-

дической дроби, то оно рациональное.

15. Если а = 0 или b = 0, то а b = 0. Оказалось, а b ≠ 0. Следовательно, а ≠ 0 и b ≠ 0. 16. Если а ≠ 0 и b ≠ 0, то а b ≠ 0. Оказалось, а b = 0. Следовательно, а = 0 или b =0.

3.3.Ответы, указания, решения к разделу 3.2

№3.2. 1. а). Решение. Введем обозначения: р – число делится на 2, q – число делится на 3, r - число не делится на 6. тогда формула, соответствующая этому высказыванию (с использованием соглашения о скобках)

будет иметь вид: р q r .

и) r → p ^ q .

№3.2. 2. Решение. е). Число не является простым тогда и только тогда, когда оно делится на 3. ж). Если число положительное и делится на 3, то оно не простое.

№3.2. 3..б). Решение. Введем обозначения: р – основание пирамиды – прямоугольный треугольник, q – боковая грань, проходит через гипотенузу, r - боковая грань перпендикулярна основанию, h - высота пирамиды проходит через середину гипотенузы.

Тогда формула, соответствующая этому высказыванию (с использованием соглашения о скобках) будет иметь вид: р → (q r ↔ h).

д). Решение. Введем обозначения: р – прямая а параллельна прямой b, q – прямая а1 – параллельная проекция прямой а на плоскость α, r - прямая b 1 – параллельная проекция прямой b на плоскость α, п - а1 параллельна b1, х- а1 совпадает с b 1.

Тогда формула, соответствующая этому высказыванию (с использованием соглашения о скобках) будет

иметь вид: р q r → п х.
№ 3.2. 4.	0, 1, 1, 1, 1, 1, 1,1, 0,		0.
к) p	(q r) p q	r. Решение p = 0, q = 1, r = 1.		Подставим в формулу. 0 (1	1) ↔ 0	1 = (по

определению дизъюнкции) = = 0 1↔ 1 =(по определению конъюнкции) = 0↔ 1 = (по определению эквиваленции) = 0.

№ 3.2. 5. Решение.

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

p	q	r		q			q	r	p ↔	q	r.
1	1	1		0			0		0
1	1	0		0			0		0
1	0	1		1			1		1
1	0	0		1			0		0
0	1	1		0			0		1
0	1	0		0			0		1
0	0	1		1			1		0
0	0	0		1			0		1

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

21

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

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

Решение. л) p ↔ q r = 1.

В левой части уравнения задана импликация, которая истинна, если её левая часть равна 0, независимо от значения правой части. Кроме того, импликация истинна, если её левая и правая части равны 1. Получим си-

стемы:

0

0

0

0

p

p

p

p

p 1

1) q 0 ,

2) q 1 ,

3) q 0 ,

4) q 1 ,

5)

q r 1

r 0

r 0

r 1

r 1

Первые четыре системы дают ращения:

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

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

Система 5). Т.к. дизъюнкция не равна 1 только тогда, когда оба высказывания ложны, то получим еще три си-

стемы:
	p 0				p 0			p 0
а)				б)
	q 0 ,				q 1 ,			в) q 1
	r 1				r 0			r 1

Получим решения: (0, 0, 0), (0, 1, 1), (0, 1, 0).

Ответ. (1, 0, 0), (1, 1, 0), (1, 0, 1), (1, 1, 1), (0, 0, 0), (0, 1, 1), (0, 1, 0).

№ 3.2. 8. Указание. Дело сводится к решению двух систем

Ф1 1	Ф1 0
	и
Ф2 0	Ф2 1

№3.2. 9. Таких функций 16.

№3.2. 10.

Указание. Можно преобразовывать обе части равносильностей, стремясь получить одинаковые формулы.

Решение. а). p q ≡ q p . Преобразуем обе части

.Левая часть Ф1 = p q ≡ (по 18 формуле основных равносильностей) ≡ p q.

Правая часть Ф2 =

≡ (по 18) ≡

≡

(по 1) ≡

q

p

q

p

≡

q

≡ (по 2) ≡

q ≡ Ф1. Равносильность доказана.

p

p

№ 3.2. 11. а)

p q r,

б) p (

),

в)

, г) p, д) 1,

r

q

p

q

е)

Решение.

s t)(

q r s t ) p q ≡ (по формуле 18) ≡

p

p

s t)(

r s t ) p q ≡ (по формуле 1) ≡

≡

(

q

p

p

≡ (p s t)(

q

r s t ) p q ≡ (по законам де Моргана, с учетом 1) ≡

p

≡ (p s t)(p

r s t )

p q ≡ (раскрываем скобки по первому закону дистрибутивности) ≡

q

≡ p p p

p r s t

s t p

s t

s t r s t t p q ≡ (по законам поглощения 10 и 12)

≡ p

q

q

q

p

ps t

s t p

s t

s t r 0

p q ≡ (по законам действий с 0)

≡ p p

p s

t s t p

s t

q

q

pq (группируем члены, содержащие р, и выносим р за скобку)

≡ p (1

s t

st q)

s t

≡ (по

q

q

q

15) ≡ р q s t

№ 3.2. 12.

1).Введем обычным образом две операции, например, отрицание и дизъюнкцию. Тогда: конъюнкцию можно

выразить формулой: p q , импликацию формулой p q, эквиваленцию формулой p q q p .

2) Введем обычным образом две операции, например, импликацию и конъюнкцию. Тогда: отрицание можно

выразить формулой p 0, дизъюнкцию формулой	(p 0)	q, эквиваленцию формулой	(p q) (q
p).

№3.2. 13. Отрицание: «Завтра будет хорошая погода, и мы не посетим музей и выставку современного дизайна, и не пойдем в лес за грибами».

№3.2. 15.. Указание. Записать соответствующие формулы и привести их к одинаковому виду.

22

№ 3.2. 16.

а) p q p r q r q r ≡ (это ДНФ) ≡ p q r (это КНФ).

б)

(p ↔ q) p q ≡ p q p q ≡ (это ДНФ) ≡( p q)( q p) (это КНФ).

в) (p → q) (q →

) ≡

.

p

p

г)

(p → q) p ≡ 1.

p

q

д)

↔ (q → p r ) ≡ p q

(это ДНФ).

p

r

p

q

е) p q →

q r ≡

.

p r

p

q

ж) p

≡ 0.

q p q

з)

↔

q ≡ (p q)(

) (это КНФ).

pq

p

p

q

и) p q p q q p ≡ p

к) p → ( q → p r) ≡ p q.

л) ((p q) (p r)) (p (q r)) ≡ 1

м) (p q) ((r q) (pr q )) ≡ p r q .

н) (p (q r)) ((p q) (p r)) ≡ 1 о) (pq r) (p (q r)) ≡ 1

п) (p q q) (p q) ≡ 1

р) ( p p ) p p ≡ 1.

№ 3.2. 17.

Каждой формуле соответствует таблица истинности, следовательно, каждой таблице истинности соответствует некоторая формула. Восстановить формулу можно двумя способами:

С помощью СКНФ или с помощью СДНФ. 1. СКНФ.

В таблице истинности выделяются строки, в которых формула ложна. Каждой такой строке будет соответствовать единственная элементарная сумма СКНФ. В эту сумму высказывание истинное будет входить с отрицанием, а высказывание, которое ложно - без отрицания. Это объясняется тем, что элементарная сумма должна быть ложной, а если в нее будут входить истинные высказывания, то она ложной не будет. Составляя СКНФ из этих строк, мы получим исходную формулу.

Пример: дана таблица

	р	q	r	Ф
1	1	1	1	1
2	1	1	0	0
3	1	0	1	1
4	0	1	1	0
5	1	0	0	1
6	0	1	0	1
7	0	0	1	0
8	0	0	0	1

Так как во 2-ой строке функция ложна, то должна быть ложна элементарная сумма. А элементарная сумма ложна тогда, когда каждый ее член равен 0.

Т. к. р = 1, то p = 0; и в дизъюнкцию должно входить p .

Т. к. q = 1, то q =0; и в дизъюнкцию должно входить q . r = 0 - без отрицания.

Получим: p q r.

Аналогично

Для 4-ой строки: р q r

Для 7-ой строки: р q r . Тогда

Ф = ( p q r) (р q r )( р q r ). 2. СДНФ.

В таблице истинности выделяются строки, в которых формула истинна. Каждой такой строке поставим в соответствие элементарное произведение, которое должно быть истинно. В это произведение истинные высказы-

23

вания входят без отрицания, а ложные - с отрицанием. Затем составляется дизъюнкция элементарных произведений.

Для нашего примера:

Ф= рqr р q r р q r p q r p q .

Замечание Полученные формулы можно преобразовать в импликацию и т.д.

№ 3.2. 19. Высказывание и его отрицание будем называть литералом. Дизъюнкцию литералов будем называть элементарной суммой, а конъюнкцию литералов будем называть элементарным произведением. Преобразуем каждую из формул в ДНФ (или КНФ), а затем в СДНФ (СКНФ).

Для преобразования ДНФ в СДНФ нужно в элементарное произведение, в котором нет какого-нибудь литерала, добавить 1 в виде дизъюнкции этого литерала со своим отрицанием, а затем раскрыть скобки.

Для преобразования КНФ в СКНФ нужно в элементарную сумму, в которой нет какого-нибудь литерала, добавить 0 в виде конъюнкции этого литерала со своим отрицанием, а затем воспользоваться вторым законом дистрибутивности.

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

Решение.

Рассмотрим формулы:

1. Ф1 = (p r ) ( q r) ≡ (p r ) ( q r) (r q ) ≡

≡ ( p r ) (q r) ( r

q ). Получили КНФ. Приведем ее к ДНФ, раскрывая скобки.

Ф1= (

q

r q

r(=0))(

) ≡

q

q

(=0)

r

(=0)

r

q

r

0

p

p

r

r

r

q

p

r

p

q

p

r

p

q

r

r

p

q

≡

q

r

q

. ((Это ДНФ. Преобразуем в СДНФ) ≡

q

r

(p

)

q

≡

q

r

p

r

p

q

r

p

r

p

q

p

r

p

r

p

q

p q

q

≡

q

r

p q

. Это СДНФ.

r

p

r

p

r

p

q

r

2.Ф2 = q r p q r (это ДНФ. Преобразуем в СДНФ) ≡

(p p ) q r p q r ≡ p q r p q r p q r . Это СДНФ.

Сравнивая СДНФ формул Ф1 и Ф2, видим, что они одинаковы. Значит, формулы равносильны. 3.Ф3 = ( p q) ( q r ) ≡ p q p r q q (=0) q r ≡

≡ p q (r r ) p (q q ) r (p p ) q r ≡

p q r p q r p q r p q r p q r p q r r ≡

≡ p q r p q r p q r p q r . Это СДНФ.

Сравнивая СДНФ формул Ф3 и Ф1(или Ф2), видим, что они не одинаковы. Значит, формулы не равносильны. № 3.2. 20. а). Решение. Введем обозначения: НБ - Набоков-бухгалтер, НК- Набоков-кассир, НСНабоковсчетовод, МБ - Матвеев-бухгалтер, МК- Матвеев-кассир, МС-Матвеев-счетовод, ЛБ - Левинбухгалтер, ЛК-

Левин-кассир, ЛС- -Левин-счетовод,.

Запишем формулы, соответствующие высказываниям.

НК → МС, НС→ МБ, МК → ЛС , ЛБ → НС.

Характеристическое уравнение имеет вид:

(НК → МС) (НС→ МБ) ( МК → ЛС ) (ЛБ → НС) = 1.

Преобразуем левую часть.

( НК МС) ( НС МБ) (МК ЛС ) ( ЛБ НС) = 1.

Преобразуем в ДНФ.

(

МБ МС

МСМБ(=0))(МК

МКНС

НС) =1. Раскроем скоб-

НК

НС

НК

НС

ЛБ

ЛС

ЛБ

ЛС

ки.

НК

МК

НК

МК

НС

НК

НК

НС

НК

МБ

НС

ЛБ

НС

НС

ЛС

ЛБ

НС

ЛС

МК ЛБ НК МБ МК НС НК МБ ЛС ЛБ НК МБ ЛС НС МС НС МК ЛБ МС НС

МК НС

МС

МС

НС =1, Дизъюнкция равна 1, если хотя бы один её член равен 1.

НС

ЛС

ЛБ

НС

ЛС

.1.

НК

НС

МК

ЛБ

=1. Отсюда:

Набоков-бухгалтер, Матвеев-кассир, следовательно, Левин-счетовод.

2.

МК НС = 0, т.к.

НС = 0.

НК

НС

НС

3.

= 1. Отсюда: Набоков-бухгалтер, Левин-кассир, следовательно, Матвеев-счетовод.

НК

НС

ЛС

ЛБ

4.

НК

НС

ЛС

НС = 0, т.к.

НС

НС = 0.

5.НК МБ МК ЛБ = 0, т.к. МБ МК – 0.

6.НК МБ МК НС = 0, т.кК. МБ МК – 0.

7.НС МБ ЛС ЛБ = 1. Отсюда Матвеев-бухгалтер, Левин - кассир, следовательно, Набоков - счетовод. Но