Файл: Логика высказываний 1.pdf

19 

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

Рассмотрим  произвольный  набор  констант 

1

2

,  

,

,  

n

 



  и 

покажем, что на нём левая и правая части равенства (*) совпадают. Левая часть 
равна 





1

2

,  

,

,  

n

f

 



, а правая  









1

1

1

1

1

, , 

,

,  

,

,

,  

m

m

m

m

m

n

f















 













, по свойству 

x



 отличной от 

нуля будет только одна конъюнкция 

1

1

1

m

m















, а при всех других набо-

рах констант 





1

, , 

m





1

1

0

m

m















. Тогда по теоремам логики высказыва-

ний 













1

1

1

1

1

1

1

, , 

,

,  

,

,

,  

,

,  

,

,

,  

m

m

m

m

m

n

m

m

n

f

f















 





 

















. 

Что и требовалось доказать. 
 

20 

21 

Покажем, что для функции 

0

f



  существует  представление  в  виде  «со-

вершенной  конъюнктивной  нормальной  формы»  (СКНФ).  В  этих  условиях 

*

0

f



, поэтому для неё существует СДНФ 

22 

Упражнение1.6.1.

  Построить  СДНФ  и  СКНФ  для  функций,  заданных 

следующими формулами. 
а)  

б) 

в)