Главная страница
Навигация по странице:

  • Дистибутивный (распределительный) закон Законы де Моргана (законы общей инверсии или дуальности)

  • Таблично-графический

  • вопросы по дискретке. множество натуральных чисел и 0


    Скачать 1,37 Mb.
    Название множество натуральных чисел и 0
    Анкорвопросы по дискретке.pdf
    Дата07.10.2019
    Размер1,37 Mb.
    Формат файлаpdf
    Имя файлавопросы по дискретке.pdf
    ТипДокументы
    #13336
    КатегорияМатематика
    страница1 из 3

    Подборка по базе: Факториалы чисел до 100.doc.
      1   2   3

    1. Множества. Основные понятия, определения. Подмножества. Равенство и мощность множеств. Подмножеством (совокупностью М понимают набор объектов произвольной природы, которые называются элементами множества. Если число элементов конечно, множество называется конечным. В противном случае говорят о бесконечном множестве. Множество состоит из некоторых объектов различных и различаемых, которые называются элементами множества Например
    N − Множество натуральных чисел.
    N0 − множество натуральных чисел и 0.
    Z − Множество целых чисел.
    Q − Множество рациональных чисел. Множество Q также можно представить в виде множества дробей p/q , где p и q – целые числа.
    R − Множество действительных чисел. Одинаковые элементы, входящие во множество, не различаются и считаются один раз
    Определение. Говорят, что всякий элемент х множества М принадлежит Ми пишут хÎМ. Если же предмет хне является элементом множества М, то говорят, что хне принадлежит Ми пишут хÏМ. Если множество А состоит из элементов а, а, … , а
    п
    , будем писать а, а,
    … , а
    п
    Î А или А = а, а, … , а
    п
    }. При этом порядок перечисления элементов не имеет значения. Множества, содержащие в качестве элементов другие множества, называются семействами (классами. Множество, не содержащее ни одного элемента, называется пустыми обозначается
    . Существование пустого множества – это постулат. Если все элементы данной системы множеств принадлежат какому-то одному большому множеству, такое множество называется универсальным множеством или универсумом и обозначается U Подмножества. Пусть задано множество А. Множество В, состоящее из элементов множества А, называется подмножеством А Например. A={a, w, b, c} и В, a, b}, тогда В А или А В (В включается в А или А включается в В. Пустое множество является подмножеством любого множества. Два множества называются равными, если они состоят из одних и тех же элементов. А,
    2, а.
    В={а,
    3, а,
    3,
    2, а. Имеем
    А=В. Теорема. Множество А равняется множеству В, если А является подмножеством В, а В является подмножеством А. Количество элементов, входящих во множество, называется его мощностью. Два множества называются равномощными, если существует метод, позволяющий каждому элементу одного множества поставить в соответствие элемент другого множества. Алгебра множеств. Операции надмножествами. Свойства. Алгебра множеств совокупность тождеств, справедливых независимо оттого, какое универсальное множество и какие именно его подмножества входят в эти равенства.
    1) Объединением множеств Аи В называется множество, состоящее из элементов, входящих или в А, или в В.
    2) Пересечение. А


    В Пересечением двух множеств называется множество, состоящее из элементов, входящих ив Аи в В.
    3) Разность. А. Разностью множеств Аи В называется множество, состоящее из элементов, входящих в А, ноне входящих в В.
    4) Дополнение. Ā
    . Дополнением множества А называется множество, состоящее из элементов не входящих в А Свойства операций
    3. Разбиение множеств на классы. Декартово произведение, степень. Свойства. Разбиение множества на классы (классификация) означает, что данное множество А разбивается на подмножества k1, k2, … , km таких, что Декартовым, или прямым, произведением множества А на множество В называется множество упорядоченных пар, 1-ый элемент которых принадлежит множеству А, а ой
    – множеству В Обозначается декартово произведение знаком

    . Для данных множеств получим А


    В, b1),( a1, b2),…,( a1, bm),…,( a2, b1),…,( an, bm)}. Мощность декартового произведения равна
    n

    m. Обозначение |A

    B| = n

    m. Декартова степень Если в качестве множества В в декартовом произведении выбрать множество А, мы будем говорить о декартовом квадрате. Декартово произведение n множеств Набор
    n элементов будем называть кортежем Декартовым произведением А

    А А …

    А будем называть множество упорядоченных кортежей, первый элемент которых принадлежит множеству А, второй множеству Аи т.д. Свойства декартового произведения. Отношения. Композиция отношений. Виды отношений. Функции. Пусть заданы два множества Аи В. Найдем А


    В. Подмножество k А

    В называется отношением из множества А во множество В Отношения задаются знаками =, <, >,

    ,

    и т.д. Пример А
    = {2,3,4}, B={1,4,3}.
    A

    B = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}. Выделим отношения больше (>) : k1 = {(2,1),(3,1),(4,1),(4,3)} и меньше (<) : k 2 = {(2,4),(2,3),(3,4)}. Композицией отношений из А в В называется множество пара) таких, что, а € Аи существует такое с € С, что ас и (с, b) k2. виды отношений Инъекция Если каждый элемент множества А соответствует элементу из множества В, то отношение f называется инъективным.
    Сюръекция. Если для каждого элемента y множества В существует элемент х А, соответствующий элементу y, то такое отношение f называется сюръекцией.
    Биекция. Если для каждого элемента y B существует ровно один элемент х А, которому соответствует y , то такое отношение называется биективным.
    Биективное отношение инъективно и сюръективно.
    Биективное отношение имеет обратное отношение. Выберем отношение f А

    В
    = {( a1, b1), (a2, b2),…}, состоящее из пар таких, что ai aj, i, j = 1,2,3,…, те. отношение, в котором все первые элементы пар различны. Такие отношения называются функциями.


    5. Комбинаторика. Основные понятия и определения. Размещения. Задачи, в которых требуется определить количество возможных операций, называются комбинаторными Пусть имеется группа некоторых объектов a1, a2, …, am которые мы будем называть элементами Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями Из этих соединений выделим классы, которые будем называть
    размещениями.
    Размещениями из m элементов по n называются соединения, каждое из которых содержит n элементов, взятых изданных и которые отличаются друг от друга или элементами, или их порядком. Предполагается, что элементы водном размещении не повторяются. Формула числа размещений без повторений Или Каждое размещение содержит одно и тоже количество элементов, взятых изданных элементов Рассмотрим размещения из m элементов по n, в которых каждый элемент может повторяться. Такие размещения называются размещениями с повторениями Таким образом, так как каждый элемент попадает в комбинацию m способами, a комбинаций n, то
    6. Комбинаторика. Основные понятия и определения. Перестановки. Задачи, в которых требуется определить количество возможных операций, называются комбинаторными Пусть имеется группа некоторых объектов a1, a2, …, am которые мы будем называть элементами Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями Из этих соединений выделим классы, которые будем называть
    размещениями. Размещения из n элементов по n, каждое из которых отличается друг от друга только порядком элементов, называются перестановками Их число обозначается Pn:
    Pn = А = n·(n-1) ·(n-2) ·…·2·1
    , то есть Pn = n! Пример Сколькими способами могут сесть 6 человек на местную лавочку Решение В данном случае каждое расположение лиц на лавочке отличается от другого расположения только порядком. Поэтому мы имеем дело с перестановками
    P6 = 6! = 720. Перестановки с повторениями


    7. Комбинаторика. Основные понятия и определения. Сочетания. Задачи, в которых требуется определить количество возможных операций, называются комбинаторными Пусть имеется группа некоторых объектов a1, a2, …, am которые мы будем называть элементами Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями Из этих соединений выделим классы, которые будем называть
    размещениями. Сочетания – это размещения, каждое из которых отличается от других хотя бы одним элементом. Другими словами, сочетания
    – это соединения, содержащие n элементов изданных, отличающиеся хотя бы одним элементом. Пример В группе 20 студентов. Требуется выбрать 5 делегатов на конференцию. Сколькими способами это можно сделать Решение Так как внутри каждой пятерки делегатов перестановки дают одну и туже пятерку, то каждая пятерка должна отличаться от других хотя бы одним делегатом. В данном случае мы должны посчитать число сочетаний из 20 по 5: Сочетания с повторением Пример На почте имеются открытки четырех видов красные, желтые, зеленые и синие. Требуется 10 открыток. Сколькими способами можно их скомбинировать Решение Пусть мы отобрали 4 красных, 2 желтых, 2 зеленых и 2 синих открытки. Составим кортеж из
    0 и
    1. Выпишем столько единиц, сколько красная открытка встречается в нашем наборе, и поставим 0: 11110. Затем добавим кортеж для желтых − 110. Получим
    11110110. Добавим кортеж для зеленых и синих открыток. В последнем 0 не ставим. Получим кортеж 1111011011011. В нем 10 единиц и 3 нуля. Общая длина кортежа – 13. Таких кортежей Общая формула

    8. Булева алгебра. Основные аксиомы, теоремы и тождества. Логические переменные и логические функции. Алгебра логики (булева алгебра) — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений истинности или ложности) и логических операций над ними. Отрицание Высказывание , которое истинно, если р ложно, и ложно, если р истинно, называется отрицанием. Конъюнкция (логическое умножение Пусть даны два высказывания р и q. Конъюнкцией двух высказываний называется высказывание, которое истинно только тогда, когда истинны оба высказывания. Дизъюнкция (логическое сложение. Дизъюнкцией двух высказываний называется высказывание, которое ложно только тогда, когда оба высказывания ложны. Задается союзом ИЛИ. Импликация Импликацией двух высказываний р и q называется высказывание, которое ложно только тогда, когда р
    – истинно, а q – ложно. ЕСЛИ р, ТО q. Обозначение
    Эквиваленция.
    Эквиваленцией двух высказываний р и q называется высказывание, которое истинно, если оба высказывания принимают одинаковые значения. В словесной формулировке тогда и только тогда необходимо и достаточно если и только если. Обозначение p ↔ q Аксиомы алгебры логики Аксиомы конъюнкции Аксиомы дизъюнкции Аксиомы отрицания если
    , то
    ; если
    , то Теоремы алгебры логики Теоремы исключения констант Теоремы идемпотентности (тавтологии, повторения для n переменных Теорема противоречия Теорема "исключённого третьего Теорема двойного отрицания (инволюции Законы алгебры логики Ассоциативный (сочетательный) закон Коммутативный (переместительный) закон
    Дистибутивный (распределительный) закон Законы де Моргана (законы общей инверсии или дуальности) Закон поглощения (элиминации)
    Закон склеивания (исключения

    9. Способы задания логических функций и их разновидности. Различают несколько способов задания ФАЛ, основными из которых являются табличный, аналитический, цифровой, таблично-графический, геометрический. Табличный способ предусматривает задание ФАЛ таблицей истинности (риса, в которой указывают, какие из двух возможных значений «0» или «1» принимает функция на каждом наборе аргументов. Аналитический способ задания предполагает запись функции в виде формализованного выражения, составленного с использованием математического аппарата алгебры логики. Цифровой способ задания ФАЛ реализуется посредством записи функции в виде совокупности рабочих, запрещённых и условных наборов аргументов.
    Таблично-графический или координатный способ предусматривает задание ФАЛ ввиде координатных карт состояний, называемых картами Карно. Графический способ задания ФАЛ предусматривает изображение функции в виде мерной геометрической фигуры, вершинам которой соответствуют наборы значений аргументов данной функции.
    10. Аналитическое представление логических функций в совершенных нормальных формах. СДНФ
    . Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) K
    i


    l
    m
    K
    K
    K
    x
    x
    f






    2 1
    1
    ,
    ,
    ,
    1

    l
    , называется дизъюнктивной нормальной формой (ДНФ) этой функции. Если все конъюнктивные термы в ДНФ являются минтермами, те. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ) этой функции
    Пусть имеем таблично заданную функцию f
    (x
    1
    , x
    2
    , x
    3
    ) На основании формулы (2.6) получаем


    3 2
    1 3
    2 1
    3 2
    1 3
    2 Как видно, при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов, при которых функция принимает значение 1.
    11. Аналитическое представление логических функций в совершенных нормальных формах. СКНФ. Если все дизъюнктивные термы КНФ являются макстермами, те. содержат в точности по одной все логические переменные функции, взятые с отрицаниями или без них, то такая КНФ называется совершенной конъюнктивной нормальной формой (СКНФ) этой функции
    Любая булева функция неравная тождественно 1) может быть представлена в СКНФ, причём такое представление единственно. Дана таблица истинности В отличие от СДНФ, при составлении СКНФ в таблице истинности логической функции нужно смотреть комбинации переменных, при которых функция принимает значение 0, и составить конъюнкцию соответствующих макстермов, но переменные нужно брать с обратной инверсией

     
    


    
    

    3 2
    1 3
    2 1
    3 2
    1 3
    2 1
    3 2
    1 3
    2 Нужно отметить, что непосредственно перейти от СДНФ функции к её СКНФ или наоборот невозможно. При попытке таких преобразований получаются функции, обратные по отношению к желаемым. Выражения для СДНФ и СКНФ функции непосредственно можно получить только из её таблицы истинности.
    12. Сущность минимизации логических функций и ее значение. Метод Квайна. Минимальной формой логической функции в некотором базисе можно считать такую, которая содержит минимальное число суперпозиций функций базиса, допуская и скобки. Однако трудно построить эффективный алгоритм такой минимизации с получением минимальной скобочной формы. Метод Квайна
    Минимизируемая функция представляется в СДНФ, и к ней применяются всевозможные операции неполного склеивания
    i
    i
    i
    i
    x
    K
    x
    K
    K
    x
    K
    Kx




    ,
    (2.10) а затем поглощения
    K
    x
    K
    x
    K
    K
    i
    i



    ,
    (2.11) и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом. Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простыми очевидным способом Этот способ плох тем, что при такой непосредственной минимизации конъюнктивные термы
    i
    Kx
    или
    i
    x
    K
    исчезают, хотя возможны ещё случаи их использования для склеивания и поглощения с оставшимися термами. Нужно отметить, что метод Квайна является достаточно трудоёмким, поэтому вероятность допущения ошибок вовремя преобразований достаточно велик. Но его преимуществом является то, что теоретически его можно использовать для любого числа аргументов и при увеличении количества переменных преобразования усложняются не так сильно.
    13. Сущность минимизации логических функций и ее значение. Метод Мак-Класки
    . Минимальной формой логической функции в некотором базисе можно считать такую, которая содержит минимальное число суперпозиций функций базиса, допуская и скобки. Однако трудно построить эффективный алгоритм такой минимизации с получением минимальной скобочной формы. Метод Квайна - Мак-Класки. Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом
    1. Все конституанты единицы из СДНФ булевой функции f записываются их двоичными номерами.
    2. Все номера разбиваются на непересекающиеся группы. Признак образования й группы i единиц в каждом двоичном номере конституенты единицы.
    3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).
    4. Склеивания производят всевозможные, как ив методе Квайна.
    Неотмеченные после склеивания номера являются простыми импликантами. Нахождение минимальных ДНФ далее производится по импликантной матрице, как ив методе Квайна.
    14. Сущность минимизации логических функций и ее значение. Метод Блейка-Порецкого. Минимальной формой логической функции в некотором базисе можно считать такую, которая содержит минимальное число суперпозиций функций базиса, допуская и скобки. Однако трудно построить эффективный алгоритм такой минимизации с получением минимальной скобочной формы. Метод Блейка - Порецкого.

    " Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания
    Ax v B/x = Ax v B/x v AB, справедливость которой легко доказать. Действительно,
    Ax = Ax v ABx; B/x = B/x v AB/x. Следовательно, Ах v В/х = Ах v АВх v В/х v АВ/х = Ах V В/х V АВ. В основу метода положено следующее утверждение если в произвольной ДНФ булевой функции f произвести всевозможные oбобщенные склеивания, а затем выполнить все поглощения, тов результате получится сокращенная ДНФ функции f.

      1   2   3


    написать администратору сайта