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₀) 

28. Техника доказательств.

f:RR f(x)=2x

пример 1: доказать, что _х,уR f(x+y)=f(x)+f(y)

доказательство: возьмем любые два вещественных числа х и у, тогда

f(x+y)=f(x)+f(y)

пример 2: доказать единственность нейтрального элемента в группе А по умножению (А*х). Предположим, что имеется два различных нейтральных элемента, левосторонний e и правосторонний e’, т.е. :

х ех=х (1)

х е’х=х (2)

Поскольку формула (1) справедлива для любого х, то возьмём в качестве х значение е’ (х=е’), получим ее’=е’. Поскольку формула (2) справедлива для любого х, то возьмём х равный е, получим ее’=е

теорема: существуют два иррациональных числа а и в, такие что а^в является рациональным числом.

Доказательство: а=в=с=- может быть либо рациональным, либо иррациональным. Если с – рационально то теорема доказана. Если с – иррационально, о возьмём в качестве а=, в=, огда а^в=. Теорема доказана.