§6. Приложения алгебры логики
6.1. Формализация высказываний.
Высказывание это утверждение об объектах, выраженное повествовательным предложением. Это предложение имеет однозначный смысл и о нем можно точно сказать истинно оно или ложно. Примеры высказываний:
1) 4 3 =12.
2) sin x > 1.
3) Лондон столица Франции.
4) Дон впадает в Азовское море.
Высказывания 1), 4) истинны, а высказывания 2), 3) ложны. Элементарными (простыми) называются высказывания, которые сообщают единичный факт. Сложные высказывания образуются из простых с помощью логических операций, рассмотренных ранее: отрицания, конъюнкции, дизъюнкции, импликации и других. Пусть p и q обозначают высказывания:
p: Петр водитель автомобиля;
q: Анна учится в ДГТУ;
r: Петр летчик.
Сложное высказывание «Петр водитель автомобиля и Анна учится в ДГТУ» состоит из двух частей, объединенных связкой «и». Символически это высказывание записывается в виде p q (p и q). Высказывание «Петр водитель автомобиля или Петр летчик» символически выражается как p r (p или r).
Отрицание
или опровержение высказывания p
обозначается
p
или
.
Высказывание q утверждает, что «Анна не учится в ДГТУ». Комбинация выше перечисленных связок приводит к более сложным высказываниям. Если s это высказывание «Денису нравится информатика», то высказывание «Петр не водитель автомобиля, Анна учится в ДГТУ и Денису нравится информатика» символически записывается как p q s. Высказывание «Анна учится в ДГТУ, Петр не летчик и Денису не нравится информатика» формализуется формулой q r s.
Условные высказывания вида «если p то q» выражаются импликацией p q. Например, предложение «Если Николай сдаст все экзамены без троек, то он получит стипендию» выражается импликацией p q, где p высказывание «Николай сдаст все экзамены без троек», q высказывание «он получит стипендию». Напомним, что импликация p q равносильна формуле
p q , т.е. утверждение «если p то q» означает «не p или q ». Учитывая таблицу истинности для импликации, утверждение «Если Николай сдаст все экзамены без троек, то он получит стипендию» истинно даже в том случае, когда соответствующие p и q ложны или p ложно, а q истинно.
С условным высказыванием p q связаны еще три типа высказываний: конверсия, инверсия и контрапозиция высказывания p q. Они определяются следующим образом:
q p конверсия высказывания p q;
p q инверсия высказывания p q;
q p контрапозиция высказывания p q.
Рассмотрим высказывание «если она играет на скрипке, то он кричит». Для этой импликации получаем:
конверсия: «если он кричит, то она играет на скрипке»;
инверсия: «если она не играет на скрипке, то он не кричит»;
контрапозиция: «если он не кричит, то она не играет на скрипке». Конверсию q p называют высказыванием обратным данному p q; инверсию p q противоположным высказыванием для высказывания
p q ; контрапозиция это обратное противоположное высказывание для исходного утверждения. Легко видеть, что импликация и контрапозиция имеют одну и ту же таблицу истинности, т.е. логически эквивалентны. Контрапозиция условных высказываний имеет в математике большое значение. Часто теорему легче доказать от противного, чем дать ее прямое доказательство. Однако импликация и ее конверсия (или инверсия) имеют различные таблицы истинности, игнорирование этого факта приводит к ошибкам в логических рассуждениях.
Утверждения «p эквивалентно q» , «p необходимое и достаточное условие q», «p тогда и тогда, когда q» символически записываются с помощью связки эквивалентность () p q. Например, утверждение «треугольник является равнобедренным (p) тогда и только тогда, когда углы при его основании равны (q)» формализуется формулой p q. Эквивалентность можно выразить через импликацию и конъюнкцию : p q = (p q) (q p).
6.2. Приложения алгебры логики в технике.
В технике автоматического управления широко используются релейно-контактные (переключательные) схемы (РКС). Под такой схемой понимают схематическое изображение некоторого устройства, состоящее из переключателей, соединяющих их проводников, входов в схему и выходов из нее. Переключатели это различные механические устройства, электромагнитные реле, полупроводники и т.д. Они могут находиться только в двух состояниях «замкнутом» и «разомкнутом». Входы и выходы схемы называют ее полюсами, в их качестве могут выступать клеммы, на которые подается напряжение.
П
ростейшая
схема содержит один переключатель Р
и имеет один вход А
и один выход
В.
А В
П
ереключателю
Р
ставится в соответствие высказывание
р
«переключатель Р
замкнут».
Если р
истинно, то импульс, поступающий на
полюс А,
может быть снят на полюсе
В, т.е. схема
пропускает сигнал. Если р
ложно, то переключатель разомкнут, и
схема не проводит сигнал. Формулам,
включающим основные логические операции,
также могут быть поставлены в соответствие
переключательные схемы. Конъюнкции
двух высказываний pq
ставится в соответствие схема:
A B
д
P
A B
Т.к. любая формула алгебры логики может быть записана в ДНФ, то каждой формуле алгебры логики можно поставить в соответствие некоторую РКС, а каждой РКС можно поставить в соответствие некоторую формулу алгебры логики.
Пример
6.1. Составить
РКС для формулы:
.
Сначала
упростим данную формулу с помощью
равносильных преобразований:
.
Р
КС
для данной формулы имеет вид:
Пример 6.2. Упростить РКС:
Составим для данной РКС формулу (функцию) проводимости и упростим её:
,
применили закон поглощения к последним
двум слагаемым. Упрощенная схема
выглядит так:
6.3. УМОЗАКЛЮЧЕНИЯ И ЛОГИЧЕСКИЕ СЛЕДСТВИЯ.
Умозаключения состоят из совокупности утверждений, называемых гипотезами или посылками, и утверждения, называемого следствием. Правильным называется такое умозаключение, следствие которого истинно всякий раз, когда истинны его посылки. Для анализа рассуждений используют понятие логического следствия.
Определение 6.1. Пусть логическая формула и все входящие в нее переменные. Интерпретацией формулы называется приписывание истинностных значений переменным , при котором каждому из , 1 i п, приписано значение 0 или 1.
Определение
6.2. Пусть
даны формулы
и
формула .
Говорят, что
есть логическое следствие формул
,
если для всякой интерпретации, в которой
формула
истинна,
также истинна. Тогда пишут:
.
Пример 6.3. Я заплатил бы за работу по ремонту телевизора (З), только если бы он стал работать (Р). Он же не работает. Поэтому я платить не буду.
Рассуждение записывается следующим образом: З Р, Р, следовательно З. Это рассуждение верно, если З Р Р З. Построим таблицу истинности:
З |
Р |
З Р |
Р |
З Р Р |
З |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
Из таблицы истинности следует, что З истинно в том случае, когда
З Р Р истинно. Следовательно, рассуждение верно.
6.4. РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ АЛГЕБРЫ
ЛОГИКИ.
Условие логической задачи с помощью соответствующих обозначений записывают в виде формулы алгебры логики. После равносильных преобразований формулы получают ответ на вопросы задачи.
Пример 6.4. По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом ложь. Вот, что они утверждали:
Браун: «Я совершил это. Джон не виноват».
Джон: «Браун не виноват. Преступление совершил Смит».
Смит: «Я не виноват, виновен Браун».
Определите имя старика, мошенника, чиновника и кто из них виноват, если известно, что преступник один.
Решение. Обозначим буквами Б, Д, С высказывания: виноват Браун, виноват Джон, виноват Смит соответственно. Утверждения задержанных можно записать в виде конъюнкций: Б Д, Б С, Б С, из которых по условию задачи, две ложны, а одна истинна. Поэтому будет истинной формула Ф = (Б Д) ( Б С) (Б С). Таблица истинности этой формулы:
Б |
Д |
С |
Б Д |
Б С |
Б С |
Ф |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Формула Ф истинна в пяти из восьми случаев. Случай 5 следует исключить из рассмотрения, т.к. здесь оказываются истинными две конъюнкции, а это противоречит условию задачи. В случаях 4, 6, 7 оказываются истинными по два высказывания Д и С, Б и С, Б и Д соответственно, что также противоречит условию задачи. Следовательно справедлив случай 2, т.е. преступник Смит. Он известный мошенник, оба его высказывания ложны: Б С = 0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон уважаемый в городе старик. А Браун малоизвестный чиновник.
Пример 6.5. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:
а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский:
б) если поедет Арбузов и Вишневский, то поедет и Брюквин.
Требуется:
1) ввести краткие обозначения для сформулированных условий и составить логическую формулу, выражающую принятое решение в символической форме;
2) для полученной формулы найти, возможно, более простую равносильную формулу;
3) пользуясь найденной более простой формулой, дать новую словесную формулировку принятого решения.
Решение. Назначение в экспедицию Арбузова, Брюквина, Вишневского обозначим буквами А, Б, В соответственно. Условие а) можно записать в виде: А Б В, а условие б) в виде А В Б. Т.к. оба условия должны выполняться одновременно, то они должны быть соединены логической связкой . Поэтому принятое решение записывается в виде следующей формулы:
(А Б В) (А В Б). Упростим эту формулу и получим:
(А Б В) (А В Б) = ( А Б В) ( А В Б) =
= ( А Б) (В В) = А Б.
Последняя формула означает: «если поедет Арбузов, то поедет и Брюквин».