7.2. Логика высказываний

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

1. ;

2. ;

3. 

4. ;

5. 

6. 

7. 

8. (

9. .

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

а)

Подформула	Глубина
	0
	1
	2
	3
	4

б)

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 , необходимо и достаточно доказать невыполнимость следующего множества дизъюнктов:

.

a b d ( ) ( ) c ( ) ( ) ( ) ( ) Пустой дизъюнкт ( )

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 :

, .

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

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

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

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

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