Считая граф представленный на рисунке 1а н-графом осуществить для указанного орграфа и графа

Считая граф, представленный на рисунке 1а н-графом, осуществить для указанного орграфа и графа, представленного на рисунке 1б, операции объединения, пересечения, разности и дополнения.
10. Для графов, представленных на рисунках 1а, 1б, привести возможные примеры частей и подграфов.

8 Маршруты и деревья
1. Для вершин d, с, g, m графа G (рисунок 6) привести примеры маршрута, цепи, простой цепи.
2. Для вершин d, сd, с, g, m графа G (рисунок 6) привести примеры циклического маршрута, цикла, простого цикла.

Рисунок 6 – Граф

3.Существует ли в графе G (рисунок 6) эйлеров цикл (цепь), гамильтонов цикл (цепь)?
4. Какими свойствами характеризуются отношения достижимости вершин в ориентированных графах G1-G3 на рисунке 7? Какой порядок задают отношения достижимости вершин в G1-G3?

Рисунок 7 – Графы G1-G3
5. Для вершин v1 графов G1-G3 (рисунок 7) привести примеры маршрута, цепи, простой цепи.
6. Для вершин v1 графов G1-G3 (рисунок 7) привести примеры циклического маршрута, цикла, простого цикла.
7. Имеют ли пятигранник-призма и пятиугольник с петлями в некоторых вершинах гамильтонов цикл (цепь)?
8. Каковы расстояния между вершинами в графах G (рисунок 6) и G1- G3 (рисунок 7)? Какие вершины графов G1- G3 являются центральными? Каковы радиусы этих графов?
9. Построить матрицы смежности и инцидентности графов G1- Gl0(рисунок 8). Чему равны степени вершин? Имеют ли графы эйлеров цикл (цепь)?

Рисунок 8 – Графы G1-G4

Продолжение рисунка 8 – Графы G5-G10

10. Какому отношению соответствует каждый граф (рисунок 8). Задать отношение матрицей, определить свойства отношения? Каковы расстояния между вершинами в графах G1- Gl0? Какие вершины графов являются центрами? Каковы радиусы этих графов?

9 Логика высказываний

1. Представить логическими формулами следующие высказывания:
а) «Ее муж не то Иван, не то Федор».
б) «Ее сыновья Илья да Дмитрий».
в) «Не то день, не то ночь».
г) «Ни рыба, ни мясо».
д) «Звездное небо – к солнечной погоде».
2. Представить логическими формулами следующие высказывания:
а) «Муж и жена – одна сатана».
б) «Куй железо, пока горячо».
в) «Делу время – потехе час».
г) «На всякого мудреца довольно простоты».
д) «Хочешь мира – готовься к войне».
е) «Семь бед – один ответ».
3. Представить логическими формулами следующие высказывания:
а) «Всяк сверчок знай свой шесток»;
б) «Не красна изба углами, а красна пирогами».
в) «Сколько с кувшином по воду не ходи – все равно разобьешь».
г) «Не красна изба углами, а красна пирогами».
4. Представить логическими формулами следующие афоризмы Козьмы Пруткова:
а) «Насколько полковник с Акулиной знаком, не спорь с полковым попом».
б) «Говорят, что труд убивает время, но сие последнее от этого нисколько не уменьшается, продолжает служить вселенной и всему человечеству во всей полноте и непрерывности».
в) «Счастье подобно шару, который подкатывается то по одного, то под другого, согласно числу и очереди счастливых людей».
г) «Что имеем – не храним, потерявши, плачем».
5. Представить логической формулой следующий текст: «Логические представления – описания исследуемой системы, процесса или явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления характеризуются законами логики – логически правильными методами рассуждений, представляющими собой наборы свойств и допустимых преобразований логических представлений. Математическая логика состоит из двух разделов: логики высказываний и логики предикатов».
6. Представить логической формулой следующий текст: «Чтобы установить или опровергнуть логическую правильность рассуждения, необходимо задать рассуждение логической схемой и сравнить ее со схемами логически правильных рассуждений. Иногда рассуждение задают логической формулой, и сравнивают ее с логическими формулами правильных рассуждений, в которые заранее были переведены схемы логически правильных рассуждений».
7. К каким схемам (логически правильным или логически неправильным) относятся следующие логические рассуждения:
а) «Если на улице идет дождь, то крыши мокрые. Крыши сухие. Дождя нет».
б) «Ему не то двадцать, не то двадцать пять лет. В паспорт вклеена новая фотография, следовательно, ему не двадцать».
в) «Если человек проспит, то он опоздает на работу. Человек опоздал на работу, следовательно, он проспал».
г) «Если за окном темнеет, то скоро ночь. Если за окном темнеет, то наступает гроза. За окном не темнеет, следовательно, не наступает ночь и не наступает гроза».
8. Проверить логическую правильность следующего высказывания: «Если посещаемость и успеваемость студента находятся на должном уровне, то студент сдаст сессию. Если посещаемость студента стопроцентная, но при этом успеваемость неважная, есть вероятность получить на экзамене двойку».
9. Проверить логическую правильность следующего высказывания: «Иванов женат либо на Анастасии, либо на Валентине. Он не женат на Валентине, следовательно, он женат на Анастасии».
10. Перевести схемы логически правильных рассуждений в логические формулы.

