Свойства бинарных отношений.

1. = , .

2. , .

3. = .

4. = .

5. = .

 

 

4.Отображения множеств. Виды отображений. Понятие функции.

Пусть А и В – произвольные множества. Отображением множества А в множество В называют правило (соответствие), которое каждому элементу множества А ставит в соответствие единственный для этого элемента элемент множества В.

Отображение называется инъекцией, если для любых элементов x₁, x₂ Î X, для которых f(x₁) = f(x₂) следует, что x₁ = x₂.

Сюръекцией (или отображением "на" ) называется отображение, при котором f(X) = Y

Биекция – это одновременно и сюръекция и инъекция.

Функция (отображение, оператор, преобразование) — математическое понятие, отражающее связь между элементами множеств.

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

 

5.Понятие подстановки. Операции над подстановками.

подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.

 

6.Элементы комбинаторики. Схемы выбора. Бином Ньютона.

Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.

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

Сочетанием без повторений из элементов по называется неупорядоченное -элементное подмножество -элементного множества. Число сочетаний без повторений из элементов по равно

 

Размещением без повторений из элементов по называется упорядоченное -элементное подмножество -элементного множества.

Схема без повторений. Упорядоченные множества состоящие из n различных элементов называются перестановками. Pn=n!

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

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

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

, где — биномиальные коэффициенты, — неотрицательное целое число.

 

7.Понятие высказывания. Простые и составные высказывания.

Высказыванием называется повествовательное предложение о котором в данной ситуации можно сказать истинно оно или ложно. Высказывания в логике обозначаются лат. Буквами – Х, У, Z,…

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

Истинность составного высказывания определяется значениями истинности его компонентов.

8.Основные логические операции. Таблицы истинности.

В алгебре логики основными операциями являются отрицание, логическое сложение (дизъюнкция), логическое умножение (конъюнкция), импликация, эквивалентность.

Отрицание. Отрицанием высказывания Х называется высказывание которое истинно, когда Х ложно и наоборот:

x

Коньюнкцией двух высказываний Х и У называется высказывание Х / У которое истинно только в том случае, когда и Х и У оба истинны:

x 1	x 2	x 1 x 2

Дизъюнкцией двух высказываний Х и У называется высказыванием Х / У, которое истинно в том случае, когда хотя бы одно высказывание истинно:

x 1	x 2	x 1 x 2

Импликацией Х и У называется высказывание Х У, которое ложно тогда и только тогда, когда Х – истинно , У – ложно:

x 1	x 2	x 1 x 2

Эквивалентностью Х и У называется высказывание Х У, которое истинно когда оба высказывания либо истинны либо ложны:

x 1	x 2	x 1 x 2

Таблица истинности — это таблица, описывающая логическую функцию.

9.Дополнительные логические связки. Построение таблиц истинности составных высказываний.

1.Сложение по модулю 2 (Антиэквивалентность)

2. Штрих Шеффера (Антиконьюнкция)

3. Стрелка Пирса (Антидизьюнкция)

При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий:

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

Во-вторых, необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций. В нашем случае количество переменных равно двум, а количество логических операций — пяти, то есть количество столбцов таблицы истинности равно семи.

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

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

 

 

10.Формулы логики. Виды формул.

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

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