9968
.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 |
|
|
|
||||||
|
1 |
0 |
0 |
0 |
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)= 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 v3 |
v2 |
|
|
|
|
|
v2 v3 |
|
v |
|||||
4) |
; |
v v |
6) ( |
) |
|||||||||||
|
|
|
|
|
5) 1 |
4 ; |
|
|
1 . |
||||||
|
|
|
|
|
|
|
|
|
166 |
|
|
|
|
|
|
5. |
Придумайте два высказывания, являющиеся дизъюнкцией трех высказы- |
||||||||||||||||||||||||||||
ваний, одно из которых истинно. а другое ложно. |
|
||||||||||||||||||||||||||||
6. |
Проверьте, не составляя таблиц истинности, являются ли следующие |
|
|||||||||||||||||||||||||||
формулы тождественно истинными: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1) |
р р ; |
|
|
|
2) р р ; |
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3) |
|
р р ; |
|
|
|
4) |
р р ; |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
5) |
|
р р ; |
|
|
|
6) р р ; |
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7) (р р) р ; |
|
|
|
8) р ( р р) ; |
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
9) |
( р р) р ; |
|
|
|
10) |
|
р р ( р р р) ; |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11) |
р ( р р) |
; |
|
|
12) |
|
р р ; |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13) |
р р ; |
|
|
|
14) ( р р) ( р р) |
|
||||||||||||||||||||||
7. |
Найдите логические значения х, у, z, |
при которых выполняются равен- |
|||||||||||||||||||||||||||
|
|
(1х) у=0; |
|
|
|
|
3) (х ( у х)) z 0; |
|
|||||||||||||||||||||
ства: |
1) |
2) х у х ; |
|
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) z ? |
|
x y y ; |
10. Составьте таблицы истинности для формул:
167
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2) (x y) (х у х у) ; |
|||||||
1) |
|
x1 x2 ; |
||||||||||||||||||||
3) (x1 x2 ) x3 ; |
4) |
x y ( у х z) ; |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
5) |
|
х у z ; |
6) (x y) ( y x x y) ; |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
8) (x y) ( y z) (z x) ; |
|||||||||||
7) |
|
x y x z ; |
||||||||||||||||||||
|
|
|
|
|
|
|
|
10) (x z) ( у (u x)) ; |
||||||||||||||
9) |
(x1 x2 ) (x1 x2 х3 ) ; |
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) |
х у х у х у х у ; |
||||||||||||||
|
|
|
|
|
|
|
х ( у z) x y z ; |
||||||||||
5) |
х у у х ; |
6) |
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) х (х у) (х у) ; |
|||||||||||||||||||
|
|
|
|
|
|
8) (х ( у z)) ((x y) (x z)) ; |
||||||||||||||
7) |
х х у у ; |
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 ; |
||||||
|
x y y x ; |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
5) |
6) |
х у х у х у ; |
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) |
х у у z y ; |
4) x y z x y z x y z ; |
|||||||||||
|
|
|
|
|
|
|
169 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5) |
z y y x ( y z y) ; |
6) х у z y y ; |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
7) (x y) y ; |
|
|
|
8) x y x z (x y) x y 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