Главная страница

матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009


Скачать 0.58 Mb.
НазваниеМетодические указания к выполнению практических работ Омск Издательство Омгту 2009
Анкорматлогика_методичка.doc
Дата04.05.2017
Размер0.58 Mb.
Формат файлаdoc
Имя файламатлогика_методичка.doc
ТипМетодические указания
#7036
страница4 из 14
1   2   3   4   5   6   7   8   9   ...   14

1.4. Тождественно истинные и тождественно ложные формулы.
Проблема разрешимости


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

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

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

Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно ложной.

Пример 1.5.

Доказать, что формула F =(PQ)((RP)(RQ)) является тождественно истинной.

Применяя равносильные преобразования, приведем формулу к КНФ:

(PQ)((RP)(RQ))(PQ)((RP)(RQ))(PQ)(RP) (RQ)(PQ) (RP) (RQ) (P R) (P P) (QR)

(QP)(RQ)(PR)(QR)(QP)(RQ)  (PRRQ)(QRRQ)(QPRQ).

В первую дизъюнкцию входят R и R. Во вторую – Q и Q, R и R. в третью – Q и Q. Следовательно, можно утверждать, что исходная формула является тождественно истинной.

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

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.6.

Установить, является ли тождественно истинной данная формула логики высказываний: F(P, Q) = (P(PQ))Q.

1) Применяя равносильные преобразования, приведем формулу к КНФ:

(P(PQ))Q (P(PQ))Q(P(PQ)Q  P(PQ))QP(PQ)Q (PQ)(PQ) (PQP)(PQQ).

В первую дизъюнкцию входят P и P. Во вторую – Q и Q, поэтому формула является тождественно истинной, F(P, Q)  1.

2) Составим таблицу истинности F(P, Q) (таблица 2).

Таблица 2

P

Q

PQ

P(PQ)

(P(PQ))Q

0

0

1

0

1

0

1

1

0

1

1

0

0

0

1

1

1

1

1

1

Из таблицы 2 видно, что F(P, Q)  1.

1.5. Формализация рассуждений. Правильные рассуждения


Рассуждение – это построение нового высказывания D на основании уже имеющихся высказываний P1, P2, ... , Pn. Высказывания P1, P2, ... , Pn называются посылками, а высказывание D – заключением.

Рассуждение называется правильным, если из конъюнкции посылок следует заключение, т. е. формула P1P2 ...  PnD тождественно истинна.

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

Схематически рассуждение изображается следующим образом:

P1, P2, ... , Pn

D

Пример 1.7.

Проверить правильность следующих рассуждений.

а) Если погода дождливая, то небо не ясное. Небо ясное. Значит, погода не дождливая.

Введем высказывания: А= "Погода дождливая"; B= "Небо ясное". Схема рассуждения имеет вид:

А  B, B

А

Докажем, что формула ((АB)B)А является тождественно истинной. Приведем эту формулу к КНФ и покажем, что формула тождественно истинна:

((АB)B)А ((АB)B)A  (AB)BA

 (АBA)(ABB)  1.

Значит, рассуждение правильное.

б) Если будет хорошая погода, я пойду гулять. Если будет плохая погода, я буду читать книгу. Погода будет хорошая. Следовательно, я не буду читать книгу.

Введем высказывания: А = “Будет хорошая погода”; B = “Я пойду гулять”. C = “Я буду читать книгу”. Схема рассуждения имеет вид:

АB, A  С, A.

С

Найдем КНФ формулы ((АB)  (AС)  A) C:

((АB)  (AС)  A) C ((АB)  (A  С) A) C (АB)  (AС) A) C А  B  A С A C А  B  A C (А  A C)  (B  A C) B  A C.

Полученная КНФ нашей формулы не содержит одновременно какой-либо переменной и ее отрицания. Следовательно, формула не является тождественно-истинной, а рассуждение не является правильным.

1   2   3   4   5   6   7   8   9   ...   14


написать администратору сайта