Глава 7. Задачи и упражнения

7.1. ПОВТОРЕНИЕ МАТЕРИАЛА ИЗ КУРСА

«ДИСКРЕТНАЯ МАТЕМАТИКА»

Совершенной конъюнктивной нормальной формой (СКНФ) логической функции называют представление её в виде конъюнкции макстермов, построенных из аргументов рассматриваемой функции:

.

Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции называют представление её в виде дизъюнкции минтермов, построенных из аргументов :

.

Пример. Привести заданную логическую функцию к форме СДНФ с использованием обоих известных способов:

x	y	z

Пример. Привести заданную логическую функцию к форме СКНФ с использованием обоих известных способов:

x	y	z				f(x, y, z)

1. Построить таблицы истинности для заданной логической функции:

а) ;

б) ;

в) ;

г) .

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

а) ;

б) ;

в) ;

г) .

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

а) ;

б) ;

в) ;

г) .

7.2. ЛОГИКА ВЫСКАЗЫВАНИЙ

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

1) ;

2) ;

3)

4) ;

5)

6)

7)

8) (

9) .

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

а)

Подформула	Глубина

б)

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

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) ;

12) ;

13) .

3. Доказать, используя метод эквивалентных преобразований, справедливость аксиом исчисления высказываний:

1) ;

2) ;

3) ;

4) ;

5) .

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

Пусть при некоторой интерпретации .

Это возможно, только если

;	(7.1)
.	(7.2)

Тогда из (7.1) следует, что возможна одна из следующих комбинаций значений переменных a и b:

;

;

.

Из (7.2) следует , это означает, что возможны следующие значения c и a:

;

;

.

Из имеем . Это единственно допустимые для c и b значения, при которых формула принимает значение «ложь». Сопоставляем полученные результаты с ранее рассмотренными возможными значениями переменных.

Оказывается, что при единственное допустимое значение для a - это , а при единственное допустимое значение . То есть переменная a должна принимать взаимно исключающие значения, что невозможно. Следовательно, предположение о существовании интерпретации, при которой формула принимает значение «ложь», неверно, и это означает ее общезначимость.

4. Доказать, используя алгоритм редукции:

1)

2)

3)

4)

5)

6)

7)

8)

9) ;

10) ;

11) ;

12)

5. Используя правила эквивалентных преобразования, доказать тождественную истинность выражений из п. 4.

Пример. Доказать, используя метод резолюций, что S является логическим следствием множества гипотез H, где , а . Сначала преобразуем множество гипотез в множество дизъюнктов:

1. ;

2. ;

3. ;

4. .

Для доказательства того, что H |= S, необходимо и достаточно доказать невыполнимость следующего множества дизъюнктов:

.

1. 2. 3. 4. 5. a 6. b 7. 8. d ( ) 9. ( ) 10. c ( ) 11. ( ) 12. ( ) 13. ( ) 14. Пустой дизъюнкт ( )

6. Используя метод резолюций для логики высказываний доказать справедливость вывода для заданного множества гипотез Н={h₁, h₂ ,..., h_m} и следствия S:

1) H = {a®( Úc), c&d®e, ®d& }, S = a®(b®f);

2) H = {(aÚb)®c&d, (dÚe)®f}, S = a®f;

3) H = {a®b&c, Úd, (e® )® , b®a& }, S = b®e;

4) H = {(a®b)&(c®d), (b®e)&(d®f), e&f, a®c}, S = ;

5) H = {pÚ Ú , q, r, tÚ Ú , tÚ }, S = p&q&r;

6) H = {a~b, b®c, Úd, ®d}, S = d;

7) H = {(aÚb)®(cÚd), , d®g}, S = c;

8) H = {(c®g)&(d®s), s&g®e, }, S = Ú ;

9) H = {abÚ , Úc, c®d, aÚd}, S = d;

10) H = {a& , Úg, Ú(cÚd)}, S = c;

11) H = { Ú Úb, d®a, Úb}, S = ;

12) H = { Ú(b®c), Úe, fÚ( )}, S = Ú Úf;

13) H = {( Úb)&( Úd), ( Úe)&( Úf), Ú , Úc}, S = .

Пример. Используя метод прямой и обратной дедукции доказать справедливость вывода для заданного множества гипотез Н={h₁, h₂ ,..., h_m} и следствия S:

, .

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

Прямая дедукция: .

Доказательство:

Обратная дедукция:

Доказательство: