Элементы математической логики, ее символы

Указание о  необходимости выполнить логическое сложение высказываний A и B записывается так:

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

Это определение  можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А+В+С=0, только если , А=0, В=0, С=0.

Таблица истинности дизъюнкции имеет следующий вид:

Следующие логические законы можно назвать свойствами дизъюнкции.

Закон противоречия.

Закон равносильности (идемпотентности  idem – лат. тот же самый; potens – лат. сильный) А+А=А

Закон исключения констант А+1=1, А+0=А

     Логическое  отрицание. (inversio – лат. переворачиваю) Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией. Обозначается A или A¬.

     Иногда  вместо приведенного определения используют другое, ему эквивалентное: присоединение  слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания. В результате выполнения операции логического отрицания получается новое высказывание.

     Инверсия  логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

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

     

     Закон двойного отрицания

     Импликация. (implicatio - лат. тесно связываю) или логическое следование соответствует обороту «если…, то…», обозначается

A={Поезд прибывает на данный путь.}

B={Подается сигнал, что путь закрыт.}

Рассматриваемое сложное высказывание истинно, если:

1) поезд  прибывает, сигнал «закрыт» (1, 1, 1);

2) поезд  не прибывает, сигнал «свободен» (0, 0, 1);

3) поезд  не пребывает, сигнал «закрыт» (0, 0, 1) – если поезд не пребывает, безопасен любой сигнал;

4) высказывание  ложно (безопасность не обеспечивается) только в том случае, если поезд  прибывает, а сигнал «свободен» (1, 0, 0).

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

     

     Эквивалентность. (aequivalens – фр. равноценное) или равнозначность, соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае», обозначается , или или

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

     «Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку.» 

В русском  языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».

     Представление эквивалентности  через конъюнкцию, дизъюнкцию и инверсию

     

     

     Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается

 

2.2. Законы логики. Упрощение логических выражений

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

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

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

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

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

     

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

3. Примеры решения задач по математической логике

Пример 1.

Расставить скобки в формулах:

1 ) x∨y ↔ z⊕x ; 2) x↓y∨z ; 3) x⊕y) ↔ z→x ∧ y∨¬z .

Решение:

1 ) в формуле  x∨y ↔ z⊕x скобки расставляются следующим образом:

((x∨y) ↔ (z⊕x));

2) т.к. операция  ↓ сильнее операции ∨ согласно замечанию имеем ((x↓y)∨z);

3) в формуле  (x⊕y) ↔ z→x ∧ y∨¬z используя введенное старшинство связок, получаем, что данная формула равносильна ((x⊕y) ↔ (z→((x ∧ y)∨(¬z)))). 

Пример 2.

Составить таблицы  истинности для формул:

а) x ↔ y → ( y ⊕ x); б) x | (( y ∨ z ) ↓ x ∧ z ).

Решение:

 а) используя  введенное старшинство связок, получим,  что данная формула

равносильна x ↔ (y → (y ⊕ x)) , а таблица истинности примет вид:

б) составим таблицу  истинности для формулы x | (( y ∨ z ) ↓ x ∧ z )

 

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

при всех значениях  входящих в нее переменных. 

Пример 3.

Является, ли формула ((х → у) ∧ у) → х тождественно истинной? 

Формула равна 1 при всех значениях входящих в  нее переменных, следовательно, она

тождественно  истинная (тавтология). 

Пример 4.

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

а) если поедет Арбузов, то должны поехать еще  Брюквин или Вишневский;

б) если поедут Арбузов и Вишневский, то поедет и Брюквин.

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

Решение.

     Назначение  в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно.

Тогда условие а) можно записать в виде А→Б∨В, а условие б) в виде А&В→ Б.

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

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

L=(А→Б∨В)&(А&В→Б) эта формула должна быть истинной.

Подвергнем  формулу L равносильным преобразованиям, получим:

L=( А ∨Б∨B)&(A & B∨В)=( А ∨Б∨B)&( А ∨ В ∨Б).

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

L= А ∨[(Б∨В)&(Б∨ В )] = А ∨[Б∨(B&В )] = А ∨Б=A→Б.

Отсюда  следует, что если поедет в экспедицию Арбузов, то с ним должен ехать  и Брюквин. 

Пример 5.

     Жили  четыре друга. Звали их Альберт, Карл, Дитрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковыми, кроме того, фамилия Дитриха не Альберт. Определите фамилию и имя каждого мальчика, если дано, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого фамилия Карла.

Решение.

     Будем обозначать имя и фамилию каждого  мальчика двумя буквами в виде Ху, где «X» - первая буква имени, а  «у» - первая буква фамилии. Из условия  задачи следует, что нет мальчиков, соответствующих символам Аа, Дд, Кк, Фф, Да, то есть высказывания

Аа=Дд=Кк=Фф=Да=0. Но есть мальчик Ху такой, что есть мальчики Уф, Кх. Следовательно, истинной является формула Кх&Ху&Уф=1.

     Но  Х≠К, так как Кк=0; Х≠Ф, так как иначе будет два мальчика с фамилией Ф. Аналогично, У≠К, У≠Ф. Следовательно, или X=Д, или Х=А. Но X≠Д, так как при Х=Д, У=А и, значит, Ху =Да, что противоречит условию. Значит, Х=А, а У=Д. Поэтому истинной является формула Ка&Ад&Дф&Фк.

     Следовательно, мальчики с именами Карл, Альберт, Дитрих и Фридрих имеют фамилии  соответственно Альберт, Дитрих, Фридрих и Карл. 

4. Применение математической логики

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

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

     Информатика - это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.

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

     Идея  логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики. В 1870 году английский философ и экономист Вильям Стэнли Джевонс построил в Манчестере “логическое пианино”, которое извлекало из алгебраически записанных посылок следствия, выделяя допустимые комбинации терминов. Это называют также разложением высказываний на конституанты. Важно отметить возможность практического применения логической машины для решения сложных логических задач.

     Современные универсальные вычислительные машины являются вместе с тем логическими машинами. Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь “разумных автоматов” соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику.