Отыскание нормальных форм формул логики высказываний

Формулы алгебры высказываний могут быть приведены к нормальным формам: дизъюнктивной и конъюнктивной.

Конъюнктивным (дизъюнктивным) одночленом от переменных Х₁, Х₂,…,Х_n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Сокращенная запись: ДН-форма (или ДНФ) и КН-форма (или КНФ) соответственно. Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него.

Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. Сокращенная запись: СДН-форма (или СДНФ) – совершенная дизъюнктивная нормальная форма, СКН-форма (или СКНФ) – совершенная конъюнктивная нормальная форма.

Например, (X₁ ÙØ X₂ Ù Х₃)Ú(Х₁ Ù Х₃)ÚØ Х₂ – дизъюнктивная (но не совершенная) нормальная форма от трех переменных Х₁, Х₂, Х₃, а (Х₁ ÚØ Х₂)Ù(Ø Х₁ Ú Х₂)Ù(Ø Х₁ ÚØ Х₂) – совершенная конъюнктивная нормальная форма от двух переменных Х₁ и Х₂.

Для того чтобы формулу равносильными преобразованиями привести к ДНФ, нужно руководствоваться следующим алгоритмом:

1) избавиться от операции импликации и эквивалентности, выразив их через логические связки Ø, Ù и Ú по законам: X ® Y ºØ X Ú Y, X «Y º (ØX Ú Y)Ù(Ø Y Ú X);

2) довести знаки отрицания до независимых переменных, используя законы де Моргана: Ø(X Ú Y) ºØ X ÙØ Y, Ø(X Ù Y)ºØ X ÚØ Y;

3) применяя закон дистрибутивности (X Ú Y)ÙZº(X Ù Z)Ú(Y ÙZ), преобразовать формулу к дизъюнкции конъюнктивных одночленов;

4) постоянно избавляться от двойных отрицаний: ØØ Х º Х.

Пример 1.1.

Привести равносильными преобразованиями формулу Ø(X Ú Z)Ù(X ® Y) к дизъюнктивной нормальной форме.

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

Ø(Х Ú Z)Ù(X®Y)º (Ø X ÙØ Z)Ù(Ø X Ú Y)ºØ X Ù(ØZÙ(Ø X Ú Y))º Ø X Ù((ØZÙØ X)Ú(ØZÙ Y))º(Ø X ÙØ Z ÙØ X)Ú(Ø X Ù Y ÙØ Z) º(Ø X ÙØ Z)Ú(Ø X Ù Y ÙØ Z).

Пример 1.2.

Привести равносильными преобразованиями формулу примера 1.1 к конъюнктивной нормальной форме.

Решение. Формулу равносильными преобразованиями можно привести к КНФ, руководствуясь приведенными четырьмя правилами, с той лишь разницей, что в правиле 3) следует использовать другой (двойственный) закон дистрибутивности: (X Ù Y)Ú Z º(Х Ú Z)Ù(Y Ú Z).

Преобразуем данную формулу:

Ø(Х Ú Z)Ù(X®Y)º(Ø X ÙØ Z)Ù(Ø X Ú Y)º(Ø X ÙØZ)Ú(Ø X Ù Y ÙØ Z)º((Ø X ÙØ Z)ÚØ X)Ù

Ù((Ø X ÙØ Z)Ú Y)Ù((Ø X ÙØ Z)ÚØZ)ºØ X Ù((Ø X Ú Y)Ù(Ø Z Ú Y))ÙØ Z ºº(Ø X Ù(Ø X Ú Y))Ù((Ø Z Ú Y)ÙØ Z)ºØ X ÙØ Z.

Пример 1.3.

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

Решение. Чтобы привести формулу к СДНФ, нужно сначала равносильными преобразованиями привести ее к какой-нибудь ДНФ (см. пример 1.1). При этом нужно убрать члены дизъюнкции, содержащие переменную вместе с ее отрицанием, а из одинаковых членов дизъюнкции удалить все, кроме одного. Если какой-либо конъюнктивный одночлен в ДНФ содержит не все переменные из числа входящих в исходную формулу, то его умножают на единицы, представляемые в виде дизъюнкций X_i ÚØ X_i каждой недостающей переменной X_i с ее отрицанием Ø X_i (закон исключенного третьего). Затем раскрывают скобки внутри каждого такого конъюнктивного одночлена, применяя закон дистрибутивности конъюнкции относительно дизъюнкции. Наконец, если среди членов полученной дизъюнкции окажутся одинаковые конъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.

Приведем данную формулу к СДНФ, начав преобразования с ДНФ, полученной при решении примера 1.1:

Ø(Х Ú Z)Ù(X ® Y)º(Ø X ÙØ Z) Ú (Ø X Ù Y ÙØ Z)º((Ø X ÙØ Z)Ù(Y ÚØ Y))Ú(Ø X Ù Y ÙØ Z)º º(Ø X ÙØ Z Ù Y)Ú(Ø X ÙØ Z ÙØ Y)Ú(Ø X Ù Y ÙØ Z) º(Ø X Ù Y ÙØ Z)Ú(Ø X ÙØ Z ÙØ Y).

Пример 1.4.

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

Решение. Правила приведения формулы к СКНФ двойственны соответствующим правилам приведения к СДНФ. Найчав с какой-нибудь КНФ данной формулы, нужно в каждом ее дизъюнктивном одночлене, в котором присутствуют не все переменные из числа входящих в данную формулу, добавить (через дизъюнкцию) нули, представляемые в виде конъюнкции X_i ÙØ X_i каждой недостающей переменной X_i с ееотрицанием Ø X_i. Затем внутри каждого такого дизъюнктивного одночлена раскрыть скобки, используя закон дистрибутивности дизъюнкции относительно конъюнкции. Если среди членов полученной конъюнкции окажутся одинаковые дизъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.

Приведем данную формулу к СКНФ, начав преобразование с КНФ, полученной при решении примера 1.2:

Ø(Х Ú Z)Ù(X ® Y)ºØ X ÙØ Z º(Ø X Ú(Y ÙØ Y))Ù(Ø Z Ú(X ÙØ X))º(Ø X Ú Y)Ù(Ø X ÚØ Y)Ù

Ù(X ÚØ Z)Ù(Ø X ÚØ Z)º(Ø X Ú Y Ú(Z ÙØ Z))Ù(Ø X ÚØ Y Ú(Z ÙØ Z))Ù(X ÚØ Z Ú(Y ÙØ Y))Ù

Ù(Ø X ÚØ Z Ú(Y ÚØ Y))º(Ø X Ú Y Ú Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø XÚ Ø YÚZ)Ù(Ø X ÚØ Y ÚØ Z)Ù Ù(XÚYÚ Ø Z)Ù(X ÚØ Y ÚØ Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø XÚ Ø YÚ Ø Z)º º(Ø X Ú Y Ú Z)Ù(Ø X Ú Y ÚØ Z)Ù(Ø X ÚØ Y Ú Z)Ù(Ø XÚ Ø YÚ Ø Z)Ù(XÚYÚ Ø Z)Ù(X ÚØ Y ÚØ Z).

 

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

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

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

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

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

Пример 1.5.

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

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

(P ® Q)®((R Ú P)®(R Ú Q))ºØ(P ® Q)Ú((R Ú P) ®(R Ú Q))º (P ÙØ Q)ÚØ(R Ú P)Ú Ú(R Ú Q) º (P ÙØ Q) Ú(Ø R ÙØ P) Ú(R Ú Q) º (P ÚØ R)Ù (P Ú Ø P) Ù(Ø Q ÚØ R)Ù

Ù(Ø Q ÚØ P)Ú(R Ú Q)º (P ÚØ R)Ù(Ø Q ÚØ R)Ù(Ø Q ÚØ P)Ú(R Ú Q) º º (P ÚØ R Ú R Ú Q)Ù(Ø Q ÚØ R Ú R Ú Q)Ù(Ø Q ÚØ P Ú R Ú Q).

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

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

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

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

Пример 1.6.

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

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

(P Ù(P ® Q)) ® Q º(P Ù(Ø P Ú Q))® Q ºØ(P Ù(Ø P Ú Q)Ú Q º º Ø P ÚØ(Ø P Ú Q))Ú Q º Ø P Ú(P ÙØ Q)Ú Q º (Ø P Ú Q)Ú(P ÙØ Q)º º (Ø P Ú Q Ú P)Ù(Ø P Ú Q Ú Ø Q).

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

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

Таблица 2

P	Q	P ® Q	P Ù(P ® Q)	(P Ù(P ® Q))® Q

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

 

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

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

Рассуждение называется правильным, если из конъюнкции посылок следует заключение, т. е. формула P ₁Ù P ₂Ù... Ù P_n ® D тождественно истинна.

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

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

P ₁, P ₂,..., P_n

D

Пример 1.7.

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

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

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

А ® Ø B, B

Ø А

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

((А ®Ø B)Ù B)®Ø А º Ø((А ®Ø B)Ù B)ÚØ A º (A Ù B)ÚØ B ÚØ A º

º (Ø А Ú Ø B Ú A)Ù(Ø A ÚØ B Ú B) º 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. Установить, является ли данное рассуждение правильным (проверить, следует ли заключение из конъюнкции посылок).

 

