26. Основные логические законы. Логические тождества.

ОБЩИЙ ПРИНЦИП: Пусть два выражения составлены из переменных и логических связок принимают одинаковые значения, если любым способом заменить переменные нулями или единицами, тогда, если в этих выражениях переменные любым способом заменить высказываниями, то получится два эквивалентных высказываний.

Основные Булевские тождества:

а  а = а а  в = в  а

а  (в  с) = (а  в)  с

а V а = а а V в = в V а

а V (в V с) = (а V в) V с

а  (в V с) = (а  в) V (а  с)

а V (в  с) = (а V в)  (а V с)

 а = а

закон Де Моргана:

 (а  в) = ( а) V ( в)

 (а V в) = ( а)  ( в)

а  ( а) = 0 а V ( а) = 1

а  1 = а а V 0 = а

ав =  а V в

а  в = (ав)  (ва)

ав = (в)(а)

докажем одно из этих тождеств:

 (а  в) = (а) V (в)

а	в	а  в	 (а  в)	а	в	(а) V (в)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Доказательство от противного:

а	в	а  в	а	в	(в)  (а)
0	0	1	1	1	1
0	1	1	1	0	1
1	0	0	0	1	0
1	1	1	0	0	1

27. Правила обращения с кванторами.

Имеется два квантора: квантор существования - 

квантор общности - 

Если Р(х) - некоторая высказанная форма с единственной свободной переменной Х, то возможно построение высказываний с ограниченными кванторами и неограниченными. Неограниченный квантор имеет вид:  х Р(х),  х Р(х). Ограниченные кванторы предполагают наличие ограничений на свободную переменную:  хS Р(х),  хS Р(х).

При работе с кванторами также выполняются законы Де моргана:

 (_x Р(х)) = _x Р(х)

 (_x Р(х)) = _x Р(х)

Пример: Записать не используя знаков отрицания, то что функция f(x) разрывна в точке Х₀

(_{ 0} _{ 0} х х-х₀  f(x)-f(x₀) )

применяется закон Де Моргана:

_{ 0} _{ 0} х  (х-х₀  f(x)-f(x₀) )

(ав)=(аVв)=а(в)

_{ 0} _{ 0} х х-х₀  f(x)-f(x₀) 