UML_4822 дм практикум

Но следователь быстро вывел их на чистую воду, не задав ни одного вопроса. Кто из свидетелей говорил правду?

Задача 190. Разбирается дело Брауна, Джонса и Смита. Один из них совершил преступление. На следствии каждый из них сделал два заявления.

Браун. Я не делал этого. Смит сделал это.

Джонс. Смит не виновен. Браун сделал это.

Смит. Я не делал этого. Джонс не делал этого.

Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий – один раз солгал, один раз сказал правду. Кто совершил преступление?

Задача 191. Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

-Говорит Мегрэ. Есть новости?

-Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать вам, что если убийство произошло после полуночи, то или Этьен убийца, или Франсуа лжет. Затем звонила...

-Все. Спасибо. Этого достаточно. - Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.

Что следует из показаний инспекторов? Какой вывод сделал Мегрэ? Указание. Рассмотрите следующие элементарные высказывания: a={Франсуа был пьян},

b={Этьен убийца}, c={Франсуа лжет},

d={Убийство произошло после полуночи}. Задача 192. Упростите формулу:

x y y y y z ; 2) x x y x z ;

Задача 193. Доказать тождественную истинность или тождественную ложность формул:

81

1)p q p;

2)p (p q);

3)( p q) (q p) ;

4)(q p) ( p q) ;

5)( p q) & ( p q) p ;

6)p & ( p q) & ( p q) ;

7)p p q q ;

8)( p (q z)) (( p q) ( p z)) ;

9)(z p) ((z q) (z p q));

10)( p z) (( y z) (( p q) z)) ;

11)( p (q z)) ( p q z) ;

12)( p q z) ( p (q z)) ;

13)( p1 ... pn ) & ( p1 ... pn q) & q ;

14)p1 ( p2 ... ( pn 1 ( pn q q))...);

15)p p q1 q2 ... yn 1 yn (z z ) .

Ответ. Формулы 6), 7), 13), 15) – тождественно ложны, а остальные тождественно истинны.

Пример 194. Последовательность высказываний (аn) определяется следующим рекуррентным соотношением:

an an 1 (an 2 an 3 ), n 3.

Высказывания а1, а2, а3 заданы, причем а1 и а3 истинны, а а2 ложно. Истинно или ложно высказывание аn ? Как выражается аn через а1, а2, а3 ?

Решение. Используя законы алгебры логики высказываний, получа-

ем

а5 а4 & (a3 a2) (а3&(a2 a1))&(a3 a2) (а3 & (a3 a2))&(a2 a1)

а3 & (a2 a1) a4.

Аналогично можно показать, что а6 а4 (n > 3). Для n=4, 5, 6 утверждение верно. Предположим, что оно верно для всех номеров, не превосходящих n, тогда

аn+1= an&(an-1 an-2) a4&(a4 a4) a4.

Высказывание а4, очевидно, истинно, следовательно, истинно и аn.

Итак, аn=1 и аn а3& (а2 а1).

Пример 195.

1)Выразить отрицание импликации через основные операции так, чтобы отрицания стояли только над аргументами.

2)Выразить операцию дизъюнкции через импликацию.

3)Выразить все основные операции:

3.1. Через операцию дизъюнкции и отрицание;

82

3.2.Через операцию конъюнкции и отрицание;

3.3.Через дизъюнкцию и отрицание;

3.4.Через импликацию и отрицание.

Решение.

1.a b a & b .

2.a b (a b) b .

Задача 196. Студент решил в воскресенье закончить курсовой проект, сходить в музей или картинную галерею, а если будет хорошая погода

– пойти на Солнечный пляж. В каком случае можно сказать, что решение студента не выполнено? В ответе отрицания должны содержаться лишь в простых высказываниях.

Ответ. Решение студента не выполнено, если он не закончил работу над курсовым проектом, или не сходил ни в музей, ни в картинную галерею, или, хотя была хорошая погода, он не был на Солнечном пляже. Запишите это сложное событие (высказывание) посредством логической формулы.

