Сочетания с повторениями

Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле: Сочетания с повторениями - student2.ru .

Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из четырех по 7 по, их число: Сочетания с повторениями - student2.ru .

3. Логика высказываний

3.1. Введение

Алгебра логики (логика высказываний) – это раздел дискретной математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.

Алгебра логики возникла в середине 19 в. в трудах Дж. Буля и развивалась затем в работах Ч. Пирса, П. С. Порецкого, Б. Рассела, Д. Гильберта и др. Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами.

С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета алгебры логики, и дальнейшим развитием математической логики (последняя четверть 19 в. - 1-я половина 20 в.) предмет алгебры логики значительно изменился. Основным предметом алгебры логики стали высказывания.

3.2. Основные понятия

В формально-логических выводах используются истинные и ложные предложения.

Определение: повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно, называется высказыванием.

Примеры высказываний: "кит - животное", "все углы - прямые" и т. п. Первое из этих высказываний является, очевидно, истинным, а второе - ложным. Предложение "реши задачу", также как и "2+2", не является высказываем.

Определения математических понятий не являются высказываниями, т.к. это принятые соглашения.

Будем обозначать высказывания большими латинскими буквами: A, B, C,….

Элементарные, нерасчленяемые высказывания будем называть атомами.

3.3. Логические операции.

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

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

Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями.

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

Каждому высказывания можно сопоставить его истинностное значение, обозначаемое соответственно через И (если высказывание истинно), Л (если высказывание ложно).

Истинно­стное значение сложных высказываний зависит от истинностных значений высказываний, составлявших слоеное высказывание.

Эта зависимость устанавливается в данных ниже определениях я стращается в таблицах истинности.

Пусть A, В - произвольные высказывания, относительно кото­рых не предполагается, что известно их истинностные значе­ния.

Связке "НЕ" соответствует логическая операция отрицания, обозначение операции – знак ù или Сочетания с повторениями - student2.ru .

Определение. Отрицанием высказывания A называется высказывание Сочетания с повторениями - student2.ru (ùA), которое истинно, если A – ложно, и ложно, если A – истинно.

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

A Сочетания с повторениями - student2.ru
И Л
Л И

Пример: A: 2*2=4 – истинное высказывание; Сочетания с повторениями - student2.ru : Сочетания с повторениями - student2.ru или 2*2 Сочетания с повторениями - student2.ru 4 - ложное высказывание.

Связке "И" соответствует операция конъюнкция, обозначение операции – знак Сочетания с повторениями - student2.ru (или &).

Определение. Конъюнкцией высказываний A и B называется высказывание A Сочетания с повторениями - student2.ru B (читается "A и B"), которое истинно тогда и только тогда, когда A, B – истинно.

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

A B A Сочетания с повторениями - student2.ru B
И И И
И Л Л
Л И Л
Л Л Л

Пример: A: 5 – нечетное число; B: Пушкин родился в 1799 г – истинные высказывания; поэтому высказывание A Сочетания с повторениями - student2.ru B: 5 – нечетное число Сочетания с повторениями - student2.ru Пушкин родился в1799 г. – истинное высказывание.

Связке "ИЛИ" соответствует операция дизъюнкция, обозначение операции – знак Сочетания с повторениями - student2.ru .

В формально-логических выводах «или» употребляется не в исключающем смысле (в отличие от обыденной речи, где эта связка может употребляться и в исключающем смысле и в неисключающем смысле)

Определение. Дизъюнкцией высказываний A и B называется высказывание A Сочетания с повторениями - student2.ru B (читается "A или B"), которое ложно тогда и только тогда, когда A, B – ложны.

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

A B A Сочетания с повторениями - student2.ru B
И И И
И Л И
Л И И
Л Л Л

Пример. A: 7<10, и.в. В: 3 - число четное, л.в. A Сочетания с повторениями - student2.ru B: 7<10 Сочетания с повторениями - student2.ru 3 - число четное, и.в.

Связке "ЕСЛИ....ТО" соответствует логическая операция импликация, обозначение операции знак →.

Определение. Импликацией высказываний A и B называется высказывание A→B (читается "если A, то B"), которое ложно тогда и только тогда, когда A – истинно, а B – ложно.

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

A B A→B
И И И
И Л Л
Л И И
Л Л И

Пример. A: 2*2=5, л. в. В: 2=2, и. в. A→B: 2*2=5→ 2=2. и. в.

Высказывание A называется условием или посылкой, высказывание В - заключением или следствием импликации.

Связке "ТОГДА И ТОЛЬКО ТОГДА, КОГДА" соответствует операция эквиваленция, обозначение операция – знак «.

Определение. Эквиваленцией высказываний A и В навивается высказывание, обозначаемое A«B (читается :"A тогда и только тогда, когда В" или короче: "A эквивалентно В"), которое считается истинным только тогда, когда оба высказывания A и В имеют одинаковое истинностное значение.

Эквивалентность А«В читается также следующим образом: "Для того, чтобы A, необходимо и достаточно, чтобы В".

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

A B A«B
И И И
И Л Л
Л И Л
Л Л И

Пример. A: 7 – число простое; и.в. В: в равнобедренном треугольнике при основании углы равны, и.в. A«В - и.в.

3.4. Составные высказывания

С помощью рассмотренных в предыдущем пункте логических операций из заданной совокупности атомов (элементарных высказываний) можно строить различимо составные высказывания. Порядок выполнения действий указывается скобками.

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

Пример. Сочетания с повторениями - student2.ru .

A B C Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru
И И И И Л И
И И Л И Л Л
И Л И Л И И
И Л Л Л И И
Л И И Л И И
Л И Л Л И И
Л Л И Л И И
Л Л Л Л И И

3.5. Формулы логики высказываний

Основная задача логики высказываний состоит в изучении логических форм составных высказываний с помощью логичес­ких операций.

Понятие логической формы составного высказывания уточня­ется с помощью вводимого понятия формулы логики высказываний.

Понятие формул логики высказываний определяется следующим образом:

1. Элементарные формулы – атомы – являются формулами логики высказываний.

2. Если A, B – формулы, то Сочетания с повторениями - student2.ru , (A Сочетания с повторениями - student2.ru B), (A Сочетания с повторениями - student2.ru B), (A→B), (A«В) также являются формулами логики высказываний.

3. только те выражения являются формулами логики высказываний, для которых это следует из 1, 2.

Согласно определения, всякая формула либо атом, ли­бо образуется из атомов в результате применения 2.

Число скобок в формулах можно уменьшить, если опустить внешнюю пару скобок и упорядочить знаки логических опера­ций по старшинству: «, →, Сочетания с повторениями - student2.ru , Сочетания с повторениями - student2.ru , Сочетания с повторениями - student2.ru .

Знак « имеет самую большую область действия, знак Сочетания с повторениями - student2.ru самую маленькую.

Определение. Формулы логики, принимающие значение "истина" при любых значениях атомов, входящих в формулу, называется тождественно истинными (или законами логики, или тавтологиями).

Например, формула Сочетания с повторениями - student2.ru всегда тождественно истинна.

Определение. Формулы логики, принимающие всегда ложное значение, называются тождественно ложными (или противоречиями).

Например, формула Сочетания с повторениями - student2.ru - противоречие.

Определение. Формулы алгебры логики, принимающие значение «ложь» хотя бы на одном наборе значений атомов, входящих в формулу называютсяопровержимыми.

Определение. Формулы алгебры логики, принимающие значение «истина» хотя бы на одном наборе значений атомов, входящих в формулу называютсявыполнимыми.

Определение. Формулы Р и Q называются равносильными, если их истинностные значения совпадают при любом выборе истинностных значений атомов, входящих в эти формулы.

Запись Р Сочетания с повторениями - student2.ru Q означает, что формулы Р и Q равносильны.

