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

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

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

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

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

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

. 

 

xGy ó  каждая из цифр числа x   больше цифры числа y , стоящей в соответствующем разряде; 

 

xSy ó   |x-y|<5. 

 

 

Решение.

 

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

 

xGy ó  каждая из цифр числа x   больше цифры числа y , стоящей в соответствующем разряде; 

 

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

 

Данное отношение  не симметрично, так как любого xGy отсутствует yGx.

 

Данное отношение асимметрично, так как отсутствуют симметричные элементы.

 

Данное отношение  транзитивно, потому что выполнение отношений xGy и yGz влечет выполнение отношение xGz

 

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

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

1

 

 

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

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

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

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

 

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

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

 

 

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

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

1

 

 

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

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

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

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

 

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

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

 

 

Рассмотрим отношение xSy=|x-y|<5

 

Данное отношение обладает свойством рефлексивности, так как  выполняется xGx  для любого x (Например, |53-53|<5).

 

Данное отношение  симметрично, так как любого xSy выполняется  ySx (например, |43-42|<5, |42-43|<5).

 

Данное отношение не антисимметрично, так как присутствуют симметричные элементы, не лежащие на главной диагонали.

 

Данное отношение не транзитивно.

 

 

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

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

1

 

 

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

 

 

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

 

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

.

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

 

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

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

 

2.  Будет ли логичным  следующее рассуждение:  Намеченная  атака  удастся, если 

захватить  противника  врасплох или его позиции плохо защищены. Захватить

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

 

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

 

A – намеченная атака удастся

X – захватить противника врасплох

Y – противник беспечен

P – позиции хорошо защищены

 

 

Выполним преобразования.

 

Из  следует Y=P,  X=P

 

То есть в исходном рассуждении есть ошибка,  правильный вывод – атака удастся.

 

Тот же вывод можно  сделать, подставляя высказывания в  соответствии с требованиями логики: Намеченная атака  удастся, если позиции  хорошо защищены (и противник беспечен, то есть его можно захватить врасплох),  или его позиции плохо защищены. То есть и при хороших, и при плохих позициях атака удастся.

 

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	1
0	1	0	0
1	1	0	0
0	0	1	1
1	0	1	1
0	1	1	0
1	1	1	0

 

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

F(x,y,z)= =

 

ДНФ:

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

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

F(x,y,z)= = =

=

 

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

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

 

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

 

 

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

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

f(0,0,0)=0, функция принадлежит классу Т0:

f(1,1,1)=0, функция не принадлежит классу Т1

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

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

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

 

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

 

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

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

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

крайний левый символ записи. Команды  машины задаются набором: q02 –> q01 R;  q01 –> q02 L;  q0* –> q22 E. Какой результат  даст машина на наборе 22122?

 

Решение.

Читающая головка, находящаяся  над цифрой 2, печатает вместо неё  цифру 1 и перемещается вправо; находясь над цифрой 1 -  печатает вместо неё цифру 2 и перемещается влево; находясь над пустоя ячейкой –печатает цифру 2 и останавливается.

 

  22122

  12122

  11122

  11222

  12222

  22222

222222

 

То есть в итоге будет напечатана последовательность цифр 222222.

 

 

 

 

5. Построить порождающую грамматику для языка L={(ac)ⁿ(cb)ⁿ, n>0}

 

Решение

L(G) = {(ac)ⁿ (cb)ⁿ | n > 0}

G:S → aQb | accb

Q → cSc