книги / Основы дискретной математики

- 31 -

ч) X & i f v t & z => X 4 y V x & y S z v x & y & Z ;

ш) ((х ф у ) ф х А у ) v z s у Y х А у 4 z i

Q) ( X t y ) ^ ( X - t / V Z ) ;

Э) f i B ( y i z ) :

Ю) ((*=> y J i Z )=>y<

26. Получить и щ а ДЛЯ функции:

а) ( ( x a g ) = > z ) ~ Z ,
б)	Q SC(A SC D V а & (&	C ))i
В)	(A * C ) v ( & => C J Sr (A =>c);
r) A S в V e s c v (A 4		$),

Д)	( x a y ) t ( y a z J;
e)	A * ( C i 2 ) v ( A * C ) S r $ ;

*>	( x i y ) y (Х*!/)* У * Z i
a) ( A ~ 8 ) * ( C 4 A ) i
и) X j j j * 2 = X ~ Z i
к)	( X V Z )Sf ( X a y ) ~ Z ,
A) X V y S z =3 x ~ Z i
*>	(Av 3 ) ~ ( A t C ) ;

п) { x i t j ) v ( x i y ) y y 6 z ,

р) (*а y ) * z v X ’

с) х ~ у = > х ; т) л => Ь ~ с ^ а ,

У>

ф) XVJ/&Z V *i<£,

X) A d С vBSCvASe&ir£,

ц) ( x t y J S ( x ~ y v z ) ;

ч)	у * ( t *	Z ) .
Ш)	A i ( A i c C a	3);

щ) (A~ 8 ) ^ ( С 4 A )

a)(A =>&)=> (A =>E),

o)x & y A z v xAySci vxStjjScZv кA y S z v x S 9 S Z i

27. Доказать неполноту систем функций:

а)	Г * , к, => } ;		а)	{ i }		■
28.	Доказать полноту систем функций:
a) { л , V, -1 i ;				д) { / } ;
6)	{ У>	7>;		е) { ( У ;
в)	{ Л ,	73.		ж)	{=>. о } ,
г)	С=>.	73;		з)	{ Ф ,	у, /j\

29. Являются ля системы функционально полными:

а) { 9 , ~ у .	0) { * , - } ;	8) С * . * } ?
30. Начертить схему,	считая, что а контактной схеш каж­

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

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

б) схема замыкается тогда, когда из 8 расположенных в определенном порядке переключателей замкнуты какие-то 4 после­ довательных (и никакие другие не замкнуты);

P (x t.x2, ...,

32

	31.	Из контактов			х ,у. z	составить схему		так,	чтобы она зам
	жцух&сь тогда я только тогда,						когда замкнуты	какие-нибудь два
	кз трех контактов			д, у. Z .
	Таблица 2.9				32.		Построить схему, соответствующую
					формуле и , заданной таблицей истинное??,
	X У		Z	и	(табл.		2*9).
					33. Составить релейно-контактную
				*\
	0	0	0		схему для функций:
				W
	0	0	I	I	а) (х = > у ) 4 ( у = г ) ;
					б)		((х=>у)&(У^г))=>(х=> z),
	0	1	0	I
					в)		(ж» у)э (%& (yv2)).
	У	«	I	0	г)		(к => ( у => z ) ) => (у=> Z).
		-*
	т	0	0	I	34. Начертить схему для функции,
	1				упростить эту функцию и начертить схему
	т	0	т	0
					упрощенной функции:
	♦		ж
	J.	X 0		0	a) a & S d C 6, € у £<£ c & d				4 f ,
	I	I	I	0	й) CL V CL it & 4 C ;
					z) a v { g v c ) & d v ( c v d v j 4 A J 4 ( a . v d \ / 2 ) 4 { €
	35.	Упростить		схемы (рис.		2.1).

2.2. Логика дрддркятоа

Предикатом P(*h xv ,..tхп) называется		сложное высказывание,
в котором переменные х г л2,...,хп	могут	принимать значения	из
некоторой вещественной области,	а само	висказыэаяие может	быть

жстенны м или ложным. В алгебре предикатов справедливы все опе­ рации алгебры высказываний, кроме того, вводятся операции наве­ шивания кванторов:

1. Квантор всеобщности V . V* Р(х) - читается "для всех

Лсправедливо Р (*)".

2.Квантор существования. 3% Pf*) - "есть такой х ,

что справедливо Р(х) " .

Предикаты, у которых одна переменная, называются одномест­ ными предикатами. Предикаты, у которых/г переменных, называют­ ся /? -местными предикатами. Предикат вида х п ) -

- 53 -

мементарнчй предикат. С помощью операций алгебры предикатов

можно подучать сложные предикаты. Расположение операций алгебры предикатов в порядке убывания силы связывания следующее:

Q t Sft v,		, где Q - символ квантора. Основные равносильное
ти логики предикатов:
1.	7 Уд Р ( х ) * J x 7 Р (х ) i
2.	1 З х Р ( х ) s V* 7 Р ( х ) ,
3.	1 3 x 1 Р ( х ) з V x Р ( х ) ;
4.	7*х	1 Р ( х ) з З х Р ( х ) \
5.	Vx Р ( х ) v Q з у х С Р ( к ) v ( И ,
6.	Зх Р (t) Ь Q*3i'CP(*) * СИ.
1. \ f x P ( x ) A Q s V* t P ( x ) A Q l ;
8.	3 x P { x ) v Q - З х ( P ( X ) Y Q I .

9.V x Q * Q ,

10.3 * Q z Q ,

11.Vx ( P ( x ) A P (x)) 5 v* P ( x ) Sc Vx R ( x ) i

12. 3 x ( P ( x ) м # ( * ) ) s j x P ( x ) v 3 x (Ц *) ;

13.Vx P(%) ш Vy P ( y ) i

14.3 x P ( x ) s 3 y P ( y ) ,

где Q не зависит от X.

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

Q , A . V . l , причем 7 стоит перед элементарным предикатом. Нор­ мальная форма представления предиката — такая приведенная форма, в которой символы навешивания кванторов либо отсутствуют, либо выполняются в последнюю очередь.

Предикат будем называть тождественно-истинным (тавтоло­ гией, общезначимым), воли он истинен при любых значениях сво­ бодных переменных. Предикат будем называть выполнимым, «если есть такие значения свободных переменных, на которых данный предикат истинен. Предикат будем называть тождественно-ложным (противоречием), если на любых наборах значений переменных он принимает значение "ложь".

36.Записать на языке предикатов;

	а)		если деталь обеспечена заготовкой, включена в план и
для	нее	есть оснастка,		которая может быть использована при об­
работке		данной детали,		то эту деталь нельзя оставлять на складе
или	назначить		неопытному рабочему;

- 34 - б) если есть такой диск, на котором расположен массив, и

этот массив имеет индексно-последовательную структуру, то име­ ется на диске зона индексов, соответствующая данному маосиду; в) все кошки имеют усы и хвост, любят молоко и рыбу и если

кошки, кроме того, рычат, то эти кошки - тигры; г) неверно, что 2x2=5;

д) если некоторые ахи не являются охами, то некоторые эхи являются ахами;

е) если нельзя решить задачу на данной ЭВМ, и задача явля­ ется важной для пользователя, то надо разбить эту задачу на под­ задачи или убедить пользователя в том, что решать эту задачу не имеет смысла.

37.Являются ли тождественно-истинными следующие предикаты:

