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

А ﬤ В; читается: ≪ если А, то В ≫. Это такое сложное высказывание, которое ложно только в том случае, когда А истинно, а В ложно.

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

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

1) А = А означает, что не А истинно, если А ложно;

2) А ˄ В = В ˄ А означает, что (А и В = В и А);

3) (А ˄ В) ˄ С = А ˄ (В ˄ С) означает, что ((А и В) и С) =

= (А и (В и С)) или, иначе, это закон логического умножения ((А - В) -С) = (А • (В • С));

4)A v B = B v A означает, что А + В = В + А — известный из курса арифметики закон: ≪ от перемены мест слагаемых сумма не меняется ≫;

5) (A v В) v С = A v (В v С) или (А + В) + С = А + (В + С);

6) А ˄ (В v С) = (А ˄ В) v (А ˄ С) означает, что левая часть выражения истинна при истинности правой части;

7) A v (В ˄ С) = (A v В) ˄ (A v С);   

8 (Ā˅ =

9) ( ˄ )=

10) А ˄А = А;

11) A v А = А;

12) А ˄ 1 = А;

13) A v 0 = А.

Проверка справедливости указанных соотношений может быть произведена на основании определений и таблиц логических опе­раций — конъюнкции, дизъюнкции и отрицания. Соотношения 1 — 13 используются для преобразования сложных логических выраже­ний к более простому виду. Соотношения 2—5 показывают, что для операций конъюнкции и дизъюнкции справедливы переместительный и сочетательный законы, в силу чего многочленные конъ­юнкции и дизъюнкции можно записывать без скобок. Например, вместо [(А ˄ В) ˄ С] ˄D можно записать А ˄В ˄ С ˄ D.

Выражения вида А ˄В ˄ С ˄ D... часто называются произведением, а его члены — множителями.

Выражения вида Av Вv С v... называют суммой, а его члены — слагаемыми.

Соотношение 6 показывает, что в алгебре логики спра­ведлив закон распределительности конъюнкции относительно дизъюнкции.

Соотношение 7 показывает, что в алгебре логики имеет место еще закон распределительности дизъюнкции относительно конъюнкции

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

Соотношения 8 и 9 называются законами де Моргана и вместе с соотношением 1 позволяют преобразовывать логические выра­жения к виду, в котором знаки отрицания относятся только к простым высказываниям.

Законы Моргана – логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана.

Отрицание конъюнкции есть ни что иное как дизъюнкция отрицания.

Отрицание дизъюнкции есть не что иное как конъюнкция отрицания.

 

       Помимо соотношений 1 — 13 весьма полезными для преобразования логических выражений являются следующие равносильные соотношения:

Диаграммы Венна

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

    Конъюнкция двух высказываний будет представляться пересечением двух множеств (рис. 1.4, б). Действительно, А ˄ В = 1 только тогда, когда А = 1 и В = 1, а это имеет место лишь для точек, одновременно принадлежащих множеству А и множеству В (их пересечению).

    Дизъюнкция двух высказываний A v В будет изображаться множеством, которое получается путем объединения множеств А и В (рис. 1.4, в).

    Эквивалентность двух высказываний А ≡ В изобразится так, как показано на рис. 1.4, г, так как истинность А  В равна 1 либо при А = 1 и В = 1, либо при А = 0 и В = 0.

    Отрицание эквивалентности А ≡ В, показанное на рис. 1.4, д, получается, если учесть, что А ≡ В равно А≡ В.

       Отрицание конъюнкции обозначается: А / В и называется операцией Шеффера (см. рис.1.4,е).

    Отрицание дизъюнкции , выраженное штрихом Шеффера, имеет смысл Ā= А / В

    Операция Шеффера играет важную роль в теории проектирования логических схем процессоров ЭВМ, поскольку электронные схемы, реализующие операцию Шеффера, являются универсальными функциональными элементами, при помощи которых может построено любое функциональное устройство.

 

Действия в реляционных БД базируются на операциях реляционной алгебры.

1. Ограничение (выборка) - создание новой таблицы путём отбора строк исходной таблицы, которые удовлетворяют условию ограничения.

2. Проекция - создание новой таблицы путём отбора определённых столбцов исходной таблицы.

3. Объединение - создание новой таблицы, содержащей все строки исходных таблиц, которые должны иметь одинаковые столбцы.

4. Пересечение -- создание новой таблицы, содержащей строки общие для исходных таблиц. При этом исходные таблицы должны иметь одинаковые столбцы

5. Разность -- создание новой таблицы, содержащей строки 1-ой таблицы, отсутствующие во 2-ой таблице. При этом и первая и вторая таблицы должны иметь одинаковые столбцы.

6. Произведение – создание новой таблицы, в которой имеются все столбцы 1-ой и 2-ой таблицы, а строки получены попарным сцеплением строк их таблиц. Число строк новой таблицы равно произведению количества строк исходных таблиц. 

 

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

 

Пример. По двум таблицам найти произведение

 

                    ПОСТАВЩИК                                ПОТРЕБИТЕЛЬ

Поставщик

Поставщик 1

Поставщик 2

 

Потребитель

Потребитель 1

Потребитель 2

                                   

Результат операции произведения

Поставщик	Потребитель
Поставщик 1	Потребитель 1
Поставщик 1	Потребитель 1
Поставщик 2	Потребитель 2
Поставщик 2	Потребитель 2

 

7. Деление – создание новой таблицы, содержащей столбцы 1-ой таблицы, отсутствующие во 2-ой таблице, и строки 1-ой таблицы, которые совпали со строками 2-ой таблицы. Для выполнения этой операции вторая таблица должна содержать лишь столбцы, совпадающие со столбцами первой таблицы.

 

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

Исходная таблица:(ФИО, Дата рождения, Шифр группы, Признак наличия стипендии)

Результат (таблица): (ФИО, Дата рождения)

Создадим вспомогательную таблицу со столбцами (Шифр группы, Признак наличия стипендии). Заполним одну строку этой таблицы, поместив в неё шифр заданной группы и отметку о получении стипендии.

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

8. Соединение – создание новой таблицы, строки которой являются сцеплением строк исходных таблиц.

Различают два вида соединения таблиц: естественное и по условию.

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

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

 

Пример. Соединить таблицы СТУДЕНТ и ОЦЕНКА. 

Общий атрибут- Номер зачётной книжки.

 

СТУДЕНТ

ФИО	Дата рождения		Номер зачётной книжки
Иванов М.Т.	22.12.80		1234
Петров П.Л.	12.05.80		1235
Сидоров С.С.		30.09.80	1236

 

 

ОЦЕНКА

Код дисциплины	Номер зачётной книжки	Оценка
1	1234	4
1	1235	3
2	1234	4
2	1235	3

 

Результирующая таблица

ФИО	Дата рождения	Номер зачётной книжки	Код дисциплины	Номер зачётной книжки	Оценка
Иванов М.Т.	22.12.80	1234	1	1234	4
Иванов М.Т.	22.12.80	1234	2	1234	4
Петров П.Л.	12.05.80	1235	1	1235	3
Петров П.Л.	12.05.80	1235	2	1235	3
Сидоров С.С.	30.09.80	1236