10 Алгебра логики

1. Представить в инфиксной форме следующие логические функции, заданные в префиксной форме:
а), если f1, f2– бинарные операции, причем f1 –⨁, f2 –. Вычислить значения функций на наборе (0, 1), если х1=0, х2=1;
б) , если f1, f2, f3 – бинарные операции, причем f1 – , f2 – , f3 –. Вычислить значения функций на наборе (0, 1, 1), если х1=0, х2=1, х3=1 .
в) , если f1, f2 – бинарные операции, причем f1 – , f2 –. Вычислить значения функций на наборе (0, 1), если х1=1, х2=0;
г) , если f1, f2, f3 – бинарные операции, причем f1 – , f2 –, f3 –. Вычислить значения функций на наборе (0, 1, 1), если х1=0, х2=1, х3=1.
2. Составить таблицы истинности следующих функций:
а) ;
б) ;
в) ;
г) .
3. Доказать или опровергнуть эквивалентность (равносильность) следующих функций:
а) =;
б) =;
в) хyх y=x;
г) х∙zх∙z х∙y = х∙zy∙z .
4. Подтвердить истинность следующих схем логически правильных заключений:
а) правила заключения;
б) правила отрицания;
в) правила утверждения-отрицания;
г) правила отрицания-утверждения;
д) правила транзитивности;
ж) правила противоречия;
з) правила контрапозиции;
к) правила сложной контрапозиции;
л) правила сечения;
м) правила импортации;
н) правила экспортации;
п) правила дилемм.
5. Представить булевой формулой в виде совершенной дизъюнктивной нормальной формы (СДНФ) следующие логические функции:
а)~;
б)~;
в)~;
г)~;
6. Упростить булевы формулы:
а) ;
б) ;
в) ;
г) .
7. Представить в базисе {┐} следующие логические функции:
;
;
;
.
8. Упростить с использованием метода Блейка-Порецкого СДНФ следующих функций:
;
;
;
.
9. Получить дизъюнктивную нормальную форму (ДНФ) следующих логических функций двумя способами (табличным и с помощью эквивалентных преобразований):
а) ;
б) ;
в) ;
г) .
10. Для функций, указанных в пункте 9, получить конъюнктивную нормальную форму (КНФ) и совершенную конъюнктивную нормальную форму (СКНФ) двумя способами (табличным и с помощью эквивалентных преобразований).

11 Логика предикатов
1. Проиллюстрировать на примере предиката порядка понятия истинного, ложного и переменного высказываний.
2. Записать предикатной формулой предложение, которое выражает для произвольных a,b,c ∈ N в модели N=(N:S, П, Е), называемой в логике предикатов арифметикой натуральных чисел, где N — множество натуральных чисел и S, П, Е -предикаты суммы, произведения, равенства соответственно:
а) коммутативность умножения;
б) ассоциативность сложения;
в) ассоциативность умножения;
г) дистрибутивность слева умножения относительно сложения;
д) дистрибутивность справа умножения относительно сложения;
е) транзитивность равенства.
3. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем N0. Дать словесную формулировку исходных и полученных высказываний и определить их истинность, если:
a)P (x) = ∃yS(y, y, x);
б) Р(х) = ∃yП(у,у, х);
в)Р(х) = ∀уП(х,у,у);
г) Р (х) = ∀yS(x,y,y).
4. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел N. Дать словесную формулировку исходных и полученных высказываний и определить их истинность, если:
a)P(x) = ∃yЕ(y, y, x);
б)Р(х) = ∀уЕ(х,у,у).
5. Пусть Q(x, у) — предикат порядка «х≤y», определенный на конечном множестве натуральных чисел М = {0,1,2, 3,…, 9}. Рассмотреть различные варианты квантификации его переменных. Определить истинность получаемых выражений.
6. Определить истинность, ложность либо выполнимость в области N0натуральных чисел следующих формул:
а) ∀x∀y∀z∀u ((S(x, у, z) &S(х, y, u)) → E(z,u));
б) (S(х, у, z) &S(y, x, u)) → E(z, u);
в) ∀x∀y∀z∀u ((П(x, y, z) & П(у, x, и)) → E(z, u));
г) ∃y(П(x,x,y) →S(x,x,y)) ;
7. Определить истинность, ложность либо выполнимость в области N0натуральных чисел следующих формул:
д) ∀x ∀y ∀z ((П(x, y,z)& E(x, y)) → S(x, y, z));
е) ∃y((S(x,y,z)vE(x,z)) → Q(x,z));
ж) Q (х,y) → (∃yS(x ,y,z) v E(x,z));
з) ∃xП(x,y, z) →D(z,y));
8. Определить истинность, ложность либо выполнимость в области N0натуральных чисел следующих формул:
и) ∃xS(x,y,y) →∀xS(х, y, y);
к) ∃х П(у, x, у) →∀y П(у, х, у);
л) ∃хS(х,х,y);
м) ∃yS(x,x,y).
9. Получить ПНФ формул в

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

семь + двенадцать =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Adblock detector