ДМ_Конспект

множество целых чисел, больших чем 2.

Квантифицированный предикат xP(x) , где P(x) : 3 x 5 , не является

истинным, если предметная область − множество целых чисел, потому что имеются значения x из этой области (например, x 4 ) такие, что P(x) ложно.

Для истинности xP(x) P(x) должно быть истинным для каждого значения x из предметной области.

Пример. Предикат xP(x) , где P(x) : x2 4 , является истинным, если

предметной областью есть множество действительных чисел, т.к. x2 4 истинно для x 2 .

Предикат xP(x) , где P(x) : x2 5, также истинен, если предметной

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

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

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

12.4 Законы и тождества логики предикатов

Все законы и тождества, которые справедливы в логике высказываний, остаются справедливыми и в логике предикатов.

Для эквивалентных преобразований предикатных высказываний с кванторами дополнительно необходимо использовать приведенные ниже законы.

1. Замена связанной переменной: (x)F(x) (y)F( y) ;

(x)F(x) (y)F( y) ,

F (x) − одноместный предикат.

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

Пример.

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

Здесь осуществлена операция переименования связанной переменной y .

2. Коммутативные свойства кванторов:

(x)(y)P(x, y) (y)(x)P(x, y) ;

131

(x)(y)P(x, y) (y)(x)P(x, y) .

Менять местами можно только одноименные кванторы.

(x)(y)P(x, y) (y)(x)P(x, y) .

3. Дистрибутивные свойства кванторов:

(x)F(x) G (x)(F(x) G) ; (x)F(x) G (x)(F(x) G) ; (x)F(x) G (x)(F(x) G) ; (x)F(x) G (x)(F(x) G) ,

где G − формула логики предикатов, которая не содержит x ; (x)F(x) (x)H (x) (x)(F(x) H (x));

(x)F(x) (x)H (x) (x)(F(x) H (x)).

Сформулированный дистрибутивный закон справедлив только для квантора всеобщности при конъюнкции и квантора существования при

дизъюнкции , т.к. другие комбинации приводят к неравенствам:

(x)F(x) (x)H (x) (x)(F(x) H (x)) ; (x)F(x) (x)H (x) (x)(F(x) H (x)) .

Для преодоления данного ограничения дистрибутивного закона, следует

использовать замену связанной переменной:

(x)F(x) (x)H (x) (x)F(x) (y)H ( y) (x)(y)(F(x) H ( y)) ; (x)F(x) (x)H (x) (x)F(x) (y)H ( y) (x)(y)(F(x) H ( y)).

Таким образом, в общем случае дистрибутивные свойства кванторов можно записать следующей схемой:

(Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ; (Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ,

где (Q1 x), (Q2 x) − любой из кванторов или .

4. Закон де Моргана для кванторов:

((x)F(x) (x) F(x) ; ((x)F(x) (x) F(x) .

12.5 Предваренные нормальные формы

Определение.

Формула F в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она может быть

представлена в виде	(Q1 x1 )...(Qn xn )(A) ,	где каждое (Qi xi ) , i 1,...,n ,	есть или
(x) , или (x) , а	A − формула,	не содержащая кванторов.	Причем

(Q1 x1 )...(Qn xn ) называется префиксом, а A − матрицей формулы F .

Для преобразования выражений произвольной формы в ПНФ необходимо поочередно выполнить следующие этапы преобразования:

1. Исключить логические связки эквиваленции и импликации, выразив их

132

через операции дизъюнкции, конъюнкции и отрицания с помощью следующих законов: F G F G ; F ~ G (F G) (G F) .

2. Опустить знаки операций отрицания непосредственно на предикаты,

используя закон двойного отрицания (F) F	и законы де Моргана
(F G) F G) , (F G) F G) , в том	числе для кванторов:
((xF(x)) (x)(F(x)) ; ((xF(x)) (x)(F(x)) .

3.Если необходимо, переименовать связанные переменные.

4.Вынести кванторы в начало формулы, используя соответствующие законы, для получения предваренной нормальной формы

Пример.

Приведем формулу (x)F(x) (x)Q(x) к предваренной нормальной

форме.

Сначала исключим импликацию, затем опустим знак операции отрицания

непосредственно на предикат и вынесем квантор в начало:

(x)F(x) (x)H (x) ((xF(x)) (x)H (x) (x)(F(x)) (x)H (x)

(x)(F(x) H (x)).

12.6Выводимость в логике предикатов

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

	а)	Правило		удаления	квантора	всеобщности
		xP(x)		используется	для доказательства истинности
	P(c) для произвольного с D
	P(с) , где c − произвольно			выбранный элемент предметной области D , в
которой справедливо xP(x) .

Пример.

Из посылки «Все студенты любят получать хорошие оценки» делаем

вывод: «Студент Петров любит получать хорошие оценки».
	б)	Правило	введения	квантора	всеобщности
	P(c) для произвольного с D		утверждает	истинность xP(x) , если доказана
		xP(x)

истинность P(с) для любого c , то есть для всех элементов c из

рассматриваемой предметной области D .
в)	Правило	удаления	квантора	существования

	xP(x)	в истинной формуле xP(x)	заключается в указании
	P(c) для некоторого с D
		133

имени элемента c (конкретного или гипотетического), для которого P(с)

истинно.
	г)	Правило	введения	квантора	существования
	P(c) для некоторого с D		позволяет	заключить, что	xP(x) является
		xP(x)

истинным, когда известен некоторый элемент c , для которого истинно P(с) .

12.7 Контрольные вопросы и задания

1. Дайте определение понятия предикат.

2. Что называется порядком предиката?

3. Приведите примеры n -местных предикатов.

4. Какие типы символов разрешается использовать для построения атомов логики предикатов?

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

6. Дайте определение терма.

7. Что понимают под предметной областью?

8. Что понимают под квантором всеобщности?

9. Дайте определение понятию «квантор существования».

10. Какие переменные называются связанными, а какие – свободными? 11. Из чего состоит интерпретация формулы логики первого порядка? 12. Объясните суть замены связанной переменной.

13. Сформулируйте коммутативные свойства кванторов. 14. Запишите формулы закона де Моргана для кванторов. 15. Дайте определение предваренной нормальной формы.

16. С помощью каких законов можно опустить знаки операций отрицания непосредственно на предикаты?

17. Каким образом можно преобразовать выражения произвольной формы в ПНФ?

ЛЕКЦИЯ 13. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

13.1 Основные понятия исчисления предикатов

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

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

134

правил вывода, позволяющих из общезначимых формул получить общезначимые.

Определение.

Исчисление предикатов − это аксиоматическая теория, символами которой являются:

1)символы предметных переменных: x1 , x2 ,...,xn ,...;

2) символы предикатов: P(t ) , P(t ) ,...,P(t ) ,..., где t 0,1, 2,...;
1 2	n

3)логические символы: , ;

4)символы кванторов: , ;

5)скобки и запятую: ),( .

13.2 Аксиомы исчисления предикатов

Аксиомами исчисления предикатов являются следующие аксиомы:

а) A (B A) ;

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

г) xP(x) P( y) ; д) P( y) xP(x) .

13.3 Правила вывода в исчислении предикатов

В исчислении предикатов используются следующие правила вывода:

1. Правило отделения, которое формулируется так же, как и в

исчислении высказываний: P, P Q ;
Q
2. Правило связывания квантором общности (правило обобщения,
правило -введения) P Q(x) , где Q(x)	содержит свободные вхождения x ,
P Q(x)

аP их не содержит.

3.Правило связывания квантором существования (правило -

введения) Q(x) P , где Q(x) содержит свободные вхождения x , а P их не

Q(x) P

содержит.

4. Правило переименования связанной переменной. Связанную переменную формулы P можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в P .

Пример. Докажем правило переименования связанных переменных для квантора общности:

1. xF (x) (по условию).

135

2.xF (x) F( y) (аксиома а) ).

3.xF (x) yF( y) (правило обобщения).

4.yF ( y) .

Понятия вывода, теоремы, вывода из системы гипотез определяется в исчислении предикатов, как и в любой аксиоматической теории.

Теорема 13.1 (ослабленная теорема о дедукции)

Пусть G − множество формул, A, B − формулы и G, A B , и

существует вывод в исчислении предикатов, построенный с применением только правила отделения, то G A B .

Утверждение 1. Аксиомы исчисления предикатов − общезначимые формулы.

Утверждение 2. формула, получающаяся из общезначимой формулы по любому из правил 1 − 4, является общезначимой.

13.4 Контрольные вопросы и задания

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

2.Сформулируйте назначение исчисления предикатов.

3.Запишите формулы аксиом исчисления предикатов.

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

ЛЕКЦИЯ 14. ОБЩИЕ ОПРЕДЕЛЕНИЯ КОМБИНАТОРИКИ. ОСНОВНЫЕ

ПРАВИЛА КОМБИНАТОРИКИ. МОДЕЛИ ТИПОВЫХ КОМБИНАТОРНЫХ

КОНФИГУРАЦИЙ.

14.1 Общие определения комбинаторики. Понятие r -выборки. Общие

задачи комбинаторики

На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют "комбинаторные задачи".

136

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina - сочетать, соединять.

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

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

Определение.

Пусть задано r множеств:

E 1 , E 2 , E 3 ,..., E r , при этом

Ei 1 E 1 , E j 2 E 2 ,..., En r E r

,

тогда

r-выборкой

называется

Ei 1 , E j 2 ,..., En r .

упорядоченная совокупность элементов вида Pa

Определение.

Множество

всех выборок

называется

теоретико-

множественным

произведением

или произведением r

множеств

E 1 , E 2 , E 3 ,..., E r . Обозначается P E 1 E 2 E 3 ... E r

