Матлогики

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

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

Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.

Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.

Импликация двух логических высказываний A и B — логическое высказывание, ложное только тогда, когда B ложно, а A истинно.

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

Теорема 2.2. Логическое значение составного высказывания равно значению формулы на наборе логических значений составляющих высказываний , т.е.

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

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

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

тривиальному равенству: .

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

В этих случаях доказываемое равенство есть одно из равенств (1.1)–(1.5).

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

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

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

. Вычисляем:

В проделанных вычислениях второе равенство основано на определении 1.3 логической операции конъюнкции. Третье равенство основано на предположении индукции о том, что для формул и соотношение теоремы выполняется. Наконец четвертое равенство записано на основании того, что

.

Аналогичным образом соотношение теоремы доказывается и во всех остальных случаях конструирования формулы из формул и .

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

Формула алгебры высказываний называется выполнимой, если

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

, что . Выполнимой формулой является, в частности, формула, рассмотренная в примере 2.4. Она превращается в истинное высказывание,

если, например, вместо пропозициональных переменных подставить ложные

высказывания. Выполнима также формула , конкретизация которой рассмотрена в начале этой лекции.

Формула называется тавтологией, или тождественно истинной, если она превращается в истинное высказывание при всякой подстановке вместо переменных конкретных

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

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

, т.е. . Другими словами, опровержимые формулы

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

подставлены истинные высказывания. Формула также опровержима.

Наконец, формула называется тождественно ложной, или противоречием, если для любых конкретных высказываний

. Другими словами, тождественно ложные формулы — это такие формулы, которые не являются выполнимыми.

Правило заключения При выводе формулы из множества аксиом и посылок используют два основных правила:

а) если Fi и ( Fi ® Fj ) есть выводимые формулы, то Fj также выводимая формула, т.е.

Fi; (Fi®Fj)

Fj.

это правило называют modus ponens (m.p.).

b) если формулы ùFj и (Fi®Fj) есть выводимые формулы, то ùFi также выводимая формула, т.е

ùFj; (Fi®Fj)

ùFi.

это правило называют modus tollens (m.t.).

Правило подстановки: Если формула A доказуема в исчислении высказываний, x – переменная, B –

произвольная формула исчисления высказываний (и.в.), то формула, полученная в результате замены в формуле A переменной x формулой B, является также доказуемой формулой. Операция

замены в формуле Aпеременной x формулой B называется подстановкой и обозначается

.

2. Правило заключения: Если формулы A и A→B доказуемы в исчислении высказываний, то формула B также доказуема.

Равносильные формулы алгебры логики

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

Обозначение. A≡B.

Теорема 4.2 (признак равносильности формул). Две формулы и алгебры высказываний равносильны тогда и только тогда, когда формула является тавтологией:

(4.2)

Доказательство. Если , то по определению 4.1

для любых высказываний . Тогда (по

определению 1.9 операции эквивалентности) , откуда на основании соотношения (1.5) заключаем, что

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

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

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

а) рефлексивно: ;

б) симметрично: если , то ;

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

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

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

пункт п) заключаем: формула принимает всегда те же самые значения, что и формула

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

Наконец, если и , т.е. и , то на основании

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

получаем , или (по теореме 4.2) . Следовательно, отношение транзитивно.

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

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

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

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

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

и

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

то есть

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

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

равносильна формуле .

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

, то . Далее, пусть исходная формула имеет следующее строение: .

Если , то . Если, кроме того, , то

, то есть .

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

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

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

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

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

Конъюнкти́вный одночле́н (минте́рм) от переменных — конъюнкция этих переменных или[1] их отрицаний.

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

Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.[1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

●в ней нет одинаковых элементарных дизъюнкций

●в каждой дизъюнкции нет одинаковых пропозициональных переменных

●каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

●в ней нет одинаковых элементарных конъюнкций

●в каждой конъюнкции нет одинаковых пропозициональных букв

●каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

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

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

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

Формулы называются посылками для логического следствия .

Таким образом, , если для любых высказываний из

следует

.

Наконец можно и так сказать о логическом следствии. Составим таблицы истинности для формул

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

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

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

то просматривается значение формулы в этой строке. При выдается результат:

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

Признаки логического следствия

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

Теорема 6.3 (признак логического следствия). Формула Нбудет логическим следствием формулы тогда и только тогда, когда формула является тавтологией: .

Доказательство. Необходимость. Дано: , т.е. если

для набора высказываний имеет место , то

. Тогда для любого набора высказываний имеет место равенство

поскольку равенство нулю возможно лишь в том случае, когда и

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

. Это означает, что формула — тавтология,

т.е. .

Достаточность. Дано: . Тогда:

для любых высказываний , откуда в силу равенства (1.4)

Предположим теперь, что . Тогда:

, откуда (на основании определения 1.7) , ибо в противном случае

— противоречие. Но это значит (по определению 6.1 логического следствия), что

.

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

Теорема 6.4. Для любых формул следующие утверждения равносильны:

а) ;

б) ;

в) .