Пример 197. Выразите операцию неравнозначности через конъюнкцию, дизъюнкцию и отрицание. Результат проверьте путем составления таблицы истинности.

Решение.

x y (x & y) (x & y) x y (x y) & ( y x)

(x y) & ( y x) (x y) ( y x) (x & y) (x & y).

Составим таблицу истинности операции неравнозначности, которую иногда еще называют исключающей дизъюнкции.

Таблица 3.5 Таблица истинности операции импликации

Пример 198. Штрихом Шеффера двух высказываний х и у называют новое высказывание, обозначаемое x|y (читают «х не совместно с у»), которое ложно только тогда, когда оба данные высказывания истинны. Со-

83

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

Решение.

x | y x & y x y ;

xx | x; x & y (x | y) | (x | y) ;

xy (a | a) | ( y | y) .

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

Решение.

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

84

Задача 201. Следующие равносильности доказать двумя способами

– с помощью таблиц истинности и посредством равносильных преобразований:

1)p (q r) pq r ;

2)( p q)( p r) p qr ;

3)( p r) (q r) pq r ;

4)p (q r) q ( p r) ;

5)pq pq pq p q 1.

Решение. Произведем указанные действия по доказательству равно-

сильности 1):

p (q r) p (q r) p q r pq r p q r p q r .

Задача 202. Следующие формулы с помощью преобразований привести к возможно более простому виду:

1)pq pr qr q r ;

2)pqr pqr pq ;

3)( p q)(q p) ;

4)( p q ) p q ;

5)p q ( p q) p .

Ответ. 1) p q r ; 2) р; 3) р; 4) p q ; 5) р q.

85

3.3. Функции алгебры логики. Совершенные нормальные формы

Определение. Функцией алгебры логики n переменных называется любая функция n переменных F(x1, x2, ..., xn), аргументы которой принимают два значения 1 и 0, а сама функция принимает одно из двух значений: 1 или 0.

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

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

F(x1, x2, ..., xn) = F(1, 1,...,1)& x1 & x2 & ... & xn F(1, 1, ..., 0)

& x1 & x2 & ... & &xn 1 & xn ... F(0, 0, ..., 0) &x1 & x2 &... & xn . (3.1)

Формулу (3.1) можно преобразовать к формуле, которая содержит только элементарные переменные высказывания и обладает следующими свойствами:

1)каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1, x2, ..., xn);

2)все логические слагаемые формулы различны;

3)ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание;

4)ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

С помощью таблицы истинности, определяющей функцию F(x1, x2,

..., xn), легко получить соответствующую формулу алгебры логики, обладающую вышеописанными свойствами.

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

рых функция F(x1, x2, ..., xn) принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции xi, если значение xi на указанном наборе значений переменных есть 1, и отрицание xi, если значение xi есть 0. Дизъюнкция всех полученных таким образом конъюнкций и будет искомой формулой.

Определение. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

Определение. Дизъюнктивной нормальной формулой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Определение. Совершенно дизъюнктивной нормальной формой (СДНФ) формулы А называется ДНФ А, обладающая указанными выше четырьмя свойствами.

86

СДНФ формулы А можно получить двумя способами: а) с помощью таблицы истинности; б) с помощью равносильных преобразований.

Правило получения СДНФ из формулы А с помощью равносильных преобразований:

1.Для формулы А получаем любую ДНФ.

2.Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь четырех свойств СДНФ:

1) Пусть в В есть слагаемое ДНФ, не содержащее xi. Тогда надо заменить слагаемое В в ДНФ А на слагаемое B&(xi xi ) (B & xi ) (B & xi ) .

2)Если в ДНФ формулы А имеют место два одинаковых слагаемых В В, то лишнее необходимо отбросить, поскольку В В=В.

3)Если в некоторое слагаемое В в ДНФ А переменная xi входит два-

жды, то лишнюю переменную нужно удалить, так как xi & xi xi .

4) Если некоторое слагаемое В в ДНФ А содержит конъюнкцию xi & xi , то это слагаемое удаляют, поскольку xi & xi 0 , и, следовательно,

В = 0, а ложное высказывание из дизъюнкции можно выбросить (в силу равносильности С 0 С).

Определение. Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний.

Определение. Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

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

1)все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные;

2)все элементарные дизъюнкции, входящие в КНФ А, различны;

3)каждая элементарная дизъюнкция, входящая в КНФ А, содержит переменную один раз;

4)ни одна элементарная дизъюнкция, входящая в КНФ формулы А, не содержит одновременно переменную и ее отрицание.

СКНФ можно получить двумя способами:

а) с помощью таблицы истинности. Используя закон двойственности

СКНФ А ÑÄÍ Ô À , вначале по таблице истинности получают СДНФ Ā,

а затем - СКНФ А; б) с помощью равносильных преобразований.

Правило получения СКНФ из формулы А с помощью равносильных преобразований.

1. Для формулы А получаем любую КНФ.

87

2. Из КНФ А путем равносильных преобразований получаем СКНФ А, последовательно добиваясь выполнения четырех свойств СКНФ.

1) Если элементарная дизъюнкция В, входящая в КНФ А, не содержит переменную xi, тогда заменяем В на

B (x & xi ) (B xi ) & (B xi ) .

2) Если в некоторую элементарную дизъюнкцию В переменных xi входит дважды, то лишнюю переменную нужно отбросить, так как xi xi xi.

3)Если КНФ А содержит две одинаковых элементарных дизъюнкции, то одну можно отбросить, так как В&В В.

4)Если в элементарную дизъюнкцию входит пара xi xi , то ее мож-

но удалить, так как xi xi 1, а истинное высказывание из конъюнкции

можно выбросить (в силу равносильности С&1 C).

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

А p (qr pq).

Решение.

А = p (qr pq) p(q r pq) p(q r pq) pq pr pq ÄÍ Ô À.

В соответствии с правилами получения СДНФ А из ДНФ А введем недостающие переменные в конъюнкции:

АДНФ А pq(r r ) pr (q q) pq(r r )

pqr pq r pqr pq r pqr pqr

pqr pq r pqr pqr СДНФ А.

Ответ. СДНФ А pqr pq r pqr pqr .

Пример 204. Для формулы из примера 203 найти СДНФ путем составления таблицы истинности.

Решение. Составим таблицу истинности для формулы А p (qr pq).

88

то есть формула записана по значениям F(x, y, z) 1. Упростив эту формулу, получим:

yz(x x) x z ( y y) x y z yz x z x yz yz x (z yz)

yz x(z y)(z z ) yz x(z y) ( yz x) & ( yz z y)

( y x)(z x)( y z y)(z z y) ( y x)(z x) x yz x yz .

Таким образом, искомой формулой, определяющей функцию F(x, y, z), можно считать x yz или x yz , или какую-нибудь другую из

равносильных им формул.

Задача 208. Установите, какие из данных формул являются ДНФ, СДНФ, КНФ, СКНФ формул с переменными x, y, z:

Ответ. 1) ДНФ; 2) СДНФ; 3) КНФ; 4) ДНФ, СКНФ; 5) СДНФ, КНФ; 6) КНФ; 7) ни одна из нормальных форм.

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

Задача 209. Заданные функции привести к ДНФ, СДНФ, КНФ, СКНФ:

1) x y z ;

3) x y x ;

5) xyz xy xy z .

Решение.

Например, формулу 4) приведем к СДНФ. Вначале получим ее ДНФ. x y & z x xy z x xyz xy .

Теперь можно получить СДНФ. Формула не удовлетворяет четвертому признаку СДНФ, для этого последнюю конъюнкцию домножим на недостающую переменную z z :

xyz xy z z xyz xyz xy z xyz xy z .

Формулу 5) приведем к СКНФ. Для этого предварительно получим

какую-нибудь КНФ:

xyz xy xy z x y z xy xy z x y z x y xy zx y z x y x x y y x y z .

Удалим члены конъюнкции, содержащие переменную вместе с ее отрицанием, а также повторяющиеся члены конъюнкции кроме одного. В

90