8908
.pdf91. Даны коды деревьев:
а) (0100011001101011); б) (00101001110001010111).
Сколько вершин имеет каждое из этих деревьев? Постройте соответст-
вующие деревья.
92. Запишите формулой булеву функцию, которая задана семантическим деревом на рисунке 3.26.
Рис. 3.26.
93. В таблице приведена стоимость перевозок между соседними железнодо-
рожными станциями. Укажите схему, соответствующую таблице
|
|
A |
B |
C |
|
D |
|
|
|
|
|
|
|
||||
|
A |
|
4 |
|
|
5 |
|
|
|
B |
4 |
|
3 |
|
6 |
|
|
|
|
|
|
|
||||
|
C |
|
3 |
|
|
|
|
|
|
D |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|||
1) |
|
|
2) |
3) |
4) |
94. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями. Укажите таблицу, для кото-
рой выполняется условие: «Минимальная стоимость проезда из А в B не боль-
ше 6».
|
A |
B |
C |
D |
E |
|
|
A |
B |
C |
D |
E |
|
|
A |
B |
C |
D |
E |
|
|
A |
B |
C |
D |
E |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
3 |
1 |
|
|
A |
|
|
3 |
1 |
1 |
|
A |
|
|
3 |
1 |
4 |
|
A |
|
|
|
1 |
|
B |
|
|
4 |
|
2 |
|
B |
|
|
4 |
|
|
|
B |
|
|
4 |
|
2 |
|
B |
|
|
4 |
|
1 |
C |
3 |
4 |
|
|
2 |
|
C |
3 |
4 |
|
|
2 |
|
C |
3 |
4 |
|
|
2 |
|
C |
|
4 |
|
4 |
2 |
D |
1 |
|
|
|
|
|
D |
1 |
|
|
|
|
|
D |
1 |
|
|
|
|
|
D |
1 |
|
4 |
|
|
E |
|
2 |
2 |
|
|
|
E |
1 |
|
2 |
|
|
|
E |
4 |
2 |
2 |
|
|
|
E |
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
161 |
|
|
|
|
|
|
|
|
|
|
|
|
|
95. Пользуясь алгоритмами Прима и Краскала, нужно построить остов ми-
нимального веса для графа на рис. 3.27.
Рис. 3.27.
96. С помощью алгоритма Прима найдите кратчайший остов графов на ри-
сунке 3.28.
Рис. 3.28.
97. |
Пользуясь алгоритмом Дейкстры, определите минимальный путь из v1 в |
v6 в нагруженных орграфах, заданных матрицами весов. |
|
а) |
б) |
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v1 |
0 |
4 |
∞ |
12 |
∞ |
∞ |
v2 |
∞ |
0 |
2 |
∞ |
5 |
10 |
v3 |
3 |
∞ |
0 |
3 |
∞ |
∞ |
v4 |
∞ |
∞ |
∞ |
0 |
1 |
∞ |
v5 |
∞ |
∞ |
∞ |
∞ |
0 |
2 |
v6 |
∞ |
∞ |
7 |
∞ |
∞ |
0 |
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v1 |
0 |
5 |
1 |
8 |
∞ |
∞ |
v2 |
∞ |
0 |
∞ |
1 |
∞ |
6 |
v3 |
∞ |
5 |
0 |
∞ |
∞ |
∞ |
v4 |
∞ |
∞ |
∞ |
0 |
1 |
∞ |
v5 |
∞ |
∞ |
∞ |
∞ |
0 |
2 |
v6 |
∞ |
∞ |
4 |
7 |
∞ |
0 |
98. Пользуясь алгоритмом Дейкстры, определите минимальный путь из v1 в
v7 в нагруженном орграфе D с заданной матрицей весов
162
а) |
б) |
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
v1 |
∞ |
∞ |
5 |
4 |
2 |
2 |
9 |
|
|
|
|
|
|
|
|
v2 |
∞ |
∞ |
1 |
1 |
∞ |
1 |
1 |
|
|
|
|
|
|
|
|
v3 |
2 |
∞ |
∞ |
1 |
1 |
∞ |
3 |
v4 |
∞ |
2 |
1 |
∞ |
1 |
∞ |
∞ |
|
|
|
|
|
|
|
|
v5 |
∞ |
∞ |
2 |
2 |
∞ |
1 |
6 |
|
|
|
|
|
|
|
|
v6 |
1 |
5 |
∞ |
1 |
1 |
∞ |
∞ |
v7 |
2 |
∞ |
1 |
∞ |
1 |
2 |
∞ |
|
|
|
|
|
|
|
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
v1 |
∞ |
∞ |
9 |
∞ |
∞ |
2 |
12 |
|
|
|
|
|
|
|
|
v2 |
1 |
∞ |
∞ |
∞ |
1 |
2 |
4 |
|
|
|
|
|
|
|
|
v3 |
2 |
1 |
∞ |
∞ |
1 |
∞ |
2 |
v4 |
∞ |
1 |
1 |
∞ |
∞ |
1 |
∞ |
|
|
|
|
|
|
|
|
v5 |
1 |
2 |
∞ |
2 |
∞ |
∞ |
∞ |
|
|
|
|
|
|
|
|
v6 |
∞ |
∞ |
∞ |
∞ |
1 |
∞ |
8 |
v7 |
∞ |
2 |
1 |
∞ |
1 |
2 |
∞ |
|
|
|
|
|
|
|
|
99. Все площадки для отдыха, расположенные в лесопарковой зоне, необхо-
димо соединить телефонной сетью, причем телефонные линии должны прохо-
дить вдоль троп лесопарковой зоны. Спроектировать телефонную сеть с мини-
мальной суммарной длиной линий.
Рис. 3.29.
100. |
Транспортная компания осуществляет грузовые перевозки в города A, |
B, C, D, E, F, G. В таблице а) приведена матрица смежности графа рейсов ком- |
|
пании; в таблице б) приведены расстояния между городами: |
|
а) |
б) |
|
A |
B |
C |
D |
E |
F |
G |
|
|
|
|
|
|
|
|
A |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
B |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
C |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
D |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
E |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
F |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
G |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
A |
B |
C |
D |
E |
F |
G |
|
|
|
|
|
|
|
|
A |
|
|
2 |
0 |
5 |
8 |
|
B |
|
|
|
8 |
|
4 |
1 |
C |
2 |
|
|
1 |
|
|
7 |
D |
|
8 |
1 |
|
|
|
|
E |
5 |
|
|
|
|
2 |
6 |
F |
8 |
4 |
|
|
2 |
|
|
G |
|
1 |
7 |
|
6 |
|
|
163
Найдите длину наименьшего пути, по которому можно доехать из города
Ав город В.
101.В таблице приведены расстояния (в милях) между шестью городами Ирландии.
|
Атлон |
Дублин |
Голуэй |
Лимерик |
Слайго |
Уэксфорд |
Атлон |
¾ |
78 |
56 |
73 |
71 |
114 |
Дублин |
78 |
¾ |
132 |
121 |
135 |
96 |
Голуэй |
56 |
132 |
¾ |
|
85 |
154 |
Лимерик |
73 |
121 |
64 |
¾ |
144 |
116 |
Слайго |
71 |
135 |
85 |
144 |
¾ |
185 |
Уэксфорд |
114 |
96 |
154 |
116 |
185 |
¾ |
Используя алгоритм поиска минимального остовного дерева, найдите сеть дорог минимальной общей длины, связывающую все шесть городов.
102. Найдите хроматическое число графа, заданного матрицей смежности:
0 |
1 |
0 |
1 |
0 |
1 |
||
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
0 |
||
|
0 |
1 |
0 |
1 |
0 |
0 |
|
|
|
||||||
1 |
0 |
1 |
0 |
1 |
0 |
||
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
||||||
|
|
0 |
0 |
0 |
1 |
|
|
1 |
0 |
103. Найдите хроматический индекс (наименьшее число цветовых классов при реберной раскраске) графа, заданного диаграммой:
Рис. 3.30.
104. Найдите хроматическое число графа на рисунке 3.31.
164
Рис. 3.31.
Раздел 4. Алгебра логики.
1. Установите, истинно или ложно высказывание:
1)2Î{х| 2х³-3х²+1=0,хÎR};
2)-3Î{х ½ х3 -1 <-2, хÎR};
х2 + 2
3){1}ÎN;
4){1}ÎР(N), где Р(N) – множество всех подмножеств множества N;
5)ÆÎÆ;
6)ÆÎ{Æ};
7){1,-1,2}Ì{х| х³+х²-х-1=0, хÎZ};
8){х| х³+х²-х-1=0, хÎZ}Ì{1,-1,2};
2.Какие из следующих предложений являются высказываниями?
Для высказываний определите истинностное значений.
1)15 кратно 3, но не кратно 4;
2)Каждое действительное число х удовлетворяет неравенству х²³0 ;
3)это предложение ложно;
4)Пушкин автор «Медного всадника»;
5)p = 3,14 ;
6)раскройте учебник на странице 23;
165
7)эта задача легкая;
8)Да здравствует математика!
3.Запишите символически следующие высказывания, употребляя буквы для обозначения простых высказываний:
1)3 есть простое число и 9 есть составное число;
2)3 – иррациональное число или существует рациональное число, не являющееся целым;
3)Петр встанет, и он или Иван уйдет;
4)Петр встанет и уйдет, или Иван уйдет;
5)студент не может заниматься, если он устал или голоден;
6)в шахматном турнире ни Петр, ни Иван не выиграли свои отложенные
партии;
7)в степи не будет пыльных бурь тогда и только тогда, когда будут лесо-
защитные полосы; если лесозащитных полос не будет, то пыльные бури унич-
тожат посевы и нанесут урон хозяйству;
8)для того чтобы натуральное число а было нечетным, достаточно, чтобы
абыло простым и большим двух;
9)необходимое и достаточное условие для жизни растений состоит в на-
личии питательной почвы, чистого воздуха и солнечного света;
10)необходимым условием сходимости последовательности S является ограниченность S;
11)если «Спартак» или «Динамо» проиграют и «Торпедо» выиграет, то
«Арарат» потеряет первое место и, кроме того «Заря» покинет высшую лигу.
4. Пусть v1 будет «сегодня светит солнце», v2 – « сегодня идет снег», v3 –
«сегодня пасмурно», v4 – « вчера было ясно». Переведите на обычный язык
следующие высказывания:
1) v1 |
v3 |
; |
|
|
2) v2 v3 ; |
3) v1 |
v2 v3 |
; |
||||||||||
|
v1 → |
|
|
|
|
|
|
↔ v |
|
|
|
v2 → v3 |
|
v |
||||
|
v3 |
v2 |
|
|
|
|
|
|
||||||||||
4) |
; |
5) |
v |
4 |
; |
6) ( |
) |
|||||||||||
|
|
|
|
|
1 |
|
|
|
1 . |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
166 |
|
|
|
|
|
|
5. Придумайте два высказывания, являющиеся дизъюнкцией трех высказы-
ваний, одно из которых истинно. а другое ложно.
6. Проверьте, не составляя таблиц истинности, являются ли следующие формулы тождественно истинными:
1) |
р→р ; |
|
|
|
2) р |
р |
; |
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
р ↔ |
|
|
; |
|
|
|
|
|
|||||
3) |
|
р |
|
; |
|
|
|
|
|
|
|
|
4) |
|
|||||||||||||||
|
р |
|
|
|
|
|
|
|
|
р |
|
||||||||||||||||||
5) |
|
|
|
→ р ; |
|
|
|
6) р↔р ; |
|
||||||||||||||||||||
|
р |
|
|
|
|
||||||||||||||||||||||||
7) (р р)→р ; |
|
|
|
8) |
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
р ( р ↔ |
|
|
|
; |
|
|||||||||||||||||||||
|
|
|
|
р) |
|
||||||||||||||||||||||||
9) |
( р → р) |
|
|
; |
|
|
|
10) |
|
р ↔ р ( |
|
→ р р) ; |
|
||||||||||||||||
р |
|
|
|
|
р |
|
|||||||||||||||||||||||
|
|
р ( р ↔ |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
11) |
|
|
|
) |
; |
|
|
12) |
|
р → |
|
|
|
; |
|
||||||||||||||
|
р |
|
|
|
р |
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
14) ( р р) → ( р р) |
|
||||||||||||||||||||
13) |
|
р ↔ |
|
; |
|
|
|
|
|||||||||||||||||||||
|
р |
|
|
|
|
||||||||||||||||||||||||
7. Найдите логические значения х, у, z, |
при которых выполняются равен- |
||||||||||||||||||||||||||||
ства: 1) |
(1→х)→у=0; |
2) х у = |
|
; |
|
3) (х ( у → х)) → z = 0 ; |
4) |
||||||||||||||||||||||
х |
|
ху ↔ ( у z) = 1
8.При каких значениях переменных следующие формулы ложны:
1) ((х → ( у z)) → ( y → x)) → y ; 2) (x y) → ((x y) (x y)) .
9. 1) Известно, что импликация х→у истинна, а эквивалентность х↔у лож-
на. Что можно сказать о значении импликации у→х?
2) Известно, что эквивалентность х↔у истинна. Что можно сказать о зна-
чении x ↔ y и x ↔ y ?
3) Известно, что х имеет значение 1. Что можно сказать о значениях им-
пликации x y → z ; x → ( y z) ?
4) Известно, что х→у имеет значение 1. Что можно сказать о значениях
z → (x → y) ; |
x → y |
→ y ; (x → y) → z ? |
10. Составьте таблицы истинности для формул:
167
1) |
|
|
|
|
|
|
; |
|
|
|
|
|
|
|
|
2) (x y) → (х |
|
|
|
|
|
→ |
|
) ; |
|||||||||||||
x1 |
|
x2 |
|||||||||||||||||||||||||||||||||||
у |
х |
у |
|||||||||||||||||||||||||||||||||||
3) (x1 x2 ) x3 ; |
4) x |
|
→ ( у |
|
→ |
|
|
) ; |
|
|
|||||||||||||||||||||||||||
y |
х |
z |
|||||||||||||||||||||||||||||||||||
5) х → |
|
|
|
; |
|
|
|
|
|
|
6) (x → |
|
) ( y x |
|
|
|
) ; |
||||||||||||||||||||
у z |
y |
x |
y |
||||||||||||||||||||||||||||||||||
7) |
|
y ↔ x |
|
; |
|
|
|
8) (x → y) → ( y → z) → (z → x) ; |
|||||||||||||||||||||||||||||
x |
z |
||||||||||||||||||||||||||||||||||||
9) (x1 → |
|
) → ( |
|
|
|
) ; |
10) ( |
|
z) ( у → (u → x)) ; |
||||||||||||||||||||||||||||
x2 |
x1 x2 |
х3 |
|||||||||||||||||||||||||||||||||||
x |
11)(х → ( у z)) ↔ ((x → y) (x → z)).
11.Система классификации получает на вход устройство, данные о котором заносит в таблицу «Оборудование» для дальнейшей обработки информации.
Таблица содержит поля «Устройство», «Назначение» и «Год выпуска» с сим-
вольными именами А, В и С, соответственно. Система формирует запросы в виде переключательных (логических) функций. Переменные функции f(x,y,z)
определены как х = ( А ¹"printer") , у = (В ¹"print") , z = (С = 2003) . Определите,
для каких ниже перечисленных функций является единичной запись со значе-
ниями: Устройство=«printer», Назначение=«print», Год выпуска=2003.
•(x « y) Ù z
•x Å y Å z
•x Ù ( у Å z)
•(x ↓ y) z
•x Ú ( у « z)
Укажите не менее двух вариантов ответа.
12. Докажите равносильности:
1) (х у) (х |
|
у |
) ≡ х ; |
2) х ( |
х |
у) ≡ х у ; |
|||||||||||||
3) х ↔ у ≡ |
|
↔ |
|
|
; |
4) х у |
|
у |
|
|
|
≡ х → у; |
|||||||
х |
у |
х |
х |
у |
|||||||||||||||
5) х → |
|
≡ у → |
|
; |
6) х → ( у → z) ≡ x y → z ; |
||||||||||||||
у |
х |
7)x ≡ (x y z) (x y z) (x y z) (x y z) ;
8)(x y) (z t) ≡ x z y z x t y t ;
168
9)x y z t ≡ (x z) ( y z) (x t) ( y t) ;
10)x1 x2 ... xn → y ≡ x1 → (x2 → (... → (xn → y)...)) .
13.Докажите тождественную истинность или тождественную ложность формул:
1) х у → х; |
2) (х → у) → ( |
у |
→ |
х |
) ; |
|
|||||||||||||
3) х → (х у) ; |
4) ( |
|
→ |
|
) → (х → у) ; |
||||||||||||||
у |
х |
||||||||||||||||||
5) (х → у) (х → |
|
) → |
|
; |
6) х (х → у) (х → |
|
) ; |
||||||||||||
у |
х |
у |
|||||||||||||||||
7) х |
|
→ у |
|
; |
8) (х → ( у → z)) → ((x → y) → (x → z)) ; |
||||||||||||||
х |
у |
9)(x → ( y → z)) → (x y → z) ; 10) (x y → z) → (x → ( y → z)) ;
11)(z → x) → ((z → y) → (z → x y))
12)(x → z) → (( y → z) → ((x y) → z)) .
14.Используя основные равносильности, нужно доказать или опровергнуть:
1)(х → у) → z ≡ x → ( y → z) ; 2) (х у → z) → (x → z) ≡ x y z ;
3) х ( у → z) ≡ x y → x z ; |
4) x ( y → z) ≡ x y → x z ; |
|||||||
|
6) |
|
|
≡ х у |
|
|
|
; |
5) x → y ≡ y → x ; |
х ↔ |
|
||||||
у |
х |
у |
7 ) (x → y) (x → z) → (x → ( y → z)) ≡ x y z ;
8)(x y → z) → (z → x y) ≡ (z → x) (z → y) ;
9)x z → y t ≡ (x → y) (z → t) ;
10)х → ( у → z) ≡ (x → y) → (x → z) .
15.Пусть F – тождественно ложная формула.
Докажите, что х у → F ≡ x → y .
16.Найдите х, если x a x a ≡ b .
17.Используя основные равносильности, упростите следующие формулы:
1) |
х → у |
|
х у |
у ; |
2) (x → y) (x y z) (x → z) |
z |
; |
||||||
3) х у |
|
y ; |
4) |
|
x |
|
x y z ; |
||||||
у z |
x y z |
y z |
|||||||||||
|
|
|
|
|
|
|
169 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5) z → |
y |
|
y x |
( y |
z |
→ |
y |
) ; |
6) |
|
х → у |
|
z → y |
y ; |
||||||||
7) (x → y) → |
|
; |
|
|
|
8) x y x |
|
( |
|
→ y) x y |
|
. |
||||||||||
y |
|
|
|
z |
x |
z |
18. Последовательность высказываний ( an ) определяется следующим рекур-
рентным выражением: an = an−1 (an−2 an−3 ) , n>3.
Высказывания а1 , a2 , a3 заданы, причем a1 и a3 истинны, а a2 ложно.
Истинно или ложно высказывание an ? Как выражается an через а1 , а2 , а3 ?
19.Выразите все основные операции:
1)через операции дизъюнкцию, конъюнкцию и отрицание;
2)через конъюнкцию и отрицание;
3)через импликацию и отрицание.
20.Автоматическая прропускная система регистрирует работников предприятия на проходной и заносит данные в таблицу «Рабочее время» для дальнейшей обработки информации. Таблица содержит поля «Код сотрудника», «Отдел», «Время прихода» и «Пропуск» с символьными именами В, В, С и D, соответственно. Система формирует запросы в виде переключательных (логических) функций. Нужно установить соответствие между запросами к данным из таблицы и двойственными запросами.
Запросы к данным из таблицы:
1)((( А =1618) « (В = R22)) ® (C ¹"08 : 55")) Ù (D =1)
2)(( А =1618) Å (В = R22)) Ú ((C ¹"08 : 55") « (D =1))
3)( А ¹ 1618) Å (В ¹ R22) Å (C ="08 : 55") Å (D =1)
Двойственные запросы:
(( А ¹1618) « (В ¹ R22)) Ù ((C ="08 : 55") Å (D ¹1))
(( А =1618) Å (В = R22)) « ((C ¹"08 : 55") Å (D ¹ 1))
((( А ¹1618) « (В ¹ R22)) Ù (C ¹"08 : 55")) Ú (D =1)
( А =1618) « (В ¹ R22) « (C ¹"08 : 55") Å (D ¹ 1)
170