9968

91. Даны коды деревьев:

а) (0100011001101011); б) (00101001110001010111).

Сколько вершин имеет каждое из этих деревьев? Постройте соответству-

ющие деревья.

92. Запишите формулой булеву функцию, которая задана семантическим деревом на рисунке 3.26.

Рис. 3.26.

93. В таблице приведена стоимость перевозок между соседними железнодо-

рожными станциями. Укажите схему, соответствующую таблице

94. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями. Укажите таблицу, для кото-

рой выполняется условие: «Минимальная стоимость проезда из А в B не боль-

ше 6».

Найдите длину наименьшего пути, по которому можно доехать из города

Ав город В.

101.В таблице приведены расстояния (в милях) между шестью городами Ирландии.

Используя алгоритм поиска минимального остовного дерева, найдите сеть дорог минимальной общей длины, связывающую все шесть городов.

102. Найдите хроматическое число графа, заданного матрицей смежности:

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)если «Спартак» или «Динамо» проиграют и «Торпедо» выиграет, то

«Арарат» потеряет первое место и, кроме того «Заря» покинет высшую лигу.

ху ( у z) 1

8.При каких значениях переменных следующие формулы ложны:

1) ((х ( у z)) ( y x)) y ; 2) (x y) ((x y) (x y)) .

9. 1) Известно, что импликация х у истинна, а эквивалентность х у лож-

на. Что можно сказать о значении импликации у х?

2) Известно, что эквивалентность х у истинна. Что можно сказать о зна-

10. Составьте таблицы истинности для формул:

167

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. Докажите равносильности:

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.Докажите тождественную истинность или тождественную ложность формул:

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 ;

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.Используя основные равносильности, упростите следующие формулы:

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