Что значит запись a b в информатике

Порядок байтов

Поря́док ба́йтов — метод записи байтов многобайтовых чисел в информатике.

В общем случае, для представления числа M, большего 255 (здесь  — максимальное целое число, записываемое одним октетом), приходится использовать несколько байтов-октетов. При этом число M записывается в позиционной системе счисления по основанию 256:

, каждое из которых лежит в интервале от 0 до 255, является последовательностью байтов, составляющих M. При этом называется младшим байтом, а  — старшим байтом числа M.

Содержание

Варианты записи

Порядок от старшего к младшему

Порядок от старшего к младшему или (англ.  big-endian , дословно: «тупоконечный»): , запись начинается со старшего и заканчивается младшим. Этот порядок является стандартным для протоколов TCP/IP, он используется в заголовках пакетов данных и во многих протоколах более высокого уровня, разработанных для использования поверх TCP/IP. Поэтому, порядок байтов от старшего к младшему часто называют сетевым порядком байтов (англ.  network byte order ). Этот порядок байтов используется процессорами IBM 360/370/390, Motorola 68000, SPARC (отсюда третье название — порядок байтов Motorola, Motorola byte order).

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

Порядок байтов от старшего к младшему применяется во многих форматах файлов — например, PNG, FLV, EBML.

Порядок от младшего к старшему

Порядок от младшего к старшему или (англ.  little-endian , дословно: «остроконечный»), о происхождении термина ниже): , запись начинается с младшего и заканчивается старшим. Этот порядок записи принят в памяти персональных компьютеров с x86-процессорами, в связи с чем иногда его называют интеловский порядок байтов (по названию фирмы-создателя архитектуры x86). В некоторых кругах используется название англ.  VAX order , например, в документации Perl [1] .

В противоположность «тупоконечному» порядку, меньше [источник не указан 580 дней] кросс-платформенных протоколов и форматов данных с «остроконечным» порядком байт; заметные исключения: USB, конфигурация PCI, таблица разделов GUID, рекомендации FidoNet.

Переключаемый порядок

Многие процессоры могут работать и в порядке от младшего к старшему, и в обратном, например, ARM, PowerPC (но не PowerPC 970), DEC Alpha, MIPS, PA-RISC и IA-64. Обычно порядок байтов выбирается программно во время инициализации операционной системы, но может быть выбран и аппаратно перемычками на материнской плате. В этом случае правильнее говорить о порядке байтов операционной системы. Переключаемый порядок байтов иногда называют англ.  bi-endian .

Смешанный порядок

Смешанный порядок байтов (англ.  middle-endian) иногда используется при работе с числами, длина которых превышает машинное слово. Число представляется последовательностью машинных слов, которые записываются в формате, естественном для данной архитектуры, но сами слова следуют в обратном порядке.

Классический пример middle-endian — представление 4-байтных целых чисел на 16-битных процессорах семейства PDP-11 (известен как PDP-endian). Для представления двухбайтных значений (слов) использовался порядок little-endian, но 4-хбайтное двойное слово записывалось от старшего слова к младшему.

В процессорах VAX и ARM используется смешанное представление для длинных вещественных чисел.

Пример

Далее приведён пример, в котором описывается размещение 4-байтового числа в ОЗУ ЭВМ, доступ к которому может производиться как к 32-разрядному слову, так и побайтно.

Все числа записаны в 16-ричной системе счисления.

Сравнение

Существенным достоинством little-endian по сравнению с big-endian порядком записи считается возможность «неявной типизации» целых чисел при чтении меньшего объёма байт (при условии, что читаемое число помещается в диапазон). Так, если в ячейке памяти содержится число 0x00000022, то прочитав его как int16 (два байта) мы получим число 0x0022, прочитав один байт — число 0x22. Однако, это же может считаться и недостатком, потому что провоцирует ошибки потери данных.

Обратно, считается что у little-endian, по сравнению с big-endian есть «неочевидность» значения байтов памяти при отладке (последовательность байтов (A1, B2, C3, D4) на самом деле значит 0xD4C3B2A1, для big-endian эта последовательность (A1, B2, C3, D4) читалась бы «естественным» для арабской записи чисел образом: 0xA1B2C3D4). Наименее удобным в работе считается middle-endian формат записи; он сохранился только на старых платформах.

Для записи длинных чисел (чисел, длина которых существенно превышает разрядность машины) обычно предпочтительнее порядок слов в числе little-endian (поскольку арифметические операции над длинными числами производятся от младших разрядов к старшим). Порядок байтов в слове — обычный для данной архитектуры.

Проблемы совместимости

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

Определение порядка байтов

Порядок байтов в конкретной машине можно определить с помощью программы на языке Си (testendian.c):

Результаты запуска на big-endian машине (SPARC):

Результаты запуска на little-endian машине (x86):

Вещественные числа

Хранение вещественных чисел может зависеть от порядка байт; так, на x86 используются форматы IEEE 754 со знаком и порядком числа в старших байтах.

Юникод

Если Юникод записан в виде UTF-16 или UTF-32, то порядок байтов является существенным. Одним из способов обозначения порядка байтов в юникодовых текстах является постановка в начале специального символа BOM (byte order mark, U+FEFF) — «перевёрнутый» вариант этого символа (U+FFFE) не существует и не допускается в текстах.

Конвертация