а)	Зх Р(х) =>ЧхР (x)i		в) Эх V yQ (x,у ) => V y Jx Q (*t y )i
d)	1 (З к Р (* )= Ч * P (*);		г)	\/* 3 y Q (/,y )= 3 y V x Q (* .y )?
	33. Выполнимы ли следующие предикаты:
а)	Эх Р (х);			д)	Зх ^ у Ш ^ ,у )= * ^		&(** У* *))•
d)	V x P ( x ) ,			в)	(ffi) =>vgP(g))>
в)	jx V y ( Q ( x , y ) £ i Q ( * , y ) ) ;			к)	Vx V g(P(x)v	7 P	( g l ?
r) J x 3 y ( P ( x ) £ I P f g J J ;
	39.	Привести к нормальной форме предикаты:
	а)	v « 1 3 у (Р (х )= > в (д )):
	б) Эх ( ’\ 4 y P ( x ly ,z ) = B u Q ( x ,u . $ S e 4 t 3 'r l ( A ( t ) v b C 'r ) ) i
	в)	Зх Vy Р(х. у ) v3x V у G (x , y j ;
	г) 3 x V y P ( x , y J * 3 x \ / y G ( x , y J -
	40. Доказать или опровергнуть, что
	а)	Vx (P(x)SeQ (x)) = VxP (x)& V xQ (x ) ;
	б)	Vx (P(x)vQ (x)) s V tP (x) v Vx Q (* )i
	в)	<*(*))= 3 x P ( * ) & 3 % Q ( x ) i
	p)	3% (P (x )v Q (x))& 3 t P ( x ) v 3 x Q ( * ) '
	Л)	Vx (P (x)=>Q (x))s	Vx P(x)z> Vx Q (* )•'
	в)	Зх (P(x) о Q(%)) s	3 x P (* )= 3 x Q l* ).
	41. Пусть A - шсказывательная форма, несодержащая свобод­
ной переменной д . Доказать или опровергнуть,						что
	а) V * ( A 4 6 ( X ) ) Z A 4 V X B ( X ) ;
	б) V x ( A v 8 ( x ) ) * A y / V x 5 ( x ) i
	в)	3 x(A Sc в ( х ) ) г А & З х в (к );
	г)	Зх (A V & (X )) Z A V 3 X		3 (ж),
	д)	Vx (А =• 5(х))ш А => Vx 5 (*)i
	е)	3 X (5 (X ) * A ) г З х б ( х ) = * А ;

C 0 . 1 J , сохраняет

		- 35 -
*)	tfx (&(*)=* A ) =	V* & (* ) =>4 *
3)	3 x (A => 3 fx)) S A a 3 x>; 6 f x j •
42.	Ввести предикаты	на соответствующих областях и записать

при их помощи следующие высказывания в виде формул логики пре*

дакатов:

а) если об - корень полинома от одной переменной с вещест­ венными коэффициентами, то <2 - также корень этого полинома;

б) между любыми двумя различными точками на прямой лежит, по крайней мере, одна точка, с ними не совпадающая;

в) через две различные точки проходит единственная прямая;

V г) каждый студент выполнил, по крайней мере, одну лаборатор­ ную работу;

д) если произведение натуральных чисел делится на простое число, то на него делится, по крайней мере, один яэ сомножителей;

е) через три точки, не лежащие на одной прямой, проходит единственная плоскость.

43. Ввести одноместные предикаты на соответствующих облас­ тях и записать при их помощи следующие высказывания в виде фор­ мул логики предикатов;

а) всякое натуральное число, делящееся на 12, делится на 2,4 и 6;

0) жители Швейцария обязательно владеют или французским, или итальянским, или немецким языком;

в) функция, непрерывная на отрезке знак или принимает нулевое значение.

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

44.Показать, что разноименные кванторы в общем случае нельзя переставлять местами.

45.Придумать содержательное описание формулы. Привести к

нормальной формуле к прочитать:

а>	1 4 * (P (x )z > 1 3 y V £ (ia (M ty , Z ) v L
	(Зу	Р (* , у)	э v z СЦг)) = З у ,		У);
В)	1 V * 3 y V x ( P		( X ,y ) = >	(x , z t >"))i

г) которая содержала бы один квантор общности, три кванто­ ра существования и две операции импликация.

46. Какие вхождения переменных являются свободными, а какие связанными в следующих формулах:

- 3 6 -

а) V * 3 y (P $ y ,l)v Q (* ,y ,z ));b ) V*3yR(*.y,x )& Q (* ,y ,z)

б) v* (P(*)V VyJ* Q (ж, ytz)i Г)	3yR(*.y,Z) V* Vy Q(x,у,z)?
47. Привести содержательные	примеры одно-, двух-, трех- и

четырехместных предикатов.

Формальная (аксиоматическая) теория считается определенной, если заданы:

1)некоторое счетное множество символов теории. Лонечные последовательности символов образуют выражения;

2)подмножество выражений теории, называемых формулами;

3)некоторое подмножество формул объявляется аксиомами

теории;

4)конечное множество отношений между формулами, называе­ мых правилами вывода.

Выводом в теории называется всякая последовательность фор­

мул Л Я	п , при которой каждая из этих формул либо является
аксиомой, либо следует из некоторых предыдущих формул по одно­
му из правил вывода»
Формула Я		теории называется теоремой теории ( t h							<#.)		или
выводимой в данной теории,			если в теории существует						такой вывод,
в котором последней формулой является Л						•
Дусть Г		- множество формул теории. Вывод из						гипотез			-
это такая последовательность формул S f, ...,							, при которой каж­
дая из формул является либо аксиомой, либо гипотезой,										либо сле­
дует из предыдущих по правилу вывода. Теперь выведем формаль­
ную аковоматичеохую теорию для исчисления высказываний.
1. Символами теории являются:				( * )	,	*7, г> и		буквы.
2. а) все буквы суть формулы;
б)		если Л	и Я — формулы,			* o ( l A )		ъ(<А z>$) 10ж& форму
лы.
3. Следующие формулы являются аксиомами: (At).Я									=>(£		я );
(А2). (Я * (Я = & ])* в Я ?J0;=> (А=>ЪЪ				(А5).						(&=> Л )-
4. Правилом вывода служит правило					m odus f>onenz(MP)\
Jb есть непосредственное следствие				Я	и	А	=> -S .
		Теорема дедукции
&сли	Г -	множество формул, А		и J9		-	формулы и			Г 9 Я hJb
то Г h Я	-=> ЗЬ	. В частном	случае,	если	Я г		Jh	, то		h Я	19 ЗЬ

- 37 -

Построим аксиоматическую теорию первого порядка.

I . Символы теории:

I f

V,

3 ,

( у ) ;

вещественные переменные

ж , у

, z t ... ;

вещественные постоянные

a

t S

, с * *..;

предикатные

буквы

Р

. #

функциональные

буквы

.

Вещественные переменные и вещественные постоянные являют­

ся термами. Если

X,,

, ... ,

- термы,

то

f ( x r fi2...* J -

тоже

терм. Кроме упомянутых термов других термов быть не может.

2 . Формулы. Выражение вида

P ( t f , t z * ' '

» t п ) , где

~

термы, является элементарной формулой. Если ^

YL ЗЬ - форму/ .,

то

( ~ 1 £ ) , ( Я = > Я ) , ( * л А

) , ( Э

ж Я )

- тоже формулы.

3.

Система

аксиом:

(A.I)

о

( Л = > А ) .

(А.2)

( Я = > ( £ = > & ) ) * ( ( *

=>Я ) = > ( л = > & ) )

(А.З)

( 1

Л

~

1

(Я>=> Л ) -

(А.4)

Vx Я ( х )

Я { 4 ) -

(А.5)

Я

(t )

^

Э х

Я

Гх),

где

i

- терм,

свободный для

ж

(т.е. никакое

свободное

вхож­

дение ж в формулу Я

не лежит в области действия никакого кван­

тора

Vy » здесь

у - переменная,

входящая в

£

).

4.

Правила вывода:

(* I)

=> ЗЬ, Я h ЗЬ - m o d u s

p o n e n s

\R 2) 3b

Я(*) ь- Я ^ Vx Я (*)- правило обобщений.

(A* 3)

Я(*)=> Л

/-

3 Л — правило конкретжэашш.

Л- предикат, не содержащий свободных вхождений ж . Собственные аксиомы - это аксиомы, которые меняются от тео­

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

48.	Доказать выводимость на гипотез :
а) А * & , 8> => С t- А => С .
б)	Г, А, В!~ К А => 1 В);
в)
Г)	Г . А . 1 &t- 1(А => &);
Д)	А =>(А =*В), (А=> в ) =* С t~A » С.

-38 -

49.Используя теорвцу о дедукции, показать:

а)	t(A =>b)= ( ( В * с ) э ( А ^ С ) ) ;
б) \ - ( а * 1 Ь ) ^ ( Ь = > ~ \ А ) >
в)	h (1 Д э д)=> (1 В э а )-
50.	Доказать» что в исчислении высказываний выводимы:

а) А =>д . б) 11А = А, в) А =>11 А.

г)	1А=>(А=>Ь),
д)	А = > ( 1 в * 1	(А =>&));
е) (А = > С )э ((5		= > А )= > (б ^ С )) .

51. Доказать,		что в исчислении предикатов выводимы:
а)	Vx Vy	Vy V X А ,
б) Vx (A * 8 ; W V * y 4 ^ V x а.
в)	V* (А=> В) =>(Зх а э			Э к в)).
52.	Построить аксиоматическую теорию, в которой					бы были
выводимы формулы:
а)	о А	; б)	ttit	; в)	2 +2 = 5	\
г)	v v v а	;д)	» э	7 ; в)	А => 1 А .

53.Построить теории первого порядка: а) теорию частичного упорядочения; б) теорию групп.

54.Чеку равна мощность множества А , для которого справед­ ливы аксиомы:

а)	0 € А ;
б)	Vx((X€A)=> (X € A )),(0 * = f);
в)	V*((xcA)=>	0 ))i
г)	УХ€а Уу £а О(х	= у* ) ^ ( Х -{/))•
д)	Чх*в((0(:аЯА)&((ХеЬ)=з(х*е в)= (5 = А))?

ГЛАВА. 3. ТЕОРИЯ АВТОМАТОВ

Основная литература

1. Глушков В.М. Синтез цифровых автоматов. II., Фиэматгиз,

1962.

2.Гилл А. Введение в теорию конечных автоматов. М . , "Нау­ ка-, 1966.

3.Бувунов Ю.А., Вавилов Б.Н. Принципы построения цифровых вычислительных машин. Киев, "Техника", 1972.

- 39 - Дополнительная литература

I* Алгебраическая теория автоматов, языков и полугрупп. Под ред. Арбиба М.А. М.. "Статистика", 1975.

2.Минский М. Вычисления и автоматы. М.. "Мир", 1971.

3.Трахтенброт Б.С., Барэдинь Я.М. Конечные автоматы. Поведение и синтез. М., "Наука", 1970.

4.Языки и автоматы. Сб. переводов. М., "Мир”, 1975.

3.1, Понятие автомата. СЬособд£__з^дд]тд_^автомото^

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

1.Конечным входным алфавитом (конечным, множеством входных сигналов) X * { X f i t j , . . . хЛ }#

2.Конечным выходным алфавитом (конечным множеством выход­ ных ожгаалов)

3.	Множеством внутренних ооотоянжй			А = { Л у , а 2 , — J .
£сдж число внутренних состояний конечно,				то имеем конечный авто­
мат, в противном случае - автомат бесконечный.
4.	функцией переходов	f ( & ,х )	•
5.	Функцией маодов	( а , х),
6.	Начальным оостоянвем автомата а9.
Или иначе: Л * < х , у ,{ ( а , х ) , 4 > (а , х ) , а 0 > .
Законы функционирования автоматов могут быть записаны:
а) для автоматов первого родя (автоматов Пили)
	« ( Ч • f f a f t - 1), г		(t /
	у f t ) : <r(a ( t - П ,		X ( t ) ;
б) доя автоматов второго рода

a ( t ) = { ( a ( t - l ) . x ( t l y ( t ) s V ( a ( t ) , x ( t f

- 40 - в) д м продольных автоматов второго рода (автоматов Мура)

a(t) = {{a.(t-i), д (t)J,

fc y(t)= *P(aft)).

I. Задание автоматов о помощью таблиц:

^а) автомат Мили задается о помощью таблицы переходов и таблицы выходов (табл. 3.1)»

Таблица 3.1

переходов выходов

	*1			** а < а* * * *				во	У2	аг * с •
			*2		Дз	9	X/ Уг
						т
						9				•
	*г			а ч	Of	т	*3	У2	У1		•
	*3			*	•	Ф		•	•
		♦					♦
		%					*
б)		автомат Мура задается о помощью отмеченной таблицы
переходов		(табл.			3.2).
		Таблица 3.2						Таблица 3.3
	Уз	Уг		У2	Ун				CLo O f		а г
	йо Of а2 Оз • • •							do Ч } %			• • « • • •
Xf *г а5 • • *					щ * •			Of Ч
хг	*з	о*		»				о 2
				9
				9
•								• • •
Ф
2. Задание автоматов в виде графа:
а) автомат Мили						(рис. 3.1);

б) автомат Мура (рис. 3.2).

3. Задание автоматов в виде матриц переходов, которые явля вггся математической копией графов переходов (табл. 3.3).