Варианты индивидуальных заданий

Вариант № 1

1. (P ® Q) ® ((Q ® R) ® (P ® R)).

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

Вариант № 2

1. (P ® Q) ® ((P ® (Q ® R)) ® (P ® R)).

2. Профсоюзы штата будут поддерживать губернатора, если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.

Вариант № 3

1. (P ® R) ® ((Q ® R) ® ((P Ú Q) ® R)).

2 Если подозреваемый совершил кражу, то либо она была тщательно подготовлена, либо он имел соучастников. Если бы кража была тщательно подготовлена, то, если бы были соучастники, украдено было бы много. Украдено мало. Значит, подозреваемый невиновен.

Вариант № 4

1. (Q ® R) ® ((P Ú Q) ® (P Ú R)).

2. Если курс ценных бумаг растет или процентная ставка снижается, то падает курс акций. Если процентная ставка снижается, то либо курс акций не падает, либо курс ценных бумаг не растет. Курс акций понижается. Следовательно, снижается процентная ставка.

Вариант № 5

1. ((Q Ú (R «Ø P)) ® (R Ù (P ® Q))) Ú Ø R.

2. Договор будет выполнен тогда и только тогда когда дом будет закончен в феврале. Если дом будет закончен в феврале, то мы можем переехать в марте. Договор будет выполнен, Следовательно, мы можем переехать в марте.

Вариант № 6

1. ((P ® Q) ® (Q ® R))Ù P ® R.

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

Вариант № 7

1. (Q Ú (R ® P)) ® (R Ù (P ® Q)).

2. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастет. Безработица не возрастет. Следовательно, правительственные расходы возрастут.

Вариант № 8

1. (P ® Q) ® ((Q ® R) ® (P ® R)).

2. В бюджете возникнет дефицит, если не повысят налоги. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят налоги, то расходы на социальные нужды не сократятся.

Вариант № 9

1. (P ® Q) ® ((Q ® R) ® (P ® R)).

2. Если цены высоки, то и заработная плата высока. Цены высоки или применяется регулирование цен. Если применяется регулирование цен, то нет инфляции. Наблюдается инфляция. Следовательно, заработная плата высока.

Вариант № 10

1. ((Q Ú (R «Ø P)) ® (R Ù (P ® Q))) Ú Ø R.

2. Если я устал, я хочу вернуться домой. Если я голоден, я хочу вернуться домой или пойти в ресторан. Я устал и голоден. Поэтому я хочу вернуться домой.

Вариант № 11

1. (P ® Q) ® ((Q ® R) ®(P ® R)).

2. Если будет холодно, то я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен. Значит, я не надену теплое пальто.

Вариант № 12

1. (P ® Q) ® ((P ® (Q ® R)) ® (P ® R)).

2. Если будет идти снег, машину будет трудно вести. Если будет трудно вести машину, я опоздаю, если не выеду пораньше. Идет снег, и я выеду пораньше. Значит, я не опоздаю.

Вариант № 13

1. (P ® R) ® ((Q ® R) ® ((P Ú Q) ® R)).

2 Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

Вариант № 14

1. (Q ® R) ® ((P Ú Q) ® (P Ú R)).

2. Если бы он был умен, то он увидел бы свою ошибку. Если бы он был искренен, то он признался бы в ней. Однако он не умен и не искренен. Следовательно, он или не увидит свою ошибку, или не признается в ней.

Вариант № 15

1. ((Q Ú (R «Ø P)) ®(R Ù (P ® Q))) Ú Ø R.

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

Вариант № 16

1. ((P ® Q) ® (Q ® R))Ù P ® R.

2. Андрей или очень переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, Андрей не болен.

Вариант № 17

1. (Q Ú (R ® P)) ® (R Ù(P ® Q)).

2. Если Иванов работает, то он получает зарплату. Если же Иванов учится, то он получает стипендию. Но Иванов не получает зарплату или не получает стипендию. Следовательно, он не работает или не учится.

Вариант № 18

1. (P ® Q) ®((Q ® R) ®(P ® R)).

2. Если я лягу спать, то не сдам экзамен. Если я буду заниматься ночью, то тоже не сдам экзамен. Следовательно, я не сдам экзамен.

Вариант № 19

1. (P ® Q) ® ((Q ® R) ® (P ® R)).

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

Вариант № 20

1. (R ® P) ®((P ® Q) ® (R ® Q)).

2. Если человек занимается спортом, то он здоров. Если человек здоров, то он счастлив. Этот человек занимается спортом. Значит, он счастлив.

 

Тема 2. ЛОГИКА ПРЕДИКАТОВ