Что представляют собой логические выражения
Перейти к содержимому

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

  • автор:

Урок 22
§18. Алгебра логики

liniya

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

Для логического выражения справедливо:

1) всякая логическая переменная, а также логические константы (О, 1) есть логическое выражение;
2) если А — логическое выражение, то и — логическое выражение;
3) если А и В — выражения, то, связанные любой бинарной операцией, они также представляют собой логическое выражение.

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

1) отрицание;
2) конъюнкция;
3) дизъюнкция, строгая дизъюнкция;
4) импликация, эквиваленция.

Операции одного приоритета выполняются в порядке их следования, слева направо. Как и в арифметике, скобки меняют порядок выполнения операций.

Пример 1. Выясним, какие из приведённых слов удовлетворяют логическому условию (первая буква согласная → вторая буква согласная) & (последняя буква гласная → предпоследняя буква гласная):

1) ОЗОН;
2) ИГРА;
3) МАФИЯ;
4) ТРЕНАЖ.

Вычислим значение логического выражения для каждого из данных слов:

Итак, заданному условию удовлетворяют первое и четвёртое слова.

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

Пример 2. Решим логическое уравнение

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

Таким образом, значение переменной D уже найдено. Импликация равна нулю в единственном случае — когда из истины следует ложь. Иначе говоря, в нашем случае: А = 1 и С = 0.

Подставим найденные значения переменных в уравнение

Ответ: А = 1, В = 1, С = 0, D = 0.

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

Пример 3. Выясним, сколько различных решений имеет логическое уравнение

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

Первое равенство будет выполняться только при А = 1, В = 1 и С = 0. Поскольку D в этом уравнении не задействовано, оно может принимать любое из двух значений (0 или 1). Таким образом, всего первое уравнение имеет два решения.

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

Сколько решений имеет исходное уравнение?

Пример 4. Выясним, сколько решений имеет очень простое с виду логическое уравнение х1 & х2 → х3 & х4 = 1.

Введём замену переменных. Пусть t1 = х1 & х2, t2 = х3 & х4. Тогда исходное уравнение примет вид: t1 → t2 = 1.

На t1 никаких ограничений нет, эта переменная может принимать значения 0 и 1. Импликация равна 0 только в случае, когда из истины (1) следует ложь (0). Исключим этот вариант. Построим дерево решений, представив на нём значения переменных t1 и t2 при которых t1 → t2 = 1.

Получаем для t1 и t2 три набора значений: 00, 01, 11. Первая двоичная цифра в каждом из этих трёх наборов — результат выражения х1 & х2, вторая — х3 & х4. Рассмотрим первый набор: существует три набора х1 и х2 таких, что х1 & х2 = 0, другими словами, первый 0 мы можем получить тремя способами. Второй О в этом наборе мы также можем получить тремя способами.

Из курсов информатики и математики основной школы вам известно одно из основных правил комбинаторики — правило умножения. Согласно ему, если элемент А можно выбрать n способами, и при любом выборе А элемент В можно выбрать m способами, то пару (А, В) можно выбрать n • m способами.

Согласно правилу умножения, пару 00 можно получить 3 • 3 = 9 способами.

Что касается пары 01, то первый 0 мы можем получить тремя способами, а для получения 1 существует единственный вариант (х3 & х4 = 1 при х3 = 1 и х4 = 1). Следовательно, есть ещё три набора переменных х1, х2, х3, х4, являющихся решением исходного уравнения.

Самостоятельно доведите решение этой задачи до конца.

Cкачать материалы урока

Логическое выражение

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

Операторы

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

Операция Си Паскаль
Равно == =
Не равно != <>
Больше > >
Меньше
Больше или равно >= >=
Меньше или равно

Например, логическое выражение «5 > 3» истинно, а «6 != 6» ложно.

Операции

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

Операция Си Паскаль
Или (дизъюнкция) || or
И (конъюнкция) && and
Отрицание ! not

Примеры

Примеры сложных логических выражений:

Язык Выражение
си !A && (B || C)
паскаль not A and (B or C)
си A > 3 && B < 6
паскаль (A > 3) and (B < 6)

См. также

  • Алгебра логики
  • Битовые операции
  • Логический тип
  • Операторы

Ссылки

  • Исправить статью согласно стилистическим правилам Википедии.
  • Переработать оформление в соответствии с правилами написания статей.
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
  • Добавить иллюстрации.
  • Булева алгебра
  • Концепции языков программирования

Wikimedia Foundation . 2010 .

  • Bausch & Lomb
  • Миусский трамвайный парк

Полезное

Смотреть что такое «Логическое выражение» в других словарях:

  • Логическое выражение — выражение, в котором операндами являются объекты, над которыми выполняются логические операции. Результатом выполнения логического выражения является одно из двух логических значений: либо Истина, либо Ложь. Синонимы: Булевское выражение См.… … Финансовый словарь
  • логическое выражение — loginis reiškinys statusas T sritis automatika atitikmenys: angl. Boolean expression; logical expression vok. logischer Ausdruck, m rus. логическое выражение, n pranc. expression booléenne, f; expression logique, f … Automatikos terminų žodynas
  • логическое выражение блокировочной зависимости — [Интент] Параллельные тексты EN RU The check of bay or station interlock equations can be cancelled for all electrically controllable switchgear units within a bay. [Schneider Electric] Проверку логических выражений блокировочных зависимостей… … Справочник технического переводчика
  • ЛОГИЧЕСКОЕ И ИСТОРИЧЕСКОЕ — см. Историческое и логическое. Философский энциклопедический словарь. М.: Советская энциклопедия. Гл. редакция: Л. Ф. Ильичёв, П. Н. Федосеев, С. М. Ковалёв, В. Г. Панов. 1983. ЛОГИЧЕСКОЕ И ИСТОРИЧЕСКОЕ … Философская энциклопедия
  • Логическое и историческое — существенные моменты развития объективного мира и методы его познания. Различают объективную логику и историю развития объекта и методы познания этого объекта. Объективно логическое это общая линия, закономерность развития объекта… … Большая советская энциклопедия
  • Булево выражение — Логическое выражение в программировании конструкция языка программирования, результатом вычисления которой является «истина» или «ложь». В большинстве языков программирования среднего и высокого уровня определён набор встроенных операций… … Википедия
  • предметно-логическое значение слова — выражение словом общего понятия о предмете или явлении через один из его признаков, который в силу исторического развития значений, стал на данном этапе основным для всего понятия. Оно закреплено в языковой системе в результате коммуникативной… … Толковый переводоведческий словарь
  • СЛЕДОВАНИЕ ЛОГИЧЕСКОЕ — СЛЕДОВАНИЕ ЛОГИЧЕСКОЕ отношение между некоторым множеством высказываний Г (гипотез) и высказыванием В (заключением), отображающее тот факт, что, в силу только логической структуры названных высказываний и, значит, независимо от их содержания… … Философская энциклопедия
  • ИСЧИСЛЕНИЕ ЛОГИЧЕСКОЕ — исчисление, символы и правила которого могут быть интерпретированы в терминах логики. Любое исчисление представляет собой знаковую систему, которая, как чисто синтаксическая структура, однозначно определяется двумя порождающими процедурами: 1)… … Современный философский словарь
  • логико-семантический признак — логическое выражение семантического значения … Толковый переводоведческий словарь
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Логические выражения

Алгебра логики (англ. 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
истина ложь
ложь истина
A ¬A
1 0
0 1

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

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

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

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

A B A ∧ B
истина ложь ложь
ложь истина ложь
ложь ложь ложь
истина истина истина
A B A ∧ B
1 0 0
0 1 0
0 0 0
1 1 1

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

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

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

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

A B AB
истина ложь истина
ложь истина истина
ложь ложь ложь
истина истина истина
A B AB
1 0 1
0 1 1
0 0 0
1 1 1

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

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

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

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

А В АB
истина ложь истина
ложь истина истина
ложь ложь ложь
истина истина ложь
А В АB
1 0 1
0 1 1
0 0 0
1 1 0

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

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

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

А В АВ
истина ложь ложь
ложь истина истина
ложь ложь истина
истина истина истина
А В АВ
1 0 0
0 1 1
0 0 1
1 1 1

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

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

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

А В АВ
истина ложь ложь
ложь истина ложь
ложь ложь истина
истина истина истина
А В АВ
1 0 0
0 1 0
0 0 1
1 1 1

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

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

Сложение по модулю два А ⊕ В $(A↖ ∧B) ∧ (A ∧ B↖)$
Импликация А → В $A↖ ∨ B$
Эквивалентность А ∼ В $(A↖ ∧ B↖) ∨ (A ∧ B)$

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

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

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

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

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

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

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

A B A → B
1 0 0
0 1 1
0 0 1
1 1 1

Пример 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 = истина;

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

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

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

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

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

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

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

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

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

Закон Для ∨ Для ∧
Переместительный A ∨ B = B ∨ A A ∧ B = B ∧ A
Сочетательный A ∨ (B ∨ C) = (B ∨ A) ∨ C A ∧ (B ∧ C) = (A ∧ B) ∧ C
Распределительный A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
Правила де Моргана $↖$ = $A↖ ∧ B↖$ $↖$ = $A↖ ∨ B↖$
Идемпотенции A ∨ A = A A ∧ A = A
Поглощения A ∨ A ∧ B = A A ∧ (A ∨ B) = A
Склеивания (A ∧ B) ∨ (A↖ ∧ B) = B (A ∨ B) ∧ (A↖ ∨ B) = B
Операция переменной с ее инверсией $A ∨ A↖$ = 1 $A ∧ A↖$ = 0
Операция с константами A ∨ 0 = A
A ∨ 1 = 1
A ∧ 1 = A
A ∧ 0 = 0
Двойного отрицания $A↖$ = A

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

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

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

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

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 .

Ответ: 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

  • ООО «Экзамер», 2015—2023
  • Написать нам
  • Юридические документы

Информатика. 10 класс (Повышенный уровень)

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

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

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

1) действия в скобках;

Значение логического выражения можно определить, построив таблицу истинности для этого выражения. Для построения таблицы истинности необходимо выполнить следующие действия (пример 26.12):

1) подсчитать число переменных в выражении ( n );

2) подсчитать число логических операций в выражении ( p );

3) установить последовательность выполнения логических операций в выражении с учетом скобок и приоритетов;

4) вычислить количество столбцов в таблице ( n + p );

5) заполнить шапку таблицы, включив в нее переменные и операции в соответствии с установленной в п. 3 последовательностью;

6) вычислить количество строк в таблице ( m = 2 n );

7) записать в таблице все возможные наборы значений переменных;

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

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

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

Пример 26.14. Упростить логическое выражение и построить логическую схему, соответствующую результату.

Выполним эквивалентные преобразования выражения в соответствии с законами логики:

  1. Импликации.
  2. Де Моргана.
  3. Инволюции.
  4. Дистрибутивности.

Высказывание «Если три меньше шести (A), то суббота всегда наступает после пятницы (B)» соответствует формуле A B , и имеет значение «истина».

Высказывание «Если я куплю яблоки (A) или абрикосы (B), то приготовлю фруктовый пирог (C)» можно записать в виде формулы A V B C.

Пример 26.11. Порядок выполнения действий в логических выражениях.

Пример 26.12. Построение таблицы истинности для выражения .

3) дизъюнкция (V), инверсия (), конъюнкция ( & );

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *