Задачи по математической логике

Контрольная работа №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 обод в «ширину»                  обход «в глубину»