Выполнимость формулы алгебры логики

Все формулы алгебры логики делятся на три класс:

1. тождественно истинные или тавтологии:

2. тождественно ложные или противоречия;

3. выполнимые.

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

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

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

Тождественно истинная формула не имеет СКНФ, а ложная СДНФ.

ПРИМЕР

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

 

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

 

Формула является выполнимой:

Очевидно, что тождественно ложная формула не имеет СДНФ, а тождественно истинная – СКНФ. Выполнимая формула алгебры логики имеет СДНФ и СКНФ,

 

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

 

С помощью алгебры логики можно:

· решать логические задачи;

· реализация технических устройств.

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

ПРИМЕР

Определить, Был ли Смит убийцей, если известно следующее:

Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжет.

Составим элементарные высказывания:

А – Джонс не встречал Смит этой ночью.

В – Смит был убийца.

С – Джонс лжет.

D – убийство было совершено после полуночи.

Тогда сложные высказывания можно записать на языке алгебры логики в следующем виде:

Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. -

.Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. -

Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжет. -

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

Упростим полученную формулу с помощью равносильных преобразований:

Ответ трактуется так: Либо Смит был убийцей, либо убийство совершено после полуночи Джонс лжет, что видел Смита этой ночью. Последнее сложное высказывание () по сути также определяет вину Смита, как и прямое утверждение, что Смит был убийцей (). Таким образом приговор Смиту вынесен.

 

В техническом аспекте математическая логика применяется в технических средствах автоматизации в виде релейно-контактных схем (РКС) и логических элементов «и-не», «или-не».

РКС представляют собой переключатели, которые могут находиться либо замкнутом состоянии (1), либо в разомкнутом состоянии (0).

Логические элементы «и-не» осуществляют логическую функцию:

Логические элементы «или-не» осуществляют логическую функцию:

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

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