Контрольная работа по "Математической логике и теории алгоритмов"

Первый вариант 

1.  Отношение  задано на множестве целых чисел {53, 43, 54, 42, 44, 60, 50, 20} . Для каждого из следующих отношений: 

 

1.1  проверить, является ли отношение рефлексивным, симметричным,

антисимметричным (строгим, нестрогим), транзитивным;

1.2.  построить матрицы и графы этих отношений; 

1.3.  определить являются ли эти отношения отношениями эквивалентности,

частичного порядка, линейного  порядка; 

1.4..  для отношений эквивалентности построить классы эквивалентности; 

1.5.  для отношений частичного порядка применить алгоритм топологической

сортировки и получить отношение  строго порядка; 

1.6.  построить транзитивные замыкания всех отношений. 

• xRy ó x и y  имеют одинаковые остатки при делении на 3; 
• xQy ó в наборе имеется элемент, больший  x , но меньший y ; 

 

Решение.

 

Рассмотрим отношение 

xRy ó x и y  имеют одинаковые остатки при делении на 3.

 

 

Для построения матрицы составим таблицу:

	X	53	43	54	42	44	60	50	20
Y	остаток	2	1	0	0	2	0	2	2
53	2	1				1		1	1
43	1		1
54	0			1	1		1
42	0			1	1		1
44	2	1				1		1	1
60	0			1	1		1
50	2	1				1		1	1
20	2	1				1		1	1

1

 

Данное отношение обладает свойством рефлексивности, так как  на главной диагонали все единицы.

 

Данное отношение  симметрично, так как наблюдается симметрия матрицы относительно главной диагонали.

Данное отношение не антисимметрично, так как существует симметричные элементы, не лежащие на главной диагонали, то есть выполнение отношений xRy,  yRx  не влечет за собой отношения x=y.

 

Данное отношение транзитивно, потому что выполнение отношений xRy и yRz влечет выполнение отношение xRz (если x, y имеют одинаковые остатки при делении на 3 и y, z имеют одинаковые остатки при делении на 3, то  x, z также имеют одинаковые остатки при делении на 3). 

 

Данное отношение является отношением эквивалентности, поскольку  оно обладает свойствами рефлексивности, симметричности, транзитивности.

 

Данное отношение не является отношением частичного порядка, поскольку оно не антисимметрично.

 

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

 

 

Граф отношения:

 

Классы эквивалентности: [43],  {53, 44,  20,  50],  [60, 42, 54].

 

 

Транзитивное замыкание

 

X	Y
53	53
53	50
53	20
53	44
50	50
50	53
50	20
50	44
44	44
44	43
44	50
44	20
20	20
20	44
20	53
20	50
43	43
54	54
54	60
54	42
42	42
42	54
42	60
60	60
60	54
60	42

 

 

Рассмотрим отношение

xQy ó в наборе имеется элемент, больший x , но меньший y

 

 

Для построения матрицы составим таблицу:

X/Y	53	43	54	42	44	60	50	20
53						1
43	1		1			1	1
54
42	1		1		1	1	1
44	1		1			1
60
50			1			1
20	1	1	1		1	1	1

1

 

 

Данное отношение не обладает свойством рефлексивности, так как на главной диагонали все нули.

 

Данное отношение  не симметрично, не наблюдается симметрия матрицы относительно главной диагонали.

 

Данное отношение не асимметрично. Нет симметричных элементов, одновременное выполнение отношений xQy, yQx  ytdjpvj;yj/

 

Данное отношение транзитивно, потому что выполнение отношений xRy и yRz влечет выполнение отношение xRz (если есть элементы больше x и меньше y, а также есть элементы больше y и меньше z, то имеются элементф больше x и меньше z.

 

Данное отношение не является отношением эквивалентности, поскольку оно не обладает свойствами рефлексивности, и симметричности.

 

Данное отношение не является отношением частичного порядка, поскольку оно не рефлексивно.

 

Данное отношение является отношением линейного порядка, поскольку для любых двух элементов a, b имеет место a<=b или b<=a.

 

Данное отношение является отношением строгого порядка.

 

Граф отношения:

 

Транзитивное замыкание

X	Y
20	43
20	44
20	50
20	43
20	54
20	60
42	44
42	50
42	53
42	54
42	60
43	50
43	53
43	54
43	60
44	53
44	54
44	60
50	54
50	60
53	60

 

2. Будет ли логичным следующее рассуждение:  Если губернатор не имеет

соответствующего авторитета или  если он не желает принимать на себя

ответственность, то порядок не будет  восстановлен  и волнения не прекратятся до

тех пор, пока участникам волнений это  не надоест, и власти не начнут

примирительные действия. Следовательно, если губернатор не желает взять на себя

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

 

Решение

 

Запишем высказывание символами формальной логики. Введем обозначения:

 

A – волнения прекратятся

X – губернатор  имеет авторитет

Y – он желает принимать на себя ответственность

P – участникам это надоест

Q – власти начнут примирительные действия

 

 

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

 

 

То есть в приведенном рассуждении  есть ошибка. Правильным будет следующее  рассуждение:

Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен  и волнения не прекратятся до

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

 

 

3. Провести исследование булевой функции 

a)  построить таблицу функции; ответ записать в виде набора значений,   

