Какие логические выражения называются равносильными кратко

Обновлено: 06.07.2024

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

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

Проверьте самостоятельно справедливость равносильностей

Выписывание в предыдущем определении в формулах и можно представить в виде условной схемы (приведена в тексте). Формулы и заданы своими таблицами значений:

Алгоритм проверки формул на равносильность

Проанализируйте работу данного алгоритма и сопоставьте ее с определением понятия равносильности формул.

Признак равносильности формул

Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии.

Теорема 4.2 (признак равносильности формул). Две формулы

Доказательство. Если для любых высказываний . Тогда (по определению 1.9 операции эквивалентности) , откуда на основании соотношения (1.5) заключаем, что для любых . Последнее означает по определению тавтологии, что . Обратными рассуждениями доказывается утверждение: если , то — формулы, то выражение " об этих формулах. Это утверждение либо истинно, либо ложно, т.е. либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний.

Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: б) симметрично: если , то ;
в) транзитивно: если и , то , т.е. отношение равносильности является отношением эквивалентности.

Доказательство. Рефлексивность следует непосредственно из тавтологии теоремы 3.3, о и теоремы 4.2.

Для доказательства симметричности отношения предположим, что , т.е. на основании признака равносильности (теорема 4.2) принимает всегда те же самые значения, что и формула , т.е. только истинные значения. Следовательно, или (по признаку равносильности) . Симметричность доказана.

Наконец, если и , т.е. и , то на основании определения конъюнкции заключаем, что: . Привлекая теперь тавтологию из теоремы 3.3, пункт р) и правило заключения для получения тавтологий (теорема 3.5), получаем , или (по теореме 4.2) . Следовательно, отношение транзитивно.

Таким образом, отношение есть отношение эквивалентности, что и требовалось доказать.

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

Примеры равносильных формул

В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1–3.4, на основании признака равносильности формул.

Теорема 4.4. Справедливы следующие равносильности:

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

Лемма 4.5 (о замене). Если , то для любой формулы алгебры высказываний имеет место равносильность

Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.

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

принимают одинаковые значения при любых одинаковых наборах значений переменных и Следовательно,

то есть , что и требовалось доказать.

Например, на основании этой леммы и равносильности из теоремы 4.4 (пункт п), формула

Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула . Если . Если , то . Если, кроме того, , то

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

Равносильные преобразования формул

Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.

Пример 4.6. Упростим формулу , используя равносильности из теоремы 4.4:

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

Замечание 4.7. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией:

Равносильности в логике и тождества в алгебре

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

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

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

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

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

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

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

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

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

A ¬A
истина ложь
ложь истина

A ¬A
1 0
0 1

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

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


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

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

A B A ∧ B
1 0 0
0 1 0
0 0 0
1 1 1

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

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


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

A B A ∨ B
истина ложь истина
ложь истина истина
ложь ложь ложь
истина истина истина

A B A ∨ B
1 0 1
0 1 1
0 0 0
1 1 1

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

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


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

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

А В А ⊕ B
1 0 1
0 1 1
0 0 0
1 1 0

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

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

А В А → В
истина ложь ложь
ложь истина истина
ложь ложь истина
истина истина истина

А В А → В
1 0 0
0 1 1
0 0 1
1 1 1

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

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

А В А ∼ В
истина ложь ложь
ложь истина ложь
ложь ложь истина
истина истина истина

