Функция дизъюнкция принимает истинное значение тогда когда
Если высказывание A истинно, будем писать A =1, а если — ложно, то A =0.
Значения логической функции для разных сочетаний значений входных переменных — или наборов входных переменных — обычно задаются специальной таблицей. Такая таблица называется таблицей истинности (комбинационной таблицей). Количество наборов входных переменных (Q) можно определить по формуле:Q=2n, где n — количество входных переменных.
Простейшим примером логической функции является функция одной переменной:
| Аргумент | Функция | |||
| X | F0(X) | F1(X) | F2(X) | F3(X) |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
- F 0 (X) — константа 0;
- F1(X) — переменная X;
- F2(X) — инверсия X;
- F3(X) — константа 1.
Рассмотрим таблицу значений функции от n переменных. Число строк в такой таблице будет равно числу всевозможных n -ок, т.е. равно 2 n . А число столбцов – числу переменных плюс единица, т.е. ( n +1). При построении таблицы учтем, что каждую n можно рассматривать как двоичное число, и выпишем их в порядке возрастания от 0 до 2 n –1.
| x1 | x2 | x3 | . | xn-1 | xn | f(x1, x2, x3, . xn-1, xn) |
| 0 | 0 | 0 | . | 0 | 0 | f(0, 0, 0, . 0, 0) |
| 0 | 0 | 0 | . | 0 | 1 | f(0, 0, 0, . 0, 1) |
| 0 | 0 | 0 | . | 1 | 0 | f(0, 0, 0, . 1, 0) |
| . | . | . | . | . | . | . |
| 1 | 1 | 1 | . | 1 | 1 | f(1, 1, 1, . 1, 1) |
В правом столбце таблицы записывают значения функции на соответствующих n -ках.
Если у двух логических функций совпадают таблицы истинности, то есть на всех наборах значений входных переменных они принимают одинаковое значение, то их называют равносильными или эквивалентными. Это обозначается знаком «=».
Тождественно-истинные функции – это логические функции, истинные на всех наборах значений входных переменных.
Тождественно ложные функции – это логические функции, ложные на всех наборах значений входных переменных.
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ.
| A | ¬A |
| 0 | 1 |
| 0 | 0 |
| A | B | A*B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| A | B | A+B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| A | B | A B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Логические операции над высказываниями
Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.
Логические операции над высказываниями
Существует 5 логических операций:
Обозначается $\bar < X >$, читается как «не $X$» или «неверно, что $X$». Логические значения высказывания $\bar < X >$ можно описать с помощью таблицы
| $x$ | $\bar < x >$ |
| 1 | 0 |
| 0 | 1 |
Таблицы такого вида принято называть таблицами истинности.
Конъюнкцией двух высказываний $X$, $Y$ называется высказывание, которое считается истинным, если оба высказывания $X$, $Y$ истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний $X$, $Y$ обозначается символом $X$&$Y$ или $X$$\wedge$$Y$ , читается «$X$ и $Y$». Высказывания $X$ и $Y$ называются членами конъюнкции или конъюнктивными элементами.
Логические значения конъюнкции описываются следующей таблицей истинности:
| $x$ | $y$ | $x$&$y$ |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Дизъюнкцией двух высказываний $X$ и $Y$ называется высказывание, которое считается истинным, если хотя бы одно из высказываний $X$ и $Y$ истинно, и ложным, если они оба ложны.
Дизъюнкция высказываний $X$ и $Y$ обозначается символом $X$$\vee$$Y$, читается «$X$ или $Y$», где «или» используется в неразделительной форме. Высказывания $X$ и $Y$ называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
| $x$ | $y$ | $x\vee y$ |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Например, высказывание «В треугольнике $DFE$ угол $D$ или угол $E$ острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике $DFE$ угол $D$ острый», «В треугольнике $DFE$ угол $E$ острый».
Импликацией двух высказываний $X$ и $Y$ называется высказывание, которое считается ложным, если $X$ истинно, а $Y$ — ложно, и истинным во всех остальных случаях.
Импликация высказываний $X$ и $Y$ обозначается символом $X \rightarrow Y$, читается «если $X$, то $Y$» или «из $X$ следует $Y$». Высказывание $X$ называют посылкой, высказывание $Y$ – заключением.
Логические значения операции импликации описываются следующей таблицей истинности:
| $x$ | $y$ | $x\rightarrow y$ |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».
Употребление слов «если . то . » в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание $X$ ложно, то высказывание «Если $X$, то $Y$» вообще не имеет смысла. Кроме того, строя предложение вида «если $X$, то $Y$» в обыденной речи, мы всегда подразумеваем, что предложение $Y$ вытекает из предложения $X$.
Употребление слов «если . то . » в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Эквиваленцией < или эквивалентностью >двух высказываний $X$ и $Y$ называется высказывание, которое считается истинным, когда оба высказывания $X$, $Y$ либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквиваленция высказываний $X$, $Y$ обозначается символом $X$$\leftrightarrow $$Y$, читается «для того, чтобы $X$, необходимо и достаточно, чтобы $Y$» или «$X$ тогда и только тогда, когда $Y$». Высказывания $X$, $Y$ называются членами эквиваленции.
Логические значения операции эквиваленции описываются следующей таблицей истинности:
| $x$ | $y$ | $x\leftrightarrow y$ |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Например, эквиваленция «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный тогда и только тогда, когда $\angle P = \angle Q$» является истинной, так как высказывания «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный» и «В треугольнике $SPQ$ с вершиной $S$ и основанием $PQ$ $\angle P = \angle Q$» либо одновременно истинны, либо одновременно ложны.
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.
Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом $X|Y$ и определяется следующей таблицей истинности:
| $x$ | $y$ | $x|y$ |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Штрих Шеффера — функция, принимающая значение ложь, если $X$ – истинно и $Y$ – истинно. Очевидно, имеют место равносильности:
1) $\overline < X >\equiv X|X$
2) $X\wedge Y \equiv (X|Y)|(X|Y)$
Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию «Штрих Шеффера».
Отметим, что $X|Y\equiv\overline < X\wedge Y >$.
Стрелка Пирса < функция Вебба >$X \downarrow Y$ – функция, принимающая значение истина, когда $X$ – ложно и $Y$ – ложно.
| $x$ | $y$ | $x\downarrow y$ |
| 1 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Отметим, что $X\downarrow Y = \overline < X >\wedge \overline < Y >= \overline < X \vee Y >$
Функция сложение по модулю 2 < функция разноименности, или сумма Жегалкина >$X\oplus Y$ — функция, принимающая значение истинно, когда $X$ и $Y$ принимают противоположные значения.
| $x$ | $y$ | $x\oplus y$ |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Отметим, что $X\oplus Y = (\overline < X >\wedge Y)\vee (X\wedge\overline < Y >)$
Итак, в математической логике для записи сложных высказываний используются следующие логические операции над простыми высказываниями:
$\sim $, $\leftrightarrow $− эквивалентно;
$\oplus $− либо, либо.
Практика
С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний $X, Y, Z$ можно построить высказывания
$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline < Y\vee (X\wedge Z) >)$
Первое из них есть дизъюнкция конъюнкции $X, Y$ и отрицания выказывания $Z$, а второе высказывание есть импликация, посылкой которой является высказывание $X$, а заключением — отрицание дизъюнкции высказывания $Y$ и конъюнкции высказываний $X, Z$.
Всякое сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции, называется формулой алгебры логики.
Высказывания обозначаются большими буквами латинского алфавита $A, B, C, …$
Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются:
- Для отрицания скобки опускаются;
- $\And $ имеет приоритет перед $\vee , \rightarrow, \equiv $;
- $\vee $ имеет приоритет перед $\rightarrow, \equiv $;
В связи с этим формулы
$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline < Y\vee (X\wedge Z) >)$
могут быть записаны так:
$X\wedge Y\vee Z$ и $X\rightarrow \overline < Y\vee X\wedge Z >$
Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы $\overline < X\wedge Z >\vee \overline < Z >$ в случае, если $X = 1, Y = 1, Z=0$ будет истина, то есть $\overline < X\wedge Y >\vee \overline < Z >= 1$.
Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Эта таблица будет содержать $2^n$ строк, где $n$ – количество переменных.
Например, для формулы $\overline < X >\vee Y\rightarrow X\wedge \overline < Y >$ таблица истинности имеет вид:
| $x$ | $y$ | $\bar < x >$ | $\bar < y >$ | $\bar < x >\vee y$ | $x\wedge \bar < y >$ | $\bar < x >\vee y \rightarrow x \wedge \bar < y >$ |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
Легко видеть, что, если формула содержит $n$ элементарных высказываний, то она принимает $2^ < n >$ значений, состоящих из нулей и единиц, или, что тоже, таблица содержит $2^ < n >$ строк.
Далее:
Линейный интеграл и циркуляция векторного поля
Несобственные интегралы от неограниченной функции
Вычисление объёмов
Односторонние и двусторонние поверхности. Ориентация поверхности
Класс Te . Теорема о замкнутости Te
Свойства криволинейного интеграла второго рода
Определение криволинейного интеграла второго рода
Полином Жегалкина. Пример.
Условия независимости криволинейного интеграла от пути интегрирования
Класс $L$. Теорема о замкнyтости класса $L$
Класс M. Теорема о замкнутости класса M
Вычисление двойного интеграла
Специальные векторные поля
Несобственные интегралы по неограниченной области
Вычисление тройного интеграла. Теорема о переходе от тройного интеграла к повторному
Огравление $\Rightarrow $
04 сентября 2016, 12:58 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 24695 0
- Теорема об алгоритме распознавания полноты
- Равносильные формулы алгебры высказываний
Логические операции над высказываниями
Эта логическая операция соответствует в обыденной жизни частице «не».
Определение. Отрицанием высказывания x называется новое высказывание, которое является истинным, если высказывание ложно, и ложным, если высказывание x истинно.
Отрицание высказывания x обозначается и читается не x . Логические значения высказывания модно описать с помощью таблицы, которая называется таблицей истинности:
Пусть x высказывание. Так как тоже высказывание, то можно образовать отрицание высказывания , то есть высказывание , которое является двойным отрицанием высказывания x . Логические значения высказываний и x совпадают.
2. Дизъюнкция (логическое сложение).
Эта логическая операция соответствует союзу «или».
Определение. Дизъюнкцией двух высказываний x , y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y истинно и ложным, если они оба ложны.
Дизъюнкция высказываний x , y обозначается x y и читается « x или y ». Логические значения дизъюнкции описываются таблицей истинности:
Высказывания x , y называются членами дизъюнкции.
x – «5>3», y – «2>4». Тогда x y – «5>3» «2>4» истинно, так как истинно высказывание x .
В алгебре логики союз «или» всегда употребляется в неисключающем смысле. Из определения дизъюнкции и отрицания следует, что высказывание x всегда истинно.
Эта логическая операция соответствует союзу «и».
Определение. Конъюнкцией двух высказываний x , y называется новое высказывание, которое считается истинным, если оба высказывания x , y истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний x , y обозначается и читается « x и y ». Высказывания x , y называются членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:
x – «6 делится на 2», y – «6 делится на 3». Тогда – «6 делится на 2» «6 делится на 3» истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания, далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Из определения операций конъюнкции и отрицания следует, что высказывание всегда ложно.
Эта логическая операция соответствует словам «если …, то…».
Определение. Импликацией двух высказываний x , y называется новое высказывание, которое считается ложным, если x истинно, а y ложно, и истинным во всех остальных случаях.
Импликация высказываний обозначается x → y и читается «если x , то y » или «из x следует y ». Высказывание x называется условием или посылкой, а высказывание y – следствием или заключением. Высказывание x → y называется следованием или импликацией. Логические значения операции импликации описываются следующей таблицей истинности:
1) x – «12 делится на 6», y – «12 делится на 3». Тогда импликация x → y – «если 12 делится на 6, то оно делится на 3» истинна, так как истинна посылка x , и истинно заключение y .
2) x – «12 делится на 2 и 3», y – «12 делится на 7». Тогда импликация x → y – «если 12 делится на 2 и 3, то оно делится на 7» ложна, так как условие истинно, а заключение ложно.
Употребление слов «если …, то…» в алгебре логики отличается от употребления их в обыденной речи, когда, как правило, считается, что если высказывание x ложно, то высказывание «если x , то y » вообще не имеет смысла. Кроме того, строя предложение «если x , то y » в обыденной речи всегда подразумевается, что предложение y вытекает из предложения x . Употребление слов «если…, то…» в математической логике не требует этого, так как в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «если x , то y ». Если при этом известно, что x истинно и доказана истинность импликации x → y то истинно и заключение y . В этом случае пишут x y и говорят, что из x следует y . Это классическое правило вывода постоянно используется в математике.
1. Эквиваленция .
Эта логическая операция соответствует словам «тогда и только тогда, когда».
Определение. Эквиваленцией или эквивалентностью двух высказываний x , y называется новое высказывание, которое считается истинным, если оба высказывания x , y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквиваленция высказываний x , y обозначается символом x ↔ y и читается «для того чтобы x , необходимо и достаточно, чтобы y » или « x тогда и только тогда, когда y ». Логические значения операции эквиваленции описываются следующей таблицей истинности :
Логические выражения
Алгебра логики (англ. 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 | A ∨ B |
| истина | ложь | истина |
| ложь | истина | истина |
| ложь | ложь | ложь |
| истина | истина | истина |
| A | B | A ∨ B |
| 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 ≤ 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—2024
- Написать нам
- Юридические документы