Комбінаторика

Р для будь-якої пари

  • (х, х) є А І.

  • якщо хру , то ух для будь - якого х, у є А, тобто якщо (х, у) є Р, то

    (у, х) Р для будь-якої пари (х, у) є А І.

    1. якщо хру і урz, то хрz для будь-яких х, у, z є А, тобто якщо (х, у) є Р і (у, z) є Р, то і (х, z) є Р для будь яких пар (х, у) (у, z) є А І.

    Так відношення р: „ х < у у множині А = {1, 2, 3, 4, 5} є відношенням строгого порядку, тому що воно антирефлексивне, антисиметричне, транзитивне.

    Відношення р називається відношенням нестрогого (часткового) порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

    Так, відношення „число х – дільник числа у” у множині А = {1, 2, 3, 4, 5} є відношенням часткового порядку, тому що воно транзитивне, рефлексивне і антисиметричне.

    У математиці та її застосуваннях особливу роль відіграють такі відношення порядку р, які дають можливість порівняти довільні різні елементи певної множини А. Ці відношення називаються відношеннями лінійного порядку у множині А.

    Відношення строгого (нестрогого) порядку називається відношенням лінійного строгого (нестрогого) порядку, якщо для будь-яких різних елементів х і у із А здійснюється одне із відношень хру або урх.

    Проілюструємо сказане на прикладі. Нехай А – множина студентів групи. Р – відношення „студент х вищий за студента у”. Це відношення антирефлексивне, антисиметричне і транзитивне.

    Значить, воно відношення строгого порядку. Якщо в даній множині А немає студентів однакового росту, то тоді про будь-яких двох студентів можна сказати, що або студент х вищий за у або студент у вищий студента х. Отже, відношення Р є відношенням строгого лінійного порядку.

    Множина А називається лінійною упорядкованою, якщо в А введено відношення Р і для будь-якої пари (х, у) є А І, якщо х ≠ у, то хру або

    урх.

    Так, множина натуральних чисел лінійно упорядкована відношенням строгого порядку „менше”, тобто N = {1, 2, 3, 4, ....}

    Розділ 3. СИМВОЛІКА МАТЕМАТИЧНОЇ ЛОГІКИ


    § 3. 1. Поняття висловлення

    Під математичною логікою або символічною логікою розуміють логіку, що розвивається за допомогою математичних методів. Математичний апарат до логіки вперше застосував у XIX ст. англійський математик Джордж Буль.

    Д. Буль (1815 – 1864 р.р.), батько відомої англійської письменниці Войнич (її чоловік був революціонером), автора роману „Овод”. Темп розвитку математичної логіки різко зростає у XIX ст. У 90-х роках ХХ ст.. математична логіка дістає широке застосування в технічних науках, наприклад, електротехніці. Зараз вона є складовою частиною теоретичного фундаменту кібернетики.

    Основним поняттям математичної логіки є висловлювання. Висловлювання належить до первинних понять, воно не визначеється через інші поняття, а вводяться за допомогою опису.

    Під висловлюванням розуміють будь-яке твердження, відносно якого можна з’ясувати, істинне воно чи хибне. Наприклад,

    1. Діагональ квадрата не сумірна з його стороною – „і” висловлювання

    2. 5 > 8 – „х” висловлення

    3. О котрій годині ти повернешся вчора додому? – не є висловленням.

    Висловлення позначаються малими латинськими буквами: p, q, r, s, ......

    Множину усіх висловлювань, яку позначимо буквою S, ділять на дві підмножини (класи)

    Т – клас усіх істинних висловлювань

    F – клас усіх хибних висловлювань

    Два висловлювання p і q називаються рівносильними (логічно рівними), якщо вони належать до одного й того самого класу і записують

    p q

    Із означення рівносильності висловлювань виникають властивості:

    1. р р

    2. Якщо р q, то q р – симетричність

    3. Якщо р q і q r,то р r – транзитивність

    § 3. 2. Операції над висловленнями

    У розмовній мові для сполучення двох речень вживають слова: і, або, якщо ...... то, тоді і тільки тоді, не. З’ясуємо те значення, в якому ці слова вживаються в логіці.

    а) Логічне множення (кон’юнкція)

    Логічним добутком (кон’юнкцією) двох висловлень p і q називається

    таке висловлення „p і q”, яке істинне тоді і тільки тоді, коли p і q одночасно істинні. Позначається: p q.

    Згідно з означенням маємо таку таблицю істинності для кон’юнкції.

    p

    q

    p q

    i i i
    i x x
    x i x
    x x x

    Приклад. Нехай висловлення р буде “5<8”, а висловлення q – “ 8 < 13 “, тоді кон’юнція цих висловлень буде “ I ”, бо істинне p i q .

    Переважно скорочено таку кон’юнкцію записують як подвійну нерівність 8 < 5 < 13

    Властивості кон’юнкції

    1) Комутативна (переставна властивість) p q q p

    p

    q

    p q

    q p

    і і і і
    і х х х
    х і х х
    х х

    х

    х


    2) Асоціативна (сполучна) властивість (p q) s p (q s)

    p

    q

    s

    (p q)

    (p q) s

    (q s)

    (q s) p

    і і і і і і і
    і х х х х х х
    х і х х х х х
    х х і х х х х
    х і і х х і х
    і х і х х х х
    і і х і х х х
    х х х х х х х


    Означення кон’юнкції двох висловлювань розповсюдна на будь-яке скінченне число висловлювань

    рі = р1р2р3р4…рn

    б) Логічне додавання (диз’юнкція)

    Диз’юнкцією або логічною сумою двох висловлень p і q називається висловлення “p і q „ яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлювань і хибне коли вони обидва хибні.

    Позначення диз’юнкції: p v q


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

    p

    q

    p v q

    i i i
    i x і
    x i і
    x x x

    Закони диз’юнкції


    1) Комутативний: p v q q v p

    p

    q

    p v q

    q v p

    і і і і
    і х і і
    х і і і
    х х

    х

    х


    2) Асоціативний закон диз’юнкції (p v q) v s p v (q v s)

    p

    q

    s

    p v q

    (p v q) v s

    q v s

    p v (q v s)

    і і і і і і і
    і х х і і х і
    х і х і і і і
    х х і х і і і
    х і і і і і і
    і х і і і і і
    і і і і і і і
    х х х х

    х

    х

    х


    3) Дистрибутивні закони, які пов’язують кон’юнкцію і диз’юнкцію

    (p v q) s (p s) v (q s)

    (p q) v s (p v s) (q v s)

    Довести дома самостійно.

    в) Заперечення висловлення

    Запереченням висловлення р називається висловлення „не р“, яке істинне, коли р хибне, і хибне коли р істинне.

    Позначення : .

    р

    і х
    х і

    Закони заперечення

    1) Заперечення заперечення висловлення рівносильне висловленню р:

    р

    2) Закон суперпозиції

    p х

    р

    p

    і х х
    х і х

    3) Закон включення третього

    q v i

    Кожне висловлення q або істинне або хибне, третього не може бути q v = i


    q

    q v

    і х i
    х і i

    4) Закони де Моргана

    v

    Заперечення кон’юнкції двох висловлень рівносильне диз’юнкції заперечень і заперечення диз’юнкції рівносильне кон’юнкції заперечень цих висловлень.

    v

    р

    q

    p q

    v

    і i i х x x x
    i x x і x i i
    x i x i i x i
    x x x

    x

    x x

    x


    г) Логічне слідування (імплікація)

    Слідуванням (імплікацією) двох висловлень p і q називається висловлення “якщо p, то q„, яке хибне тоді і тільки тоді, коли p – істинне, а q – хибне. Позначається імплікація: p q

    p

    q

    p q

    i i i
    i x x
    x i і
    x x i

    Операцію імплікації двох висловлень можна виразити через операцію заперечення і диз’юнкцію:

    p q v q

    p

    q

    p q

    v q

    i i i x і
    i x x x х
    x i і i і
    x x i i і



    д) Еквіваленція (рівносильність) двох висловлень

    Еквіваленцією (рівносильністю) двох висловлень p і q називається висловлення „р тоді, і тільки тоді, коли q, яке істинне тоді і тільки тоді, коли p і q одночасно істинні, або одночасно хибні“

    Позначається: p q , p q

    Еквіваленція

    (p q) (p q q p)

    p

    q

    p q

    p q

    q p

    p q q p

    i i і i і і
    i x х x і х
    x i х і х х
    x x і i i і



    § 3.3. Предикати

    (неозначуване висловлення або висловлювальна форма)

    Розглянемо речення

    1. х – парне число

    2. Поет х написав поему “ Сон”.

    Ці речення не є висловленням, бо неможна сказати чи вони “і” чи “х“. Якщо змінну в першому реченні замінити числом, а в другому прізвищем поета, то вони перетвореться у висловлення.

    Предикатом називається твердження, в яке входять вільні змінні і яке при заміні їх коректними значеннями стає висловленням.

    Це є одномісні предикати.

    Для кожного предиката треба, вказати множину значень, які може приймати змінна х. Цю множину називають областю визначення предиката і в першому прикладі область визначення – N, у другому - множина прізвищ поетів.

    Предикат позначають великими буквами:

    P(x), Q(x), R(x), S(x), де х Х.

    Множина тих значень змінних, при яких предикат набуває істиного значення називається областю істинності предиката і позначається Т. Область істиності є підмножиною області визначення Т Х.

    У першому прикладі Т = {x | x N i є парне}

    У другому прикладі Т = { Шевченко }

    Предикат в який входить дві змінні називаються двомісним. Приклади:

    1. x > y;

    2. “Поет х написа поему у “

    Двомісні предикати позначаються P(x, y), Q(x, y) які визначені на множенні Х Ч У.

    В математиці зустрічаються багато предикатів, причому деякі з них мають спеціальні позначення

    „х = у“; „х < у“; „х ║ у“; „х у“ і т.д.

    В математиці зустрічається і трьох, чотирьох і т.д. місні предикати. Приклади:

    1. Число х ділиться на число у і на число z.

    2. Всі числа, які діляться на х і у, діляться і на z.

    3. Сума чисел х і у дорівнює добутку чисел U і V.

    4. а1х1 + а2х2 + а3х3 + … + аnxn = b n–місний предикат

    Нехай Q (a, b) – двомісний предикат.

    (a - b)І = аІ – 2ab + bІ. Цей предикат перетворюється на істинне висловлення при всіх дійсних значеннях „a” і „b”. Областю істинності предиката Q є множина всіх дійсних чисел R. Такий предикат називається тотожно істинним.

    Рівності, рівняння, нерівності та їх системи, що розглядаються в математиці, з точки зору логіки – предикати.


    § 3. 4. Квантори.

    У математиці часто використовують вирази „для всіх”, „для кожного”, „яке б не було”, „існує”, „знайдеться хоча б одне”.

    Для позначення цих виразів вживаються символи, які називаються кванторами: квантор загальності , який позначається , у звичайній мові йому відповідає вираз „для кожного”, „для всякого”, „для всіх”.

    Нехай Р(х) – „Трикутник х прямокутний», то вираз (х є Х) Р(х) читається:

    1. Будь-який трикутник прямокутний

    2. Кожний трикутник прямокутний

    3. Всі трикутники прямокутні

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

    Розглянемо ще квантор існування, який позначається . У звичайній мові йому відповідає вираз: „існує”, „знайдеться хоча б одне”.

    Нехай Р(х): „х > 5”

    Вираз ( х є R) (х > 5) читається:

    1. Існує дійсне число х таке, що х > 5

    2. знайдеться таке дійсне число х, яке > 5

    3. хоча б одне дійсне число > 5

    В результаті квантифікація, навішування квантора на змінну предикат перетворився у висловлення.

    Над предметами, так само, як і над множинами можна проводити операції кон’юнкцію, диз’юнкцію, заперечення, імплікацію і еквіваленцію.


    § 3. 5. Поняття про теореми.

    Які б ми розділи математики не розглядали скрізь ми зустрічаємось з твердженнями, які називаємо теоремою.

    Теорема – це математичне твердження, істинність якого з’ясовується доведенням (міркуванням).

    Формулювання будь-якої теореми складається з двох частин: умови і

    Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
    Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

    Поможем написать работу на аналогичную тему

    Получить выполненную работу или консультацию специалиста по вашему учебному проекту
    Нужна помощь в написании работы?
    Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
  • Похожие рефераты: