5. Высказывания. Эквиваленция высказываний. Таблица истинности эквиваленции.

Высказывание – это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.

Эквиваленция (равносильность)

[<=>,<-> ,~,=, ≡]

A	B	A <-> B
0	0	1
0	1	0
1	0	0
1	1	1

Эквиваленцией двух высказываний (А и В) называется такое высказывание, которое истинно только тогда, когда истина и ложь совпадает.

^{(1 то же самое, что 2)} 

6. Высказывания. Отрицание высказываний. Таблица истинности высказывания.

Высказывание – это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.

Инверсия (отрицание)

[ , ¬А, not A]

Инверсией высказывания (А) называется такое высказывание, которое примет значение истины, а за тем ложи.

А
0	1
1	0

^{("1" тогда и только тогда, когда на входе «0»,)}

^{("0" тогда и только тогда, когда на входе «1»)}

7) Тождественно-истинные

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

Законы де Моргана:

1) ;

2) ;

Закон контрапозиции:

;

Законы поглощения:

1) ;

2) ;

Законы дистрибутивности:

1) ;

2) .

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

Равносильные формулы - две формулы А и В принимающие одинаковые значения, при одинаковых наборах значений входящих в них переменных.

Равносильность двух формул алгебры логики обозначается символом .

9. 9.Булева функция (Что-то непонятное %)) Булева функция- y=F(x₁,x₂,x₃…x_n), все переменные которой являются Булевыми.

Булевы переменные- переменные, которые могут принимать только два значения: 0 и 1.

Унарные функции.

При n = 1 число булевых функций равно 2²¹ = 2² = 4. Определение этих функций содержится в следующей таблице.

Таблица значений и названий булевых функций от одной переменной:

x0=x	1	0	Обозначение	Название
0	0	0	F1,0 = 0	тождественный ноль
1	0	1	F1,1 = x = ¬x = x' = NOT(x)	отрицание, логическое "НЕТ", "НЕ", "НИ", инвертор, SWAP (обмен)
2	1	0	F1,2 = x	тождественная функция, логическое "ДА", повторитель
3	1	1	F1,3 = 1	тождественная единица, тавтология

Бинарные функции

При n = 2 число булевых функций равно 2²² = 2⁴ = 16.

Таблица значений и названий булевых функций от двух переменных:

x1=x	1	1	0	0
x0=y	1	0	1	0	Обозначение	Название
0	0	0	0	0	F2,0 = 0	тождественный ноль, детектор 0
1	0	0	0	1	F2,1 = x ↓ y = x NOR y = NOR(x,y) = x НЕ-ИЛИ y = НЕ-ИЛИ(x,y)	стрелка Пи́рса, НЕ-ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, детектор 1
2	0	0	1	0	F2,2 = x ← y = x < y = x LT y = LT(x,y)	инверсия обратной импликации, меньше, детектор 2
3	0	0	1	1	F2,3 = x = x' = ¬x = NOT1(x,y) = НЕ1(x,y)	отрицание (негация, инверсия) первого операнда
4	0	1	0	0	F2,4 = x → y = x > y = x GT y = GT(x,y)	инверсия прямой импликации, больше, детектор 4
5	0	1	0	1	F2,5 = y = y' = ¬y = NOT2(x,y) = НЕ2(x,y)	отрицание (негация, инверсия) второго операнда
6	0	1	1	0	F2,6 = x ⊕ y = x XOR y = XOR(x,y) = x >< y = x <> y = x NE y = NE(x,y)	сложение по модулю 2, исключающее «или», сумма Жегалкина[5], не равно
7	0	1	1	1	F2,7 = x | y = x NAND y = NAND(x,y) = x НЕ-И y = НЕ-И(x,y)	штрих Ше́ффера, НЕ-И, 2И-НЕ, антиконъюнкция, пунктир Чулкова
8	1	0	0	0	F2,8 = x ∧ y = x · y = xy = x & y = x AND y = AND(x,y) = x И y = И(x,y) = min(x,y)	конъюнкция, 2И, минимум, детектор 8
9	1	0	0	1	F2,9 = (x ≡ y) = x ~ y = x ↔ y = x EQV y = EQV(x,y)	эквивалентность, равенство
10	1	0	1	0	F2,10 = YES2(x,y) = ДА2(x,y) = y	второй операнд
11	1	0	1	1	F2,11 = x → y = x ⊃ y = x ≤ y = x LE y = LE(x,y)	прямая (материальная) импликация (от первого аргумента ко второму), меньше или равно
12	1	1	0	0	F2,12 = YES1(x,y) = ДА1(x,y) = x	первый операнд
13	1	1	0	1	F2,13 = x ← y = x ⊂ y = x ≥ y = x GE y = GE(x,y)	обратная импликация (от второго аргумента к первому), больше или равно
14	1	1	1	0	F2,14 = x ∨ y = x + y = x OR y = OR(x,y) = x ИЛИ y = ИЛИ(x,y) = max(x,y)	дизъюнкция, 2ИЛИ, максимум
15	1	1	1	1	F2,15 = 1	тождественная единица, тавтология

16. Способы задания множеств.

1. Перечислением элементов.

Пример: А={Вася, Маша, Коля}

2. Задание множества с помощью характеристического предиката.

А={x|P(x)} – означает, что множество А состоит из таких элементов х которые обращают предикат P(x) в истинное высказывание.

Пример:

17.Сравнение множеств

21. Прямым или декартовым произведением множеств A и B, называется множество всех упорядоченных пар (a, b), где первый элемент a из множества A,  а второй элемент b из множества B.

ПРИМЕР

, 

Степенью множества называется декартовое произведение множества A само на себя n раз.

ПРИМЕР

,  .

23.Виды бинарных отношений на множестве A

1)          Обратное отношение   .

2)          Дополнение                  .

3)          Тождественные              .

4)     Универсальные               .

24.Свойства бинарного отношения на множестве( Опять непонятно что)

Определение 2. Говорят, что бинарное отношение   на множестве   обладает свойством рефлексивности²⁾, если   для всех  .

Определение 3. Говорят, что бинарное отношение   на множестве   обладает свойством антирефлексивности³⁾, если   для всех  .

Определение 4. Говорят, что бинарное отношение   на множестве   обладает свойством симметричности⁴⁾, если   влечет за собой   для всех  .

Определение 5. Говорят, что бинарное отношение   на множестве   обладает свойством антисимметричности⁵⁾, если  ,  , влечет за собой   для всех  .

Определение 6. Говорят, что бинарное отношение   на множестве   обладает свойством транзитивности⁶⁾, если   и   влечет за собой   для всех  .

Определение 7. Говорят, что бинарное отношение   на множестве   обладает свойством связанности⁷⁾, если   или   для всех .

Пример 5. Отношение делимости целых чисел из примера 2 является

• рефлексивным: любое целое число   делится на себя, то есть  ;

• транзитивным: если   делится на  , а   делится на  , то   делится на  .

Пример 6. Отношение порядка   из примера 3 обладает свойствами

• рефлексивности;

• транзитивности;

• антисимметричности;

• связанности.

Пример 2. На множестве целых чисел   отношение делимости, состоящее из упорядоченных пар  , в которых   делится на  , является бинарным отношением. В этом случае обозначение   заменяется на  .

Пример 3. На множестве действительных чисел   упорядочение   является бинарным отношением на  , состоящим из всех точек плоскости  , лежащих не ниже прямой  .