24

Набоков не счетовод. Т.о. уравнение не имеет решений.

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

9.МС НС МК ЛБ = 0, т.к. МС МК= 0.

10.МС НС МК НС = 0, т.к. НС НС = 0.

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

12.МС НС ЛС НС = 0, т.к. НС НС = 0.

Ответ.

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

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

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

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

б) 1. Ева и Эмма . 2. охраны нет.

в) 11000 11010 01101 11001 г) 10001111 д) 11011.

е) Да. ж) В и С.

№3.2. 21. Указание. Составить формулу, соответствующую рассуждению и приведением к КНФ доказать, что она тождественно истинна.

№3.2. 22.

1.Рассуждение неверное.

2.Рассуждение неверное.

3.Формализуем рассуждение. Пусть p - стороны треугольника равны, q – треугольник равнобедренный, r - углы при основании равны. Рассуждение принимает вид: p q, q r, p ├ r.

Построим вывод. (Вывод – это последовательность формул, каждая из которых является либо посылкой, либо получается из предыдущих формул по правилам вывода, причем последней формулой должно быть заключение.)

1.p q - посылка.

2.p – посылка.

3.q из 1 и 2 по ПЗ.

4.q r – посылка.

5.r из 4 и 3 по ПЗ. Рассуждение верное.

4Рассуждение верное.

5Рассуждение верное.

7.Рассуждение верное.

8.Рассуждение неверное.

9.Рассуждение неверное.

10.Рассуждение верное.

11.Рассуждение верное

12.Рассуждение верное.

13.Рассуждение верное.

14.Рассуждение верное.

15.Рассуждение верное.

16.Рассуждение верное.

3.4. Предикаты

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

местностью.

Одноместные предикаты выражают свойство объекта – быть чем-то. Предикат большей местности выражают отношения между объектами (равно, больше, принадлежит, лежит против, и т.д.).

0-местный предикат – это высказывание.

Если предметной переменной задать значение, то получим предикат меньшей местности.

Навешивание квантора всеобщности ( ), квантора существования ( ), квантора существования и единственности ( !) понижает местность предиката. Предметная переменная, по которой навешен квантор, называется связанной этим квантором, а остальные переменные называются свободными.

Множество МР наборов значений, при которых предикат Р (…) равен 1, называется областью истинности данного предиката.

25

№ 3.4. 1. В приведен-

ных функциях заменить переменные значениями так, чтобы получи-

лись истинные высказы-

вания.

а) x – президент Рос-

сии.

!г-элементное

множествоА

, то

б) число x делится на 3

и на y.

(x)

(x) А В(

в) число x – больше 7, но меньше y.

дикатов (различных) типа А

На множестве (О, и1) 3черезоп

г) неверно, что А старше В, но моложе С.

Р(x, y,

д) число x расположено между y и z.

«X делит y» определено

Составить таблицу значений

№ 3.4. 2. Бинарное отношение (двухместный предикат) P(x, y):

на множестве А2, где А = {2, 3, 4, 5, 6}. Составить прямоугольную таблицу, задающую этот

область истинности.

предикат, и определить его область истинности.

118. Двуместный предика

2

. Соста-

10, определен на множ

№ 3.4. 3. Пусть А = {1, 2, 3, 4, 5, 6, 7}. Предикат P(x, y) определен на множестве А

5, 6, 7}. Составить таб

вить

прямоугольную таблицу,

ката и определить его

задающую этот предикат, и опре-

рить то же для предика

делить его область истинности,венством x + y < 10.

если

119. Двуместный предик

1. P(x, y): x + y = 10.

LЗ, где A={l, 2, 3, 4, 5}, аВ=(3

2. P(x, y): x + y < 10.

ний этого предиката и опреде

№

3.4. 4. На диаграмме (рис.повторить для предиката x < y,

19): А = М [А (x)]; В = М [В (x)], С = М [С (x)], т. е.

области истинности обозначаются теми же бук-

вами, что и предикаты. Заштриховать область ис-

тинности предиката:

В (x) С (x);

а) А (x) V В (x) V С (x);

б) А (x)

в) А (x) В (x)

;

г) А (x)

С (x);

С(х)

В(х)

д)

В (x) С (x);

е) А (x)

/\

,

А(х)

В(х)

С(х)

ж)

В (x)

;

з)

) \ С (x);

А(х)

С(х)

А(х)

В(х)

и)

.

А(х)

В(х)

С(х)

Рис. 19. Заданные множества

№3.4. 5. Записать предикаты, области истинности которых заштрихованы на рис. 20 -28, (обозначения задачи

№3.4.4.)

Рис. 20

Рис. 21

Рис. 22

Рис 23

Рис 24

Рис. 25

Рис. 26

Рис. 27

Рис. 28

№ 3.4. 6. Предикаты А(x) и В(x) определены на некотором множестве М. В каком отношении должны находиться области истинности А и В этих предикатов, чтобы:

А(x) В (x) принимал значение 1 а) для некоторых x из М;

б) для всех x из А; в) для всех x из В;

26

г) ни для одного значения x из М (принимал значение 0 при всех значениях x из М);

№ 3.4. 7. В приведенных функциях навесить кванторы так, чтобы получились истинные высказывания. а) x - автор романа y.

б) город x расположен на берегу реки y. в) река x впадает в y.

г) студент x учится на факультете y вуза z.

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

3.4. 8. Определить, являются ли нижеследующие последовательности символов формулами логики предикатов:

а) ( x)P(x, y) → ( z)Q(y, г) R(y,t); б) ( x)A(x, y) ( y) В(x, y);

в) ( x) y) S(x, y, г) → (' x) ( y)P(x, y).

№ 3.4. 9. Пусть заданы предикаты С(x, y, z) = ( x + y = z ) и Р(x, y, z) = = (x * y = z). Записать формулу с одной свободной переменной, истинную тогда и только тогда, когда

а) x = 1, б) x = 0, в) x = 2, г) x – четное число, д) x – нечетное число, е) x – простое число.

№3.4. 10. Пусть N(x) - предикат «x - натуральное число» (x N); С(x) - предикат «x - целое число» (x C); Р(x)

-предикат «x - простое число»; В(x) - предикат «x - положительное число»; Т(x) - предикат «x - четное число»; D(x, y) - предикат «x делит y».

Сформулировать словесно записанные ниже на языке логики предикатов высказывания и указать, какие из них истинны, какие ложны:

а) ( x) [N(x) → С(x)];	б) ( x)[N(x) С(x)];		в) ( x) C(x) → N(x)];
г) ( x) [С(x) В(x) ↔ N(x)];		д) ( x) [С(x) →			T(x)];
				Т (Х )
е) ( x) ( y) [С(x) С(y) → D(x, y)];
ж) ( y) ( x) [С(x) С(y) → D(x, Y)];
з) ( x) ( y) [С(x) С(y) → D(x, y)];
и) ( x, y) [Т(x) Т(y) → D(x, y)];
к) ( x)[Р(x) Т(x)];	л) ( x)[P(x) → Т(x)].

№3.4. 11. Пусть С (х) - предикат «х - составное число»; R(x, y) - предикат «x меньше y»; S(x, y, z) - предикат x

+y = z; Р(x, y, z) - предикат x∙y = г. Используя введенные обозначения, записать на языке логики предикатов, следующие предложения:

а) для всяких целых чисел x, y существует целое число z такое, что							x + y = z.
б) Для всяких двух целых чисел не существует более одного целого числа, равного их сумме.
в) Для всяких целых чисел х, y, z, если х + y = z, то y + х = z.
r) Для всяких целых чисел х, y существует целое число z такое, что x∙y = z.
д) Для любых двух целых чисел не существуют более одного целого числа, равного их произведению.
е) Для всяких целых чисел x, y, z, если x∙y = z, то y∙x = z.
ж)	Для	всяких	целых	x,	z	существует	целое	число	y	такое,	что
x + y = z.
з) Для всяких x, таких, что			x меньше y, если и только если существует натуральное число k такое, что x + k =

y.

и) Для всякого x, x - составное число, если и только если существуют числа y, z, меньшие x и такие, что y∙z =

x.