А В А ∼ В
1 0 0
0 1 0
0 0 1
1 1 1

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

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

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

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X 3) ∨ (1 3) ∨ (12 3) ∨ (3 2) → (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 — высказывание ложно.

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

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

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

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

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

$1 ≤ a ∨ A ∨ sin(π/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 = истина;

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

Построение таблиц истинности логических выражений

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы $↖ ∧ X2 ∨ ↖ ∨ X1$.

X1 X2 $↖$ $↖$ \ X2 X1 ∧ X2 $↖$ $↖$ ∧ X2 ∨ $↖$ $↖$ ∧ X2 ∨ $↖$ ∨ X1
1 1 0 0 1 0 0 1
1 0 0 0 1 0 0 1
0 1 1 1 1 0 1 1
0 0 1 0 0 1 1 1

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

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

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

Алгоритм построения ДНФ следующий:

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

X1 X2 F(X1, X2)
1 1 1
0 1 0
1 0 0
0 0 1

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ $↖$ ∧ $↖$.

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

Алгоритм построения КНФ следующий:

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

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

X1 X2 F(X1, X2)
1 1 1
0 1 0
1 0 0
0 0 1

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

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ $↖$ ∧ $↖$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ $↖$ ∧ $↖$ ∨ X2 = X1 ∧ $↖$ ∨ X1 ∧ X2 ∨ $↖$ ∧ $↖$ ∨ $↖$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $↖$ ∧ $↖$ ∨ 0 = X1 ∧ X2 ∨ $↖$ ∧ $↖$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

X1 X2 F(X1, X2)
1 1 1
1 0 0
0 1 1
0 0 0

Решение. Используем алгоритм ДНФ для построения исходной функции:

X1 X2 F(X1, X2)
1 1 1 • X1 ∧ X2
1 0 0
0 1 1 • $↖$ ∧ X2
0 0 0

Искомая формула: X1 ∧ X2 ∨ $↖$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ $↖$ ∧ X2 = X2 ∧ (X1 ∨ $↖$) = X2 ∧ 1 = X2.

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

X1 X2 X3 F(X1, X2, X3)
1 1 1 1 • X1 ∧ X2 ∧ X3
1 0 1 0
0 1 1 1 • $↖$ ∧ X2 ∧ X3
0 0 1 0
1 1 0 1 • X1 ∧ X2 ∧ $↖$
1 0 0 1 • X1 ∧ $↖$ ∧ $↖$
0 1 0 0
0 0 0 0

Искомая формула: X1 ∧ X2 ∧ X ∨ $↖$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖$ ∪ X1 ∧ $↖$ ∧ $↖$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ $↖$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖$ ∨ X1 ∧ $↖$ ∧ $↖$ = X2 ∧ X3 ∧ (X1 ∨ $↖$) ∨ X1 ∧ $↖$ ∧ (X2 ∨ $↖$) = X2 ∧ X3 ∨ X1 ∧ $↖$.

Таблицы истинности для решения логических задач

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

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

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

X1 X2 X3 Y(X1, X2, X3)
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

1-й урок 2-й урок 3-й урок
Информатика 1 1 0
Математика 1 0 1
Физика 0 1 1

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

  1. математика, информатика, физика;
  2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

  1. Борис — самый старший;
  2. играющий в футбол младше играющего в хоккей;
  3. играющие в футбол и хоккей и Петр живут в одном доме;
  4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
  5. Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

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

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Футбол Хоккей Лыжи Плавание Бадминтон Теннис
Петр 0 0 1 1 0 0
Борис 0 0 0
Алексей 0 0

Из таблицы видно, что в теннис может играть только Алексей.

Футбол Хоккей Лыжи Плавание Бадминтон Теннис
Петр 0 0 1 1 0 0
Борис 0 0 0 0
Алексей 1 0 0 0 0 1

Окончательно получаем, что Борис увлекается хоккеем и бадминтоном. Итоговая таблица будет выглядеть следующим образом:

Футбол Хоккей Лыжи Плавание Бадминтон Теннис
Петр 0 0 1 1 0 0
Борис 0 1 0 0 1 0
Алексей 1 0 0 0 0 1

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

Две формулы алгебры высказываний $A$ и $B$ называются равносильными или эквивалентными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.

Равносильность формул будем обозначать знаком $\equiv$, а запись $A\equiv B$ означает, что формулы $A$ и $B$ равносильны.

Например, равносильны формулы:

Тождественно истинная формула

Формула $A$ называется тождественно истинной < или тавтологией >, если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы $X\vee \overline < X >$, $X\rightarrow (Y\rightarrow X)$

Тождественно ложная формула

Формула $A$ называется тождественно ложной < или противоречием >, если она принимает значение 0 при всех значениях входящих в нее высказываний.

Например, тождественно ложна формула $X\wedge \overline < X >$

Выполнимая формула

Формула $A$ называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.

Например, выполнима формула $X\vee \overline < X >$

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Группы равносильностей

Между понятиями равносильности и операцией $\leftrightarrow$ существует следующая связь: если формулы $A$ и $B$ равносильны, то формула $A\leftrightarrow B$ - тавтология, и обратно, если формула $A\leftrightarrow B$ - тавтология, то формулы $A$ и $B$ равносильны.

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

Равносильности алгебры Буля

Закон двойного отрицания: $\overline < \overline < X >> \equiv X$

Коммутативность: $X\wedge Y\equiv Y\wedge X$; $X\vee Y\equiv Y\vee X$

Ассоциативность: $X\wedge (Y\wedge Z)\equiv (X\wedge Y)\wedge Z$; $X\vee (Y\vee Z)\equiv (X\vee Y)\vee Z$

Дистрибутивность $\wedge$ относительно $\vee$: $X\wedge (Y\vee Z)\equiv (X\wedge Y)\vee (X\wedge Z)$; $(X\vee Y)\wedge Z\equiv (X\wedge Z)\vee (Y\wedge Z)$

Дистрибутивность $\vee $ относительно $\wedge $: $X\vee (Y\wedge Z)\equiv (X\vee Y)\wedge (X\vee Z)$; $(X\wedge Y)\vee Z\equiv (X\vee Z)\wedge (Y\vee Z)$

Законы де Моргана: $\overline < X\wedge Y >\equiv \overline < X >\vee \overline < Y >$; $\overline < X\vee Y >\equiv \overline < X >\wedge \overline < Y >$

Законы поглощения: $X\wedge (Y\vee X)\equiv X$; $X\vee (Y\wedge X)\equiv X$

Законы идемпотентности: $X\wedge X\equiv X$; $X\vee X\equiv X$

Свойства констант: $X\wedge 1\equiv X$; $X\vee 1\equiv 1$; $X\wedge 0\equiv 0$; $X\vee 0\equiv X$

Закон противоречия: $X\wedge \overline < X >\equiv 0$

Закон исключения третьего: $X\vee \overline < X >\equiv 1$

Равносильности, выражающие одни логические операции через другие

$X\leftrightarrow Y\equiv (X\rightarrow Y)\wedge (Y\rightarrow X)$

$X\leftrightarrow Y\equiv (\overline < X >\vee Y)\wedge (\overline < Y >\vee X)$

$X\leftrightarrow Y\equiv (X\wedge Y)\wedge (\overline < Y >\wedge \overline < X >)$

$X\rightarrow Y\equiv \overline < X >\vee Y$

$X\wedge Y\equiv \overline < \overline < X >\vee \overline < Y >> $

$X\vee Y\equiv \overline < \overline < X >\wedge \overline < Y >> $

$X | Y\equiv \overline < X\cdot Y >$

$X \downarrow Y\equiv \overline < X\vee Y >$

$X \rightarrow Y\equiv \overline < X >\vee Y$

$X \bigoplus Y\equiv (X \cdot \bar < Y >)\vee (\bar < X >\cdot Y)$

$X \sim Y\equiv \overline < X \bigoplus Y >\equiv (XY)\vee (\bar < X >\bar < Y >)$

Далее:

Теорема об алгоритме распознавания полноты

Поверхностный интеграл первого рода и его свойства

Лемма о построении множества $[F]_$

Свойства тройного интеграла

Несобственные интегралы от неограниченной функции

Упрощение логических функций

Вычисление криволинейного интеграла второго рода в случае выполнения условия независимости от формы

Определение тройного интеграла. Теорема существования тройного интеграла

Функции 2-значной логики. Лемма о числе функций. Элементарные функции 1-ой и 2-х переменных

Нормальные формы

Теорема Остроградского

Полином Жегалкина. Пример.

Вычисление двойного интеграла. Двукратный интеграл

Вычисление криволинейного интеграла второго рода. Примеры.

Огравление $\Rightarrow $

04 сентября 2016, 13:38 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 20152 0




Алфавит логики высказываний состоит из трех групп символов: высказывательные переменные a , b , c , d , …, x , y , z ; логические символы , , →, ↔, −; символы скобок ( , ). Словом в алфавите называется произвольная конечная последовательность символов.

Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1) любая высказывательная переменная – формула;

2) если А и В формулы, то слова , , , , – формулы;

3) только те слова являются формулами, для которых это следует из 1) и 2).

Например: или . Скобки указывают порядок выполнения действий.

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

Пример.

1) равносильно .

2) равносильно .

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

Пример.


При x = 1, y = 1, z = 0 формула

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

Пример.


Таблица истинности логических значений формулы будет следующая:






Если формула содержит n элементарных высказываний, то она принимает 2 n значений. Таблица истинности будет содержать 2 n строк.

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

Обозначается равносильность ≡, т. е. A ≡ B .

Пример.


Следующие формулы являются равносильными:



Формула А называется тождественно истинной (или тавтологией ), если она принимает значение 1 при всех значениях входящих в нее переменных.

Пример.


Следующие формулы являются тавтологиями: ,



Формула А называется тождественно ложной , если она принимает значение 0 при всех значениях входящих в нее переменных.

Пример.


Формула является тождественно ложной.

Отношение равносильности обладает следующими свойствами: оно рефлексивно, симметрично и транзитивно.

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

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

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности


– законы идемпотентности.


– закон снятия двойного отрицания.


– законы поглощения.

Докажем формулу 4.


Пусть А ≡ при x = 1, значение А = 1, при х = 0, значение А = 0. Итак во всех случаях значения формулы А совпадают со значениями х, следовательно, А ≡ х.

2. Равносильности, выражающие одни логические операции через другие

Замечание. Формулы 5 и 6 получаются из 3 и 4, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

Докажем формулы 1–4.

Докажем формулу 1.

1) при одинаковых логических значениях x и y формулы , и – истинны, следовательно, истинной будет и коньюнкция т. е. обе части равносильности имеют одинаковые истинные значения.

2) пусть теперь x и y имеют разные логические значения , тогда будут ложными и одна из или . При этом будет ложной и коньюнкция т. е. обе части равносильности имеют одинаковые ложные значения. Что и требовалось доказать.

Докажем формулу 3.

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

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

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

Аналогично доказываются равносильности 2 и 4.

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

3. Равносильности, выражающие основные законы алгебры логики

– комм утативность коньюнкции и дизьюнкции.




Докажем формулу 6.

При х = 1, формулы , и будут истинны, тогда и – тоже истинна.

При х = 0, ≡ , ≡ ≡ следовательно,


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

Равносильности 3-ей группы выражают основные законы алгебры логики: коммутативность, ассоциативность и дистрибутивность (относительно логических операций – коньюнкции и дизьюнкции). Эти же законы имеют место в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел, т. е.

1) раскрытие скобок;

2) заключение в скобках;

3) вынесения за скобки общего множителя.

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

Равносильные преобразования формул используют

1) для доказательства равносильностей,

2) для приведения формул к заданному виду,

3) для упрощения формул.

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

Читайте также: