Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Дискретная математика

Читайте также:
  1. Вопросник для математика и логика.
  2. Математика
  3. Математика 11 класс
  4. Математика и компьютеры на службе прогнозирования
  5. Математика и применение математических знаний
  6. Математика и применение математических знаний для учащихся с нарушениями речи.

 

1) используя правила де Моргана, получить ДНФ и упростить её.

 

Решение:

2) даны две функции , Требуется:

а) для функции составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. Упростить, если возможно, СДНФ.

б) для функции составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную РКС.

в) составить таблицу Поста для системы функций , , проверить полноту системы и выбрать базисы, если она полная.

,

Решение:

а)

x y
       
       
       
       

 

Найдем полином Жегалкина

СКНФ:

x y
       

 

СКНФ=

СДНФ:

x y
       
       
       

 

СДНФ=

б)

x y z
           
           
           
           
           
           
           
           

Функция является противоречием

Так как функция является противоречием, то полином Жегалкина равен 0, проверим это:

СКНФ:

x y z
           
           
           
           
           
           
           
           

 

СКНФ=

СДНФ:

Так как все значения функции равны нулю, функция не имеет СДНФ, соответственно невозможно получить минимальную ДНФ

в)

Рассмотрим заданные функции:

   
   
   
   
   
   
   
   

 

1. , – функции, сохраняющие ноль.

2. – функция, сохраняющая единицу. – – функция, не сохраняющая единицу.

3. – функция, не самодвойственная. – функция самодвойственная

4. – линейная – линейная

5. , – функции монотонные

  T0 T1 S M L
+ + - + +
+ - + + +

Система не является полной, так как она целиком содержится в классах T0, М и L

3) дан граф. Составить для данного графа структурную матрицу. Найти: а) все простые пути из вершины i в вершину j; б) совокупность всех сечений между вершинами i и j.

i=3, j=5

Решение:

Составим структурную матрицу:

а) найдем все простые пути из вершины 3 в 5:

Вычислим минор , заменяя сложение и вычитание на дизъюнкцию, а умножение на конъюнкцию.˅

Получили все простые пути:

3→2→5

3→2→1→5

б) найдем совокупность сечений между 3 и 5 вершиной:

Получили совокупность сечений.

4)

заданы сеть и начальный поток f. Требуется построить максимальный поток, считая вершину с номером 1 источником и вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна максимальному потоку.

Решение:

Путь из s=1 в t=4, по которому поток может быть увеличен, состоит из прямых дуг, соединяющих вершины s=1→3→t=4. Пометки указанных вершин

 

Добавка к потоку:

Построим новый поток ,

Путь из s=1 в t=4, по которому поток может быть увеличен, состоит из прямых и обратных дуг, соединяющих вершины s=1→2←3→t=4. Пометки указанных вершин

Построим новый поток ,

Путь из 1 в 4, на котором возможно увеличение потока построить не удалось, до стока t не дошли, поток максимален

Найдем минимальное сечение. Помеченные вершины М1={1,2}. Непомеченные вершины М2={3,4}. Прямые насыщенные дуги, идущие из М1 в М2, образуют минимальное сечение . Величина этого сечения равна 5+2+1+4=12 и совпадает с величиной максимального потока

5) на указанном множестве задано отношение. Для каждого отношения нужно: а) записать отношение R; б) построить матрицу смежности и граф отношения; в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.

На множестве А={1,2,3,4,5,6} задано отношение R: xRy тогда и только тогда, когда x и y имеют общий делитель, отличный от 1

Решение:

а) Запишем отношение

Отношение R определяется множеством пар

 
(2,2) (2,4) (2,6)
(3,3) (3,6)
(4,2) (4,4) (4,6)
(5,5)
(6,2) (6,3) (6,4) (6,6)

 

 

 

 

б) построим матрицу смежности и граф отношения

Проверим свойства:

Рефлексивность. Отношение не рефлексивное, так как для x =1 отношение не выполняется, так как 1 имеет только один делитель, равный 1

Симметричность. Отношение симметрично, так как если x и y имеют общий делитель, отличный от единицы, то и y и x так же, имеют его

Транзитивность. Отношение не транзитивно, покажем на примере:

x и y имеют общий делитель 3, z и y имеют общий делитель 2, а x и z не имеют общего делителя, отличного от единицы

 

 


Дата добавления: 2015-07-11; просмотров: 811 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Примеры определения строения молекул по методу Гиллеспи| Принцип работы автомобильного видеорегистратора

mybiblioteka.su - 2015-2024 год. (0.016 сек.)