1. Построить таблицу истинности для формулы
2. В формуле избавиться от операции импликации и упростить с помощью равносильных преобразований. Перечислить используемые законы
3. Проверить правильность логического рассуждения сокращённым способом. Какими другими способами можно решить эту задачу?
4. Используя 2 предиката, запишите предложение в виде формулы логики предикатов: «Некоторые почтальоны не любят собак». Поставьте знак отрицания перед полученной формулой и приведите её к предварённой нормальной форме.
5. Для орграфа G0 найдите множество достижимости и множество контрдостижимости вершины x1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G0. постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
Дан неорграф G1. Занумеруйте вершины графа и определите степени всех его вершин.
6. Покажите, что графы G1 и G2 изоморфны. Планарен ли G2?
7. Определите цикломатическое число графа G1. Выясните, можно ли нарисовать граф G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
8. Выясните, сколько рёбер нужно удалить из графа G1 при построении его каркаса. Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
Контрольная работа №2
1. Построить таблицу истинности для формулы:
F
A B
B
(
)
A
A B A B
0
0
1
1
0
1
0
1
0
1
1
1
B
A B
)
A
A B
B
1
1
1
1
A
1
1
0
0
(
1
1
0
0
2. В формуле
избавиться от операции
импликации и упростить с помощью равносильных преобразований. Перечислить
используемые законы1.
( & ))
B C
) & (
A
C
F
A
B
A
(
(
)
(
F
6
(
7
A
A
5
(
A
11
(
1
) & (
5
A
( & ))
B C
B
(
) & (
A
C
A
)
( & ))
B C
B A
(
) & (
A C
)
( & ))
B C
B A
(
A C
)
( & ))
B C
(
A
( & ))
B C
A
( & )
B C
( & )
B C
A
( & )
B C
A
3. Проверить правильность логического рассуждения сокращённым способом. Какими
B C A C
( & )
A C
& (
B
B
)
другими способами можно решить эту задачу?
«Если я буду говорить правду, то меня прославит простой народ. Если я буду лгать, то меня
прославят богатые и знатные. Но я должен говорить правду или лгать. Значит, меня
прославит простой народ или прославят богатые и знатные».
X=”Я буду говорить правду”
Y=”Меня прославит простой народ”
Z=”Меня прославят богатые и знатные”
X
Y
X
Z
X
X
Y Z
Рассуждение является логически правильным, если при любых наборах значений переменных
(X,Y,Z), для которых все посылки истинны, заключение также истинно. Предположим противное:
есть набор (X0,Y0,Z0) такой, что посылки истинны, а заключение ложно.
№ Истина
Y
1
X
X
Z
2
X
3
X
4
5
6
7
8
9
X
Ложь
Примечания
Предположим, что посылки истинны,
Y Z
Y
Z
X
X
Z
а заключение ложно
Из 4 и определения дизъюнкции
Из 4 и определения дизъюнкции
Из 1,5 и определения импликации
Из 7 и определения отрицания
Из 8,6 и определения импликации
1 Данные по законам беру из таблицы 2.5 со страницы 55 пособия З.А. Смысловой «Дискретная математика».Получили противоречие во 2 и 9 строках таблицы (из предположения X
=И, а из
=Л). Следовательно, наше предположение
Z
Z
логических рассуждений в ходе доказательства X
о неправильности рассуждения неверно. А, значит, данное в условии рассуждение – верно.
Другой способ решения задачи: построить таблицу истинности для формулы
Y
и убедиться, что она является тавтологией. Тогда по
X
признаку логического следования рассуждение является логически правильным.
Y Z
&
&
X
X
X
Z
4. Используя 2 предиката, запишите предложение в виде формулы логики предикатов:
«Некоторые почтальоны не любят собак». Поставьте знак отрицания перед полученной
формулой и приведите её к предварённой нормальной форме.
P(X)=”x – почтальон”
S(X)=”x – любит собак”
x P x
( )
(
(
F
( )
x P x
( ))
(
x P x
S xпредварённая нормальная форма
( )
( )
(
( )))
x P x
F
(
S x
P x
( )
S x
( ))
( )))
S x
( ))
S x
(
(
x
(
( )
x P x
( )
P x
( ))
S x
( ))
S x
x
(
5. Для орграфа G0 найдите множество достижимости и множество контрдостижимости
вершины x1. Выясните, какими свойствами обладает бинарное отношение, заданное графом
G0. постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G0.
X2
X1
X5
X3
X4
G0
D
{ }
x
0
1
) { ,
) { , },
R x
x x D D
(
R x
(
, }
x x x
1
2
1
0
1
5
2
5
1
2
) { , }
)
(
))
R x
R R x
(
R x
(
)
(
(
R x
x x
{ , }
x x
1
3
1
1
2
5
1
3
) { ,
x x x x
, } { , } { ,
x x
D D R x
x x x
(
, }
1
1
1
1
5
3
5
,
2
3
2
2
1
2
В x4 нельзя попасть из x1 процесс построения множества достижимости окончен
D(x1)=
{ ,
x x x x
, }
1
5
,
2
3
Множество контрдостижимости
K0={x1};
K(x1)={x1,x2}
1
(
R x
1
) { }
x
2
, K1=K0 {x2}={x1,x2}Отношение не является рефлексивным (не при всех вершинах есть петли) и не является
антирефлексивным (есть петля при X4), не является симметричным (пара вершин (x1,x5) соединена
только одной дугой), не является несимметричным (вершины (x2,x3) и (x1,x2) соединены парами
дуг), не является антисимметричным ((x1,x3)R, (x3,x1) R, но x3 x1), не является транзитивным
((x3,x2)R, (x2,x1)R, (x3,x1) R).
Матрица смежности орграфа G0:
x
3
x
2
x
4
x
x
5
1
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
A
x
1
x
2
x
3
x
4
x
5
g1
X1
g5
X2
g2
g4 g3
g6
X5
G0
X3
X4
Матрица инцидентности
B
g
1
1
1
0
0
0
x
1
x
2
x
3
x
4
x
5
g
2
0
1
1
0
0
g
3
0
1
1
0
0
g
4
1
1
0
0
0
g
6
g
5
0
1
0
0
0
0
0
2
1 0
6. Дан неорграф G1. Занумеруйте вершины графа и определите степени всех его вершин.
Нарисуйте какойлибо остовный подграф графа G1. Запишите матрицу смежности и матрицу
инцидентности графа G1, занумеровав его рёбра.
Степени вершин: p(1)=3, p(2)=3, p(3)=4, p(4)=3, p(5)=3,
p(6)=3, p(7)=3,
X4
X3
X6
X7
X2
X1
X5
G1
Остовный подграф G1
X2
X3
X6
X7
X4
X1
X5
Матрица смежности:
X
X
3
5
0 0 1
X
4
0 1
0 1
X
X
1
2
0 1
1
0 1
0 0 1
1
0 0 1 1 1
1 1 1
X
X
6
7
0 1
0 0 0 1
0 1 1
0
0
0 0
0 0 0 0
0 1 1
0 1
0 0 1
X
X
X
X
X
X
X
A
1
2
3
4
5
6
7
Матрица инцидентности:
III
IX X
0 0 0 0 1
IV V VI VII VIII
II
0 0 0 1 1
XI
I
0 0 0 0 0
1
0 0 0 0
1 1
0 0
0 1 1
0
0 0 1 1
0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1 1
0 0 0
0 0 0 0 0 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1
B
X
X
X
X
X
X
X
1
2
3
4
5
6
7
X3
X2
II
VIII
VII
IX
X6
III
X
X4
X7
I
VI
X1
IV
X5
XI
V
G1
7. Покажите, что графы G1 и G2 изоморфны. Планарен ли G2?
X3
II
X2
VIII
IX
III
X
X4
IV
VII
VI
I
X1
X6
X7
XI
V
G1
X5
X4
X2
II
IV
III
X3
I
X1
VI
VII
V
X
X6
IX
X7
VIII
XI
X5
G2
Число вершин n1=n2=7; число рёбер m1=m2=11
G1 и G2 – изоморфны
G3
G2 планарен, т.к. существует G3 – плоский, изоморфный графу G2.
8. Определите цикломатическое число графа G1. Выясните, можно ли нарисовать граф
G1, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.X2
X1
X3
X6
X7
G1
X4
X5
Цикломатическое число
p(1)= p(2)= p(4)= p(5)= p(6)= p(7)=3; p(3)=4
k m n
1 11 7 5
1(
G
)
В графе G1 имеется 6 вершин с нечётной степенью и 1 вершина с чётной. Т.о. не существует
в графе G1 Эйлерового цикла и Эйлеровой цепи. Нельзя нарисовать граф G1, не отрывая руки от
бумаги и не проходя ни по одному ребру дважды.
9. Выясните, сколько рёбер нужно удалить из графа G1 при построении его каркаса.
Занумеруйте вершины графа G1 и постройте каркас двумя способами (обход «в ширину»,
обход «в глубину»), начав обход из вершины с максимальной степенью.
X3
X6
X7
X2
X4
X1
X5
Цикломатическое число равно 5 (из предыдущего задания) для построения каркаса
необходимо удалить 5 ребёр.
Максимальную степень имеет вершина X3: p(X3)=4.
1
2
4
5
7
3
6
1
2
3
4
5
6
7
обод в «ширину»
обход «в глубину»