Лабораторная работа №12

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

Лабораторная работа №12 Тема: Логические операции

Цель: ознакомиться с основными понятиями законами и операциями алгебры логики. Получить практические навыки по работе и применению битовых операций.

Лабораторная работа направлена на освоение следующих компетенций:

ОК-9 - способность к логически-правильному мышлению, обобщению, анализу, критическому осмыслению информации, систематизации, прогнозированию, постановке исследовательских задач и выбору путей их решения на основании принципов научного познания

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

ПК-2 способность применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач

I.Теоретическая часть

1.1. Алгебра логики

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

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B, ¬ , , , 0, 1},

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

где B — непустое множество, над элементами которого определены три операции:

отрицание (унарная операция) – это отрицание в логике — унарная операция над суждениями, результатом которой является суждение (в известном смысле) «противоположное» исходному. Обозначается знаком ¬ перед или чертой над суждением. Синоним: логическое "НЕ";

конъюнкция (бинарная) - логическая операция, по своему применению максимально приближённая к союзу "и". Синонимы: логическое "И", логическое умножение, иногда просто "И". Обозначается символом ;

дизъюнкция (бинарная) - (лат. disjunctio - разобщение) логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логическое «ИЛИ», включающее «ИЛИ», логическое сложение, иногда просто «ИЛИ». Обозначается символом ;

константы — логический ноль 0 и логическая единица 1.

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

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество B, состоящее всего из двух элементов: B = {Ложь, Истина}

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

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

эквивалентность («тогда и только тогда, когда»);

импликация («следовательно»);

сложение по модулю два («исключающее или»);

штрих Шеффера │;

стрелка Пирса и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция приобретает смысл вычитания из единицы; — немодульного сложения; & — умножения; — равенства; — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); — непревосходства суммы над 1 (то есть A B = (A + B) <= 1).

1.1.2. Свойства логических операций

Для логических высказываний справедливы следующие свойства и законы.

1.Идемпотентность

2.Коммутативность

3.Ассоциативность

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

4.Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:

5.Законы де Моргана

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

1.2. Битовые операции

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

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

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

1.2.1. Побитовое отрицание (NOT)

Побитовое отрицание (или побитовое НЕ, или дополнение) — это унарная операция, действие которой эквивалентно применению логического отрицания к каждому биту двоичного представления операнда. Другими словами, на той позиции, где в двоичном представлении операнда был 0, в результате будет 1, и, наоборот, где была 1, там будет 0 (см. таблицу 1).

Таблица 1 - Побитовое отрицание

НЕ

0 1

1 0

1.2.2. Побитовое И (AND)

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

Таблица 2 - Побитовое умножение (И)

1.2.3. Побитовое ИЛИ (OR)

Побитовое ИЛИ — это бинарная операция, действие которой эквивалентно применению логического ИЛИ к каждой паре битов, которые

Лабораторный практикум по «Информатике». Разработчик: Аткина В.С.

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

Таблица 3 - Побитовое сложение (ИЛИ)

1.2.4. Побитовое исключающее ИЛИ (XOR)

Побитовое исключающее ИЛИ (или побитовое сложение по модулю два) — это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если соответствующие биты операндов различны, то двоичный разряд результата равен 1; если же биты совпадают, то двоичный разряд результата равен 0.

Таблица 4 - Исключающее ИЛИ

В распространенных языках программирования встроенными средствами реализуются только четыре побитовые логические операции: И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных, и, более того, как следует из теории булевых функций, можно ограничиться еще меньшим набором базовых операций.