r -выборка не является множеством, а является элементом теоретико-

множественного произведения.

В r -выборке каждый элемент (компонента) может повторяться, но их

порядок фиксирован.

Определение. Две упорядоченные выборки равны или эквивалентны

тогда

и

только

тогда, когда

соответствующие элементы равны

P

P

, P

P

,....

1

2

1

2

Определение.

r-выборка

с

произвольным

порядком

размещения

компонент называется неупорядоченной r-выборкой. Обозначается P , P ... .

Основными и типичными операциями и связанными с ними задачами комбинаторики являются:

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

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

3)образование упорядоченных подмножеств – составление размещений.

137

14.2 Основные правила комбинаторики

Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения.

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

Правило суммы. Если A и B – несвязанные события, и существует n1 возможных исходов события A , и n2 возможных исходов события B , то возможное число исходов события « A или B » равно сумме n1 n2 .

Интерпретация. Если элемент a A можно выбрать m способами, а элемент b B – n способами, то выбор элемента x A B можно осуществить

m n способами. Пусть X1, X2 ,..., Xk								– попарно непересекающиеся множества,
	Xi X j 0 ,					где i j .	Тогда,	очевидно, выполняется	равенство
	k		k
		Xi			Xi
			i 1			.
	i 1
			Правило произведения.				Если дана последовательность k событий с n1
возможными исходами первого, n2 – второго, и т.д., вплоть до nk									возможных

исходов последнего, то общее число исходов последовательности k событий равно произведению n1 n2 ...nk .

Правило произведения тоже можно сформулировать на языке теории множеств. Пусть A1 обозначает множество n1 исходов первого события, A2 – множество n2 исходов второго, и т. д. Тогда любую последовательность k

событий можно	рассматривать		как			элемент		декартова	произведения
A1 A2 ...Ak , чья мощность равна
		A1		A2	...	Ak	.
Пример. Из	28 костей домино					берутся		2 кости. В	каком числе

комбинаций вторая кость будет приложима к первой?

На первом шаге имеется два варианта: выбрать дубль (7 комбинаций) или не дубль (21 комбинация). В первом случае имеется 6 вариантов продолжения, во втором – 12.

Общее число благоприятных комбинаций равно: 7 6 21 12 294 .

А всего вариантов выбора 2 костей из 28 равно 378; т. е. при большом числе экспериментов в 7 случаях из 9 (294/378 = 7/9) при выборе 2 костей одна кость окажется приложимой к другой.

138

14.3 Модели комбинаторных конфигураций

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

Определение. Размещением Ank из n элементов по k называется упорядоченный набор из k различных элементов некоторого n -элементного множества.

Определение. Перестановкой Pn из n элементов (например, чисел 1,2,..., n ) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n .

Определение. Сочетанием Cnk из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Определение. Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.

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

14.3.1 Размещения без повторений

Рассмотрим задачу: Сколько разных 5-разрядных чисел можно записать с помощью десяти цифр при условии, что в числах не используются одинаковые цифры?

Перенумеруем разряды:

1	2	3	4	5

В первый разряд можно поставить одну из 10 цифр (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Независимо от того, какая цифра помещена в первый разряд, во втором можно поставить только одну из 9 цифр, в третий – одну из 8 цифр и т. д. Всего существует 10 9 8 7 6 30240 различных пятиразрядных чисел, в каждом из которых нет двух одинаковых цифр.

139

В общем случае, если имеется k позиций и n разных предметов, причем каждый представлен в единственном экземпляре, то количество разных расстановок равно A n n 1 n 2 ... n k 1 n! n k !.

Пример. Из группы в 25 человек требуется выбрать старосту, сенатора и профорга. Сколько вариантов выбора руководящего состава группы? Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть сенатором, то для выбора сенатора остается 24 варианта. Профорга

выбирают				одним			из	23	способов.	Всего	вариантов:
A3		25!			25!	25 24 23 13800 .
25		(25 3)!		22!

Пример. На дискотеку пришло 12 девушек и 15 юношей. Объявлен ―белый‖ танец. Все девушки выбрали для танцев юношей (и никто из них не

отказался). Сколько могло образоваться танцующих пар? 15!(15 12)!

14.3.2 Размещения с повторениями

Рассмотрим задачу: сколько разных 5-разрядных чисел можно составить из 10 цифр?

Перенумеруем разряды:

1	2	3	4	5

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

Для двоичной системы счисления (используются только две цифры: 0 или 1) получаем 25 различных чисел.

Для системы с основанием k и числом разрядов n соответственно получаем: A k n , где n – число позиций (разрядов); k – число элементов в каждой позиции (цифр).

В общем виде задача ставится следующим образом: имеется k типов предметов (количество предметов каждого типа неограниченно) и n позиций (ящиков, кучек, разрядов). Требуется определить, сколько разных комбинаций можно составить, если в позициях предметы могут повторяться? Следовательно, размещения с повторениями можно определить как Ank k n .

140