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

  • Комбинаторный признак умножения. Количество битовых строк длины k

  • Количество всех подмножеств k

  • Перестановки, размещения, сочетания без повторения.

  • Бином Ньютона. Треугольник Паскаля. Свойства биномиальных коэффициентов. Формула бинома Ньютона

  • треугольник Паскаля

  • Перестановки, размещения, сочетания с повторениями.

  • 7. Признак клеток (Дирихле).

  • Признак математической индукции. Индукция

  • . Высказывания. Отрицание, конъюнкция, дизъюнкция, их таблицы истинности.

  • 10. Импликация и эквиваленция, таблицы их истинности.

  • 11. Эквивалентные высказывания. Теорема о свойствах логических эквивалентностей.

  • 12. Тавтологии и противоречия, их свойства. Формула называется тавтологией

  • противоречием

  • 13. Умозаключения и правила вывода, доказательство от противного.

  • ВОПРОСЫ и ответы К ЭКЗАМЕНУ. Ответы к экзамену комбинаторный признак умножения. Количество битовых строк длины


    Скачать 2.8 Mb.
    НазваниеОтветы к экзамену комбинаторный признак умножения. Количество битовых строк длины
    Анкорlbcrhtn vfnfy
    Дата10.05.2023
    Размер2.8 Mb.
    Формат файлаdocx
    Имя файлаВОПРОСЫ и ответы К ЭКЗАМЕНУ.docx
    ТипОтветы к экзамену
    #1120624
    страница1 из 6
      1   2   3   4   5   6


    ВОПРОСЫ и ответы К ЭКЗАМЕНУ


    1. Комбинаторный признак умножения. Количество битовых строк длины k.

    Пусть задана последовательность событий E1, E2, E3, …Eтаких, что событие Е1осуществляется n1способами, и если события E1, E2, E3,...,Ек-1осуществились, то событие Ек может осуществиться nкспособами. Тогда существует n1х n2х n3х … х nтспособов осуществления всей последовательности событий.

    . Битовая строка это строка, состоящая из элементов множества

    {0, 1}, т.е. каждый из элементов имеет значение 0 или 1. Сколько существует битовых строк длины 5? Сколько существует битовых строк длины k?

    Поскольку каждый символ строки может иметь значение 1 или 0, то

    существует два варианта выбора для каждой позиции. Следовательно, существует 2 x 2 x 2 x 2 x 2 = 25 битовых строк длины 5. По аналогичным соображениям, имеется 2k битовых строк длины k.


    1. Количество всех подмножеств k - элементного множества.

    Число всех подмножеств из элементов равно N(M(A))=2^n

    1. Комбинаторный признак сложения.

     (Комбинаторный принцип сложения) Пусть S1, S 2S3,..,Sm – попарно непересекающиеся множества (т.е. SiSj = для всех  j), и пусть для каждого i, множество Si содержит niэлементов. Количество вариантов вы­бора из S1 или S2или S3 или ... или Smравно n1 + n2 + n3+ … + nmНа языке теории множеств утверждение теоремы имеет вид |S1 S2 S3 ... Sm|= |S1| + |S2| + |S3| + ... + |Sm|, где |S| обозначает количество элементов множества S.

    1. Перестановки, размещения, сочетания без повторения.

    Перестановками -называются наборы состоящие из одного и того элементов,следования элементов. Pn=n!

    Размещение –называются упорядоченные наборы из элементов выбранных из n элементов, которые отличаются друг от друга, как порядком следования, так и составом элементов. m

    A =n!/(n-m)!

    n

    Сочетание- называются

    элементов выбранных из n элементов, которые отличаются друг

    от друга составом элементов. m

    С =n!/m!(n-m)!

    n


    1. Бином Ньютона. Треугольник Паскаля. Свойства биномиальных коэффициентов.

    Формула бинома Ньютонадля натуральныхnимеет вид  , где   -биномиальные коэффициенты, представляющие из себя сочетания изnпоk,k=0,1,2,…,n, а "!" – это знак факториала).

    К примеру, известная формула сокращенного умножения "квадрат суммы" вида   есть частный случай бинома Ньютона приn=2.

    Выражение, которое находится в правой части формулы бинома Ньютона, называютразложениемвыражения(a+b)n, а выражение   называют(k+1)-ым членом разложения,k=0,1,2,…,n.

    Биномиальные коэффициенты для различныхnудобно представлять в виде таблицы, которая называется арифметическийтреугольник Паскаля. В общем виде треугольник Паскаля имеет следующий вид:


    Треугольник Паскаля чаще встречается в виде значений коэффициентов бинома Ньютона для натуральныхn:



    Боковые стороны треугольника Паскаля состоят из единиц. Внутри треугольника Паскаля стоят числа, получающиеся сложением двух соответствующих чисел над ним. Например, значение десять (выделено красным) получено как сумма четверки и шестерки (выделены голубым). Это правило справедливо для всех внутренних чисел, составляющих треугольник Паскаля, и объясняется свойствами коэффициентов бинома Ньютона.

    Для коэффициентов бинома Ньютона справедливы следующие свойства:

    • коэффициенты, равноудаленные от начала и конца разложения, равны между собой  ,p=0,1,2,…,n;

    • ;

    • сумма биномиальных коэффициентов равна числу2, возведенному в степень, равную показателю степени бинома Ньютона:  ;

    • сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.

    Первые два свойства являются свойствами числа сочетаний.


    1. Перестановки, размещения, сочетания с повторениями.

    Перестановка – _

    Размещение-




    Сочетание-



    7. Признак клеток (Дирихле).

    Принцип Дирихле — простой, интуитивно понятный и часто полезный метод для доказательства утверждений о конечном множестве. Этот принцип часто используется в дискретной математике, где устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках данное утверждение известно как «принцип голубей и ящиков, когда объектами являются голуби, а контейнерами — ящики.

    Этот принцип утверждает, что если множество из n элементов разбито на m непересекающихся частей, не имеющих общих элементов, гдеn > mто, по крайней мере, в одной части будет более одного элемента.

    На языке отображений эта формулировка означает, чтоесли в А (множестве предметов) больше элементов, чем в В (множестве ящиков), то не существует обратимого отображения А в В.

    Другая формулировка “ принципа Дирихле“:если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы двапредмета.

    В шутливой форме принцип Дирихле выглядит так: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “. [2]


    1. Признак математической индукции.

    Индукция – это переход от частного к общему, а дедукция наоборот – от общего к частному. Определение 2



    9. Высказывания. Отрицание, конъюнкция, дизъюнкция, их таблицы истинности.

    Высказываниемназывается повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.

    Например, «Москва – столица России», «число 2 больше 5» – высказывания. Первое высказывание является истинным, а второе – ложным.

    Отрицаниемвысказывания  называется высказывание («не », «неверно, что »), которое истинно, когда ложно, и ложно, когда истинно.

    Таблица истинности для отрицания:



    Конъюнкцией (логическим умножением) двух высказываний  , называется высказывание (« и »), которое истинно только в том случае, когда и оба истинны.

    Таблица истинности для конъюнкций:



    Дизъюнкцией (логическим сложением) двух высказываний  , называется высказывание (« или »), которое истинно, когда хотя бы одно из них истинно.

    Таблица истинности для дизъюнкций:



    10. Импликация и эквиваленция, таблицы их истинности.

    Импликацией двух высказываний  ,  называется высказывание  («если , то », « влечёт », «из следует », « имплицирует »), которое ложно тогда и только тогда, когда истинно, а ложно.

    Таблица истинности для импликаций:



     Эквивалентностью высказываний  , называется высказывание (« эквивалентно », « тогда и только тогда, когда », «для того, чтобы , необходимо и достаточно, чтобы »), которое истинно тогда и только тогда, когда  и  оба истинны или ложны.

    Таблица истинности для эквивалентности:


    11. Эквивалентные высказывания. Теорема о свойствах логических эквивалентностей.

    Эквиваленцией (или эквивалентностью) двух высказываний Х, У называется новое высказывание, которое считается истинным, когда оба высказывания Х, У, либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

    Эквиваленция высказываний Х, У обозначается символом  (или,

    ), читается «Х эквивалентно У» или « для того, чтобы Х, необходимо и достаточно, чтобы У», или «Х тогда и только тогда, когда У».
    12. Тавтологии и противоречия, их свойства.

    Формула называется тавтологией, если при любой интепретации она истинна; или противоречием, если при любой интепретации - ложна.

    Теорема 3.1. Следующие формулы алгебры высказываний являются тавтологиями:
    а) закон исключенного третьего;
    б) закон отрицания противоречия;
    в) закон двойного отрицания;
    г) закон тождества;
    д) закон контрапозиции;
    е) закон силлогизма (правило цепного заключения);
    ж) закон противоположности;
    з) правило добавления антецедента ("истина из чего угодно");
    и) правило "из ложного что угодно";
    к) правило "модус поненс" (лат. modusponens);
    л) правило "модус толленс" (лат. modustollens);
    м) правило перестановки посылок;
    н) правило объединения (и разъединения) посылок;
    о) правило разбора случаев;
    п) правило приведения к абсурду.

    Доказательство. Отметим, что непосредственно из определений логических операций вытекает тождественная истинность формул а), б), в), г); для формулы д) доказательство имеется. Установим тождественную истинность формул л) и н) (для остальных проверьте самостоятельно).

    Противоречие, как уже отмечалось, является одним из четырёх основных законов логики.

    Причём, из определения закона видно, что в данном формально логическом законе имеется в виду не всякое противоречие. а только один из видов противоречия. а именно, противоречие формально-логическое. У логического противоречия нет точного прототипа в природе и обществе. Поэтому возникающее противоречие в процессе исследования на тавтологию рассматриваемых в сравнении формул.
    13. Умозаключения и правила вывода, доказательство от противного.

    Умозаключения, как и понятия и суждения, являются формой аб­страктного мышления. С помощью многообразных видов умозак­лючений опосредованно (т. е. не обращаясь к органам чувств) мы можем получать новые знания. Умозаключать можно при наличии одного или нескольких суждений (называемых посылками), постав­ленных во взаимную связь. Возьмем пример умозаключения:

    Все углероды горючи.

    Алмаз - углерод.

    Алмаз горюч.

    Умозаключение - форма мышления, в которой из одного или нескольких суждений на основании определенных правил выво­да получается новое суждение, с необходимостью или опреде­ленной степенью вероятности следующее из них.

    Умозаключения делятся на такие виды: дедуктивные, индук­тивные, по аналогии. Умозаключения могут быть логически не­обходимыми, т. е. давать истинное заключение, и вероятностными (правдоподобными), т. е. давать не истинное заключение, а лишь с определенной степенью вероятности следующее из данных посы­лок (при этом в качестве посылок могут быть и ложные суждения).

    Схема умозаключения «от противного» такова:«Если из А следует В, то из не В следует не А».Другими словами, если верно АВ, то верно  , и наоборот. Такое умозаключение лежит в основе рассуждения от противного и в математике. Если АВ назватьпрямой теоремой,то ВА называетсяобратной теоремой,а  называетсяпротивоположной к обратной теореме.

    Покажем справедливость  , при условии справедливости АВ. Нам нужно доказать, что еслиистинно, то истинно. Другими словами, если В ложно, то А ложно. Но это очевидно, так как истинность А влечет за собой истинностьВ.
      1   2   3   4   5   6


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