упорядоченного в соответствии с  лексикографическим порядком набора

аргументов;

b)  построить СДНФ этой функции; ответ записать, упорядочив  элементарные 

конъюнкции  в  лексикографическом порядке;

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

ответ   записать    в   виде минимальной ДНФ;

d)  построить   многочлен   Жегалкина     исходной   функции;

e)  построить таблицу двойственной  функции; ответ записать в виде упорядоченного

набора значений;

f) построить  СКНФ  двойственной  функции; ответ записать, упорядочив

элементарные   дизъюнкции  в  лексикографическом порядке;

g)  проверить исходную функцию на     принадлежность основным классам

замкнутости T0 ,T1 , L, M, S;

h)  Можно ли через эту функцию выразить все остальные булевы функции. 

 

Решение

Составим таблицу истинности:

x	y	z	F(x,y,z)
0	0	0	0
1	0	0	0
0	1	0	0
1	1	0	1
0	0	1	0
1	0	1	0
0	1	1	0
1	1	1	0

 

Построим  СДНФ :

F(x,y,z)=

 

ДНФ:

F(x,y,z)=x˄y˄¬z

 

Построим   многочлен   Жегалкина:

F(x,y,z)=x˄y˄(z 1)= x˄y˄z x˄y

 

Двойственная функция:

(F(x,y,z))^*=¬( ¬x˄¬y˄z)

 

 

Составим таблицу истинности двойственной функции:

x	y	z	(F(x,y,z))*
0	0	0	1
1	0	0	1
0	1	0	1
1	1	0	1
0	0	1	0
1	0	1	1
0	1	1	1
1	1	1	1

 

СКНФ  двойственной  функции

(F(x,y,z))^*= + + + + + =

= =

 

Проверим функцию на принадлежность к классам замкнутости:

 

Функция принадлежит к классу Т0, поскольку F(0,0,0)=0

Функция не принадлежит к классу Т1, поскольку F(1,1,1)=0

Функция не принадлежит к классу S, поскольку

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

Функция не принадлежит к классу L линейных функций, поскольку не представляется в виде суперпозиции произведений аргументов на коэффициенты.

 

Для того, чтобы  система булевых функций была полной, необходимо и достаточно, чтобы  для каждого из классов Т₀, Т₁, S, L, M нашлась функция f_i из этой системы не принадлежащая этому классу. В данном случае все функции принадлежат классу Т0, поэтому система функций не является полной, не все булевы функции могут быть выражены в этой системе.

 

 

 

4. Машина Тьюринга имеет алфавит из трех символов {2,1,*} (символ  ∗   означает

отсутствие символа на ленте), два  состояния {q0, q2}, из которых q0–начальное состояние,

q2 – конечное. Символ  R  означает сдвиг читающей головки вправо по ленте,  L – влево,

E – головка остается на месте. В начальный момент головка указывает на крайний левый

символ  записи. Команды машины задаются набором: q₀2 –> q₀1 R;  q₀1 –> q₀1 L;  q₀* –>

q₂1 E. Какой результат даст машина на наборе 22122?

 

Решение

 Печатающая  головка будет перемещаться вправо, заменяя цифры 2 на 1, пока не  дойдет до цифры 1; потом она перемещается влево, считывая цифры 1. Дойдя до пустой ячейки, головка напечатает цифру 1 и остановится. В итоге получится последовательность 111122.

 

5, Построить порождающую грамматику для языка

 

Решение  

 Язык L = {aⁿbⁿcⁿ | n > 0} порождается грамматикой с правилами

	S ® aSBC	S ® aBC	CB ® BC
	aB ® ab	bB ® bb
	bC ® bc	cC ® cc

 

 

 Второй  вариант 

1. Отношение задано на множестве целых чисел  {53, 43, 54, 42, 44, 60, 50, 20) . Для каждого из следующих отношений:

 

1.1  проверить, является ли  отношение рефлексивным, симметричным,

антисимметричным (строгим, нестрогим), транзитивным; 

1.2.  построить матрицы и графы  этих отношений; 

1.3.  определить являются ли эти отношения отношениями эквивалентности,