B) Найти все неравносильные и не тождественно ложные посылки, для которых данная формула является следствием.

Пример выполнения типового расчета.

1) Приведите пример составного высказывания, которое можно было бы записать в следующем виде. Определите его значение истинности.

Решение.

В данном составном высказывании есть три простейших: A, B, C. В качестве них можно взять, например, следующие повествовательные предложения:

A—«Розовые слоны живут в Африке»;

B—«В Солнечной системе - девять планет»;

C—«5 меньше 3».

Заменяя логические связки соответствующими речевыми оборотами, получим:

«Если розовые слоны живут в Африке и в Солнечной система девять планет, то 5 меньше 3 или в Солнечная системе число планет отлично от девяти».

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

Тогда соответственно , , и окончательно .

2) Приведите пример нечеткого высказывания.

Решение.

Высказывание: «Мужчина сорока лет – молодой человек».

Это высказывание может быть истинным или ложным в зависимости от того, какой эксперт определяет степень его истинности. Если эксперту 80 лет, то с его точки зрения 40 лет – возраст скорее молодой, чем пожилой. С точки же зрения 17-летнего эксперта, 40 лет – скорее зрелый, чем молодой возраст.

3) Вычислите степень истинности составного нечеткого высказывания , пр и условии, что , , .

Решение.

Согласно определениям логических операций над нечеткими высказываниями получаем:

,

,

и окончательно

.

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

Решение.

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

Определим порядок выполнения операций:

Замечание.

При составлении данной таблицы истинности цифры 4, 5, 6, 7 обозначают результаты соответствующих операций.

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

5) a) С помощью равносильных преобразований упростите формулу.

Решение.

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

Решение.

Сначала упростим формулу:

.

Затем, с помощью закона де Моргана, поменяем дизъюнкцию на конъюнкцию:

.

6) Приведите равносильными преобразованиями следующую формулу к ДНФ.

Решение.

Сначала все логические связки выразим через и .

,

Затем, на основании закона дистрибутивности, сделаем так, чтобы конъюнкции выполнялись раньше дизъюнкций:

Данная формула уже является ДНФ, но ее еще можно упростить:

Это и есть искомая дизъюнктивная нормальная форма.

7) Приведите равносильными преобразованиями следующую формулу к КНФ.

Решение.

Выразим все логические связки через и .

,

Далее, на основании закона дистрибутивности, сделаем так, чтобы дизъюнкции выполнялись раньше конъюнкций:

.

8) Применяя равносильные преобразования, найдите СДНФ и СКНФ для данной формулы. Проверьте полученные формы с помощью таблицы истинности.

Решение.

Чтобы найти СДНФ и СКНФ формулы, сначала построим ее ДНФ и КНФ:

Это — дизъюнктивная форма; преобразуя ее, найдем конъюнктивную форму:

Получившиеся нормальные формы не содержат одинаковых конъюнктов или дизъюнктов, и все элементарные конъюнкции и дизъюнкции правильны, то есть не содержат одинаковых переменных. Осталось пополнить каждый конъюнкт и дизъюнкт относительно набора {X, Y, Z}, чтобы получить соответственно СДНФ и СКНФ нашей формулы.

СДНФ:

.

СКНФ:

ДДля проверки построим таблицу истинности исходной формулы:

							СДНФ	СКНФ

9) Доказать следующее логическое следование 2-мя различными способами.

Решение.

Приведем 4 способа решения; читатель выберет 2 наиболее для него приемлемых.

Способ.

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

Так как, Q(X,Y,Z) принимает значение истины на всяком наборе пропозиционных переменных, на котором значение истины принимает формула Р(X,Y,Z), то по определению логического следования Р Q ■.

Способ.

□ Рассмотрим следующую формулу:

,

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

Итак, формула P→Q является тавтологией, следовательно, по Теореме 1 §8 Р Q ■

Способ.

□ Предположим противное, то есть, что Q не является логическим следствием P, тогда

, а .

Т.к.

Но, если то .

Получено противоречие, следовательно наше предположение неверно и Р Q ■

Способ.

□ Рассмотрим следующую формулу:

,

преобразуем ее

Затем воспользуемся формулой метода резолюций ├ , где в качестве Q выступает Z.

Тогда и по Теореме 1 §8 Р Q ■

10) Выясните, верны ли следующие следования из группы формул.

Решение.

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

а

Тогда из следует, что и , а значит . Если , следовательно, и одновременно . Так как, и , то .

Но, если , , , тогда .

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

11) Проверьте логичность рассуждений:

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

Решение.

Обозначим

A—«Я поеду автобусом»;

B—«Автобус опоздает»;

C—«Я пропущу назначенное свидание»;

D—«Я начну огорчаться»;

E—«Мне следует поехать домой»;

F—«Я получу работу».

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

, а следствие .

Предположим, что логическое следование неверно, т. е.

, , , .

Если , то , .

Так как, и , тогда .

Далее, из и следует, что , а значит , .

Итак , , , следовательно .

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

12) a) Найти все неравносильные между собой и не тождественно истинные следствия из данных посылок.

Решение.

Составляем конъюнкцию посылок и приводим ее равносильными преобразованиями к СКНФ:

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

1. ;
2. ;
3. ;
4. (первая посылка);
5. (вторая посылка);
6. 

;

1. .

b) Найти все неравносильные и не тождественно ложные посылки, для которых данная формула является следствием.

Решение.

Чтобы определить, логическим следствием каких посылок является данная формула, ее необходимо привести к совершенной конъюнктивной нормальной форме; в данном случае это проще сделать с помощью таблиц истинности:

					СКНФ

Недостающими дизъюнктами в этой форме являются:

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

Выписываем получившиеся формулы, придав им более удобную равносильную форму.

1.

2.

3.

4.

5.

6.

7.

Замечание.

Так как нас интересуют только не тождественно ложные посылки, то последний случай мы исключаем из ответа к задаче.

13) Задан алгоритм функционирования некоторого комбинационного цифрового устройства в виде связи между входными и выходными сигналами. Комбинации входных сигналов представлены следующей таблицей истинности