3.6. Законы логики (свойства логических операций)

Следующие формулы являются законами логики.

1. Сочетания с повторениями - student2.ru - закон двойного отрицания.

2. Сочетания с повторениями - student2.ru - закон коммутативности конъюнкции.

3. Сочетания с повторениями - student2.ru - закон коммутативности дизъюнкции.

4. Сочетания с повторениями - student2.ru - закон ассоциативности конъюнкции.

5. Сочетания с повторениями - student2.ru - закон ассоциативности дизъюнкции.

6. Сочетания с повторениями - student2.ru - закон дистрибутивности конъюнкции относительно дизъюнкции.

7. Сочетания с повторениями - student2.ru - закон дистрибутивности дизъюнкции относительно конъюнкции.

8. Сочетания с повторениями - student2.ru - закон отрицания дизъюнкции.

9. Сочетания с повторениями - student2.ru - закон отрицания конъюнкции.

10. Сочетания с повторениями - student2.ru - закон отрицания импликации.

11. Сочетания с повторениями - student2.ru - закон выражения эквивалентности через конъюнкцию и импликацию.

12. Сочетания с повторениями - student2.ru - закон контрапозиции.

13. Сочетания с повторениями - student2.ru - закон силлогизма.

Для доказательства любого из приведенных выше законов можно использовать следующие способы:

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

2. Построить значение всей формулы и убедится, что формула является тавтологией.

A B A®B Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru
И И И Л Л Л
И Л Л И И Л
Л И И Л И И
Л Л И И И И

Пример. Докажем закон отрицания конъюнкции ( Сочетания с повторениями - student2.ru ) этими способами:

1. Найдем значения для Сочетания с повторениями - student2.ru и Сочетания с повторениями - student2.ru и сравним их.

A B Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru
И И И Л Л Л Л
И Л Л И Л И И
Л И Л И И Л И
Л Л Л И И И И

2. Найдем значение Сочетания с повторениями - student2.ru и убедимся, что при всех значениях A и B - это истинное значение.

A B Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru Сочетания с повторениями - student2.ru
И И И Л Л Л Л И
И Л Л И Л И И И
Л И Л И И Л И И
Л Л Л И И И И И

Заключение

В XXI веке дискретная математика является бурно развивающейся ветвью математики. Ее роль и место определяются в основном тремя факторами:

1) дискретную математику можно рассматривать как теоретические основы компьютерной математики

2) модели и методы дискретной математики являются хорошим сред­ством и языком для построения и анализа моделей в различных науках, включая химию, биологию, генетику, физику, психологию, экологию, со­циологию и др.

3) язык дискретной математики чрезвычайно удобен и стал фактиче­ски метаязыком всей современной математики.

В настоящее время знание дискретной математики необхо­димо специалистам в различных областях деятельности и элементы дискретной математики все чаще вводят в программы подготовки не только математиков, инженеров, программистов, но даже юристов. Ин­терес к этой дисциплине не случаен, т.к. потребность в зна­ниях этой области математики объясняется широким кругом ее применения: электроника и информатика, вопросы оптимизации и принятия решений. XXI в. называют веком информатизации, когда основной объем информации хранится в памяти ЭВМ. Применение ЭВМ для комплексной автома­тизации информационной деятельности принципиально измени­ло характер взаимоотношений человека и машины. Если раньше компьютер осваивали только те, кто непосредственно его обслу­живал: программисты, электронщики, операторы, то в XXI в. без машинной обработки информации не обойдется ни одна отрасль деятельности.


Список использованной литературы

1. Курс «Дискретная математика» http://any-book.org/download/11058.html

2. Мельников О.И. Обучение дискретной математике. – М. : Издательство ЛКИ, 2008. – 224с.

3. Фирсова Е. В. История развития дискретной математики и ее роль в обучении информатиков - экономистов [Текст] / Е. В. Фирсова // Молодой ученый. — 2012. — №2. — С. 304-311.

Наши рекомендации