Для преобразования между сетевым порядком байтов (англ.  network byte order ), который всегда big-endian, и порядком байтов, использующимся на машине (англ.  host byte order ), стандарт POSIX предусматривает функции htonl() , htons() , ntohl() , ntohs() :

• uint32_t htonl(uint32_t hostlong);  — конвертирует 32-битную беззнаковую величину из локального порядка байтов в сетевой;
• uint16_t htons(uint16_t hostshort);  — конвертирует 16-битную беззнаковую величину из локального порядка байтов в сетевой;
• uint32_t ntohl(uint32_t netlong);  — конвертирует 32-битную беззнаковую величину из сетевого порядка байтов в локальный;
• uint16_t ntohs(uint16_t netshort);  — конвертирует 16-битную беззнаковую величину из сетевого порядка байтов в локальный.

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

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

Ядро Linux: le16_to_cpu(), cpu_to_be32(), cpu_to_le16p(), и так далее;

Ядро FreeBSD: htobe16(), le32toh(), и так далее;

данные примеры для Erlang, Python, Perl содержат идентичную функциональность.

Этимология названия

Термины big-endian и little-endian первоначально не имели отношения к информатике. В сатирическом произведении Джонатана Свифта «Путешествия Гулливера» описываются вымышленные государства Лилипутия и Блефуску, в течение многих лет ведущие между собой войны из-за разногласия по поводу того, с какого конца следует разбивать варёные яйца. Тех, кто считает, что их нужно разбивать с тупого конца, в произведении называют Big-endians («тупоконечники»). Споры между сторонниками big-endian и little-endian в информатике также часто носят характер т. н. «религиозных войн». [2]

Термины big-endian и little-endian ввёл Коэн (англ.  Danny Cohen ) в 1980 году в своей статье «On Holy Wars and a Plea for Peace». [3] [4]

См. также

Примечания

1. ↑pack() в Perl
2. ↑DAV’s Endian FAQ (недоступная ссылка — история)
3. ↑Danny Cohen.On Holy Wars and a Plea for Peace   (англ.) (1 апреля 1980). Архивировано из первоисточника 15 февраля 2012.Проверено 24 января 2010.
4. ↑Таненбаум Э. Архитектура компьютера. — 5-е изд. — СПб. : Питер, 2007. — 844 с. — С. 89.

Ссылки

• Компьютер

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Порядок байтов» в других словарях:

обратный порядок байтов — Способ хранения и обмена данными в сети, при котором сначала передается самый младший байт, а затем остальные в порядке, обратном их размещению в блоке данных. [Л.М. Невдяев. Телекоммуникационные технологии. Англо русский толковый словарь… … Справочник технического переводчика

прямой порядок байтов — Способ хранения и обмена данными в сети, при котором сначала передается самый старший байт, а затем остальные в порядке их размещения в блоке данных. Ср. little . [Л.М. Невдяев. Телекоммуникационные технологии. Англо русский толковый словарь… … Справочник технического переводчика

Порядок байт — Порядок байтов в информатике метод записи байтов многобайтовых чисел. В общем случае, когда нужно компактно записать число, большее 255 (28 − 1 = 255 максимальное целое число, записываемое одним байтом (октетом)) необходимо использовать… … Википедия

порядок следования байтов — Под этим термином понимается порядок хранения байтов в машинном слове (или двойном слове). Порядок может быть "прямым" (т.е. 32 битовое число хранится так 0x12345678) и тогда говорят "big endianness" (на отечественном жаргоне… … Справочник технического переводчика

прямой порядок (следования) байтов — Формат для хранения и передачи двоичных данных, при которой старший (наиболее значимый бит (или байт) передается сначала. Обратное преобразование называется little endian. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN … Справочник технического переводчика

UTF-16 — (англ. Unicode Transformation Format) в информатике один из способов кодирования символов из Unicode в виде последовательности 16 битных слов. Данная кодировка позволяет записывать символы Юникода в диапазонах U+0000..U+D7FF и… … Википедия

UCS-4 — Юникод, или Уникод (англ. Unicode) стандарт кодирования символов, позволяющий представить знаки практически всех письменных языков. Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода» (англ. Unicode Consortium,… … Википедия

UNICODE — Юникод, или Уникод (англ. Unicode) стандарт кодирования символов, позволяющий представить знаки практически всех письменных языков. Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода» (англ. Unicode Consortium,… … Википедия

UTF-32LE — Юникод, или Уникод (англ. Unicode) стандарт кодирования символов, позволяющий представить знаки практически всех письменных языков. Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода» (англ. Unicode Consortium,… … Википедия

UTF-32 Little Endian — Юникод, или Уникод (англ. Unicode) стандарт кодирования символов, позволяющий представить знаки практически всех письменных языков. Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода» (англ. Unicode Consortium,… … Википедия

Таблицы истинности и логические схемы

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

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

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖<->$) или такими условными обозначениями, как ¬, 'not', и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖<->$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

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

Высказывание $A↖<->$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖<->$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если. то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

Операция эквивалентности противоположна сложению по модулю два и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.

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

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А), то вторник всегда наступает после понедельника (В)» — импликация А → В, и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Логические выражения и их преобразование

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

• выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
• непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

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

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a — π/b) < 1 = sin(π/2 — π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

Таким образом, результат логического выражения при заданных значениях— «истина».

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

Тождественные преобразования логических выражений

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

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

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

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

Примеры решения задач

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35