Билет 10. Сочетания с повторениями. Примеры

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

Теорема: число сочетаний с повторениями может быть вычислено по формулам:

.

11.

Понятие высказывание. Основные логические операции.

Высказывание – это одно из неопределяемых понятий математики, смысл которого был проиллюстрирован предыдущими нестрогими рассуждениями. Ещё более сложно объяснить смысл понятий истина и ложь, которые в математике также являются неопределяемыми. По этой причине не существует строгого математического алгоритма приписывания произвольным предложениям значений истина и ложь. На интуитивном уровне этот “алгоритм” можно описать так:

(1): уяснить смысл высказывания,

(2): убедиться, что объекты и их отношения, о которых идёт речь, можно

сравнить с действительностью,

(3): если установленные в высказывании отношения между объектами согласуются с действительностью, то высказывание считается “истинным”, в противном случае – “ложным”.

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

2) Логические операции - мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий

12.

Логические функции. Таблицы истинности. Эквивалентность формул логики высказываний.

Логическая функция - это функция, которая устанавливает соответствие между одним или несколькими высказываниями, которые называются аргументами функции, и высказыванием которое называется значением функции.

Это определение почти не отличается от определения числовой функции. Разница лишь та, что аргументом и значением числовой функции являются числа, а аргументом логической функции - высказывания.

Как можно составить логическую функцию? Очень просто.

Приведем пример: Пусть дано высказывание А. Оно может быть либо истинно, либо ложно. Определим высказывание В следующим образом: пусть В истинно, когда А ложно, и ложно когда А истинно.

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

Функция, определённая таким образом, называется отрицанием и записывается так: ¬A . Читается так: не А.

2) Таблица истинности — это таблица, в которой отражены все значения логической функции при всех возможных значениях, входящих в неё логически Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (true либо false, 1 либо 0).

3) Эквивале́нция (или эквивале́нтность) — двуместная логическая операция. Обычно обозначается символом ≡ или ↔. Задаётся следующей таблицей истинности:

a	b	a↔b
0	0	1
0	1	0
1	0	0
1	1	1

Таким образом, высказывание A ≡ B означает «A то же самое, что B», «A эквивалентно B», «A тогда и только тогда, когда B». Не надо путать эквиваленцию — логическую операцию с эквивалентностью — бинарным отношением. Связь между ними следующая:

Логические выражения X и Y эквивалентны в том и только в том случае, когда эквиваленция X ↔ Y  истинна при всех значениях логических переменных.

13.

Основные законы алгебры высказываний.

Среди тождественно-истинных формул алгебры высказываний важную роль в математической логике и ее приложениях играют так называемые законы алгебры высказываний. Рассмотрим основные из них. 1. Закон исключения третьего. х , то есть для любого высказывания имеет место одно из двух, либо оно истинно, либо ложно, третье места не имеет. 2. Закон отрицания противоречия.  , то есть неверно, что одновременно имеет место некоторое высказывание и его отрицание. 3. Закон двойного отрицания.  , то есть отрицать отрицание некоторого высказывания это все равно, что утверждать это высказывание. 4. Закон тождества  , то есть всякое высказывание есть логическое следствие самого себя. 5. Закон контрапозиции  , то есть импликация двух высказываний эквивалентна обратной импликации их отрицаний. Данный закон позволяет устанавливать равносильность различных видов теорем. 6.Закон силлогизма  . Данный закон является правилом вывода, лежащим в основе большинства методов доказательств предложений. 7.Закон приведения к абсурду   . Данный закон является правилом вывода, лежащим в основе доказательства предложений методом от противного. Чтобы доказать, что каждый из этих законов является тождественно истиной формулой достаточно составить для нее сответствующую таблицу истинности, а в простых случаях воспользоваться определением соответствующей логической операции..

14.

Связь теории высказываний и теории множеств.

Существует тесная связь между множествами – с одной стороны, и высказываниями – с другой, а также между операциями над множествами, с одной стороны, и операциями образования составных высказываний- с другой.

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

Определение. Пусть Х,У,Z,… означает некоторые высказывания, и пусть U- их множества логических возможностей. Пусть А, В, С,…. означают подмножества U, для которых истинны соответственно множествами истинности высказываний X,Y, Z, …

Вывод.

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

Тео́рия мно́жеств — раздел математики, в котором изучаются общие свойства множеств — совокупностей элементов произвольной природы, обладающих каким-либо общим свойством