з) Для всяких двух рациональных чисел x, y, если x < y, то существует рациональное число z такое, что x < z и z < y.

№3.4. 12. Сформулировать теорему. Ввести необходимые предикаты (можно использовать принятые в математике) и записать в виде формулы логики предикатов:

1) первый признак равенства треугольников.

2) первый признак подобия треугольников.

3) признак перпендикулярности прямой и плоскости.

4) признак перпендикулярности плоскостей.

5) второй признак равенства треугольников.

6) второй признак подобия треугольников.

7) необходимый и достаточный признак делимости натурального числа на 6. 8) необходимый и достаточный признак делимости натурального числа на 5. 9) признак параллельности двух плоскостей.

10) один из признаков параллельности прямых на плоскости.

11) третий признак равенства треугольников.

12) третий признак подобия треугольников.

13) свойство двух прямых, параллельных третьей.

№3.4. 13. Выразить на языке логики предикатов следующие высказывания:

а) Существует, по крайней мере, один предмет, обладающий свойством Р (выражение «существует, по крайней мере, один предмет» понимается в том же смысле, что «существует предмет»).

27

б) Не существует предмета, обладающего свойством Р (или «неверно, что существует предмет, обладающий
свойством Р»).
в) Не существует более одного предмета, обладающего свойством Р (или «существует не	Доказать, что если epl:==ep2
более одного предмета, обладающего свойством Р»).	132. Записать в виде ф
	Доказать общезначимость пр
г) Существует точно один предмет, обладающий свойством Р («существует предмет, обла-	до132вой. планиметрииЗаписатьв видеслф
	(1) - (8).
дающий свойством Р, и не существует более одного предмета, обладающего этим свой-	сущестдовой планиметриивуетболее однойв сл
	140. Доказать общез
ством»).	дящейсу стчерезвуетболееточкуоднойвне
	- (12) омадящейпараллельностичерез точку внеплан
д) Существует, по крайней мере, два предмета, обладающих свойством Р (или «существуют	(установить, что в каждой и
два различных предмета, каждый из которых обладает свойством Р»).	формулыома параллельноспрочитатьи пласл
	ности основанияlim f(x) = включаетсяl == (уе> О)
	скогоформулы.	и прочитать сл
е) Существуют не более двух предметов, обладающих свойством Р (или «для всяких трехпоэтому{(хнельзя)-		найти таких з
предметов x, y, z если каждый из них обладает свойством Р, то x = z или y = z »).	ского133. Прочитать словам
	при которых основаниех- х. Dfбыло
	133. Прочитать словам
ж) Существует точно два предмета, обладающих свойством Р (или «существует, по крайнейным). -/1<8].
мере, два предмета, обладающих свойством Р, и не существует более двух предметов, обла-	141. Доказать, что если фор
дающих этим свойством»).	Построить отрицание
	держащая в качестве свободн
	сформулировать словами
	134. Какая из нижесле
№ 3.4. 14. Пусть А, В, С - переменные для точек; a, b, c -переменные для прямых'; * - знакобщезначимой, то и формула (
	х .хо
	пе		.
отношения «инцидентно» ("лежит на", "проходит через"), применимого к точке и прямой (А *чимой, и обратно\
а). Используя эти обозначения, записать в виде формул логики предикатов следующие гео-	142. Если формула) (ух) (з/)логики[{(х + 1п
	риодической функции
метрические предложения (аксиомы, характеризующие предикат «инцидентно» на плоско-честве свободной{(х)]?				только пре
сти):	общезначимойПостроить, то иотрицаниеформула (
а) Для любых двух точек существует прямая, инцидентная им.	чимойславами. Верно ли. обратное?
б) Для любых двух различных точек не существуют более одной прямой, инцидентной им.	143. Доказать135. Какое, чтосвойство:				ф
в) Для любой прямой существуют, по крайней мере, две точки, инцидентные ей.	а) еслилы формула логики пред

г) Существуют три точки, не инцидентные одной прямой (т. е. такие, что не существует пря-(ух) ер =>(УХ(ух],)х'2)Ф [их]f-<(зхХ2) ер=>={

мой, инцидентной каждой из этих точек).	(ух) ер <=>Построить(ух) 'Ф иотрицаниеf- (зх) ер <
д) Для любых двух различных прямых не существует более одной точки, инцидентной каж-	144. Доказать, что нижесле
дой из этих прямых.	общезначимыми136. Записать(подобратьв виде фт

3.4. 15. Построить отрицания следующих высказываний и прочитать их словами (x, y, z, r -менныхнотонно, при которыхубывающаяоснова».

переменные для вещественных чисел):

ствие ложнопрочитать): его словами.

а) ( x, y)[x>y x<y x=y];

а) (уу) (зх) р (х, у) =>

б) ( x)( y)[

→ x+ y = x];

137. Записать в виде ф

y 0

V Qшее(х) )значение=> (ух) Рфункции(х) V (ухf)

в) ( x, y) ( z)[ x y z ( r) (x+ y = r z r )].

=> (эхпрочи) [Р (хтать) 1\ Qего(хсловами»); г) [(ух.

г) ( x, y) [x2 + y2 >0];

=> => Q (х»); д) (зх) р (х) => (у

___________________

Доказать, что если epl:==ep2

д) ( x, y)[

x2 y2 x y ].

Доказать общезначимость пр

№ 3.4. 16. Пусть C(х, у) - предикат «х делит у», а x, y - переменные для целых чисел. Сфор-

(1) - (8).

мулировать словами предложение, выраженное формулой

Доказать

общез

- (12)

( x, y) [ C (3, x) C (3, y) → C (3, х+у)].

(установить, что в каждой и

Построить отрицание этого предложения и прочитать его словами.

№ 3.4. 17.

Какая из нижеследующих формул выражает определение периодической функ-ности основания включается

ции:

поэтому нельзя найти таких з

при которых основание было

а) ( x) ( l) [f(х + l) = f(х)];

б) ( l) ( x) [f(х + l) = f(х)].

ным).

Построить отрицание этого определения и сформулировать его славами.

Доказать, что если формула

№ 3.4. 18. Какое свойство функции f выражается с помощью формулы ( x1, x2) [х1 < Х2

→ f (х1) < f (х2)]?

жащая в качестве свободной т

щезначимой, то и формула (у х

Построить отрицание этой формулы и прочитать его словами.

№ 3.4. 19.

Какое свойство функции f выражается с помощью формулы ( x1, x2) [х1 < Х2мой, и обратно.

→ f (х1) > f (х2)]?

Если формула логики преди

свободной только предметную

Построить отрицание этой формулы и прочитать его словами.

№ 3.4. 20.

Записать в виде формулы высказывание «Функция f - монотонно убывающая».чимой, то и формула (эх) ер

Построить отрицание этой формулы и прочитать его словами.

Верно ли обратное?

Доказать, что:

№ 3.4. 21.

Записать в виде формулы высказывание «f(х0) - наибольшее значение функции

f». Построить отрицание этой формулы и прочитать его словами.

а) если формула логики пред

№ 3.4. 22. Доказать, что если формула логики предикатов φ (x), содержащая в качестве сво-(ух) ер => (ух) 'Ф и f- (зх) ер =

	бодной только переменную x, является общезначимой, то и формула ( x) φ (x) также являет-(ух) ер <=> (ух) 'Ф и f- (зх) ер <
	ся общезначимой, и обратно.	Доказать, что нижеследую
	№ 3.4. 23. Если формула логики предикатов φ (x), содержащая в качестве свободной толькощезначимыми (подобрать таки
	предметную переменную x, является общезначимой, то и формула ( x) φ (x) также являетсяных. при которых основание
	общезначимой. Верно ли обратное?	ложно):
		а) (уу) (зх) р (х, у) =>
	№ 3.4. 24. Доказать, что:
	а) если формула логики предикатов φ (x) → ψ (x) общезначима, то формула ( x) φ (x) →	V Q (х) ) => (ух) Р (х) V (ух)
	( x) ψ (x) и ( x) φ (x) → ( x) ψ (x) общезначимы.	=> (эх) [Р (х) 1\ Q (х»); г) [(ух

=> => Q (х»); д) (зх) р (х) => (у