20.Докажем по таблице истинности:

А	В	А=>B	Не А	Не В	НеВ=>НеА
и	и	и	л	л	и
и	л	л	л	и	л
л	и	и	и	л	и
л	л	и	и	и	и

Замечание. Любая теорема устроена, как некоторая импликация, тогда в силу в силу св-ва 2⁰ любая теорема равносильна обратной противоположной (или противоположной обратной), а в силу св-ва 3⁰, обратная теорема равносильна противоположной теореме. Поэтому, из четырех теорем достаточно док-ть две (не любые).

Эквиваленцией (БАО) выск-ий А и В наз-ся выск-ие АВ(равносильно; если и только если) с таблицей истинности:

А	В	А<=>B
и	и	и
и	л	л
л	и	л
л	л	и

Теорема о св-вах эквиваленции:ВСЕГДА

1⁰.AB=BA 2⁰.(AB)C=A(BC)

3⁰.AA=^?Аи (нет идемпотентности)

4⁰.Aи=^?А(и – нейтр эл-т) Aл=^?А неА

5⁰.Нет поглощающего эл-та (см. 4⁰)

6⁰.AВ=(А=>B)^(B=>A) – смысл  Док-во:

1⁰, 2⁰ при помощи таблицы:

А	В	С	(AB)	BA	(AB)C	(BC)	A(BC)
и	и	и	и	и	и	и	и
и	и	л	и	и	л	л	л
и	л	и	л	л	л	л	л
л	и	и	л	л	л	и	л
л	л	л	и	и	л	и	л
л	л	и	и	и	и	л	и
л	и	л	л	л	и	л	и
и	л	л	л	л	и	и	и

3⁰, 4⁰ и 5⁰:

А	АA	Aи	Aл
и	и	и	л
л	и	л	и

6⁰:

А	В	AB	A=>B	B=>A	(A=>B)^(B=>A)
и	и	и	и	и	и
и	л	л	л	и	л
л	и	л	и	л	л
л	л	и	и	и	и

№2 Операции над высказываниями. Свойства.

Дизъюнкцией (БАО) высказываний А и В (напомним, что высказывание А - это предложение, относительно которого можно установить истинность или ложность) называется высказывание вида АvВ (или) с таблицей истинности:

	А			В			АvВ
	и			и			и
	и			л
	л			и
	л			л			л

А	В	АvВ
и	и	и
и	л	л
л	и
л	л

Конъюнкцией (БАО) высказываний А и В называется высказывание вида А^В (и) с таблицей истинности:

Свойства диз-ции и кон-ции. Теорем а об их св-вах: Они обе:

1⁰.Коммутативны 2⁰.Ассоциативны

3⁰.Идемпотентны 4⁰.Имеют нейтральные эл-ты, но разные:

Для диз-ции – «л», для кон-ции – «и»

5⁰.Поглощающие эл-ты:

Для диз-ции – «и», для кон-ции – «л». Всегда: Аvи=и; А^л=л.

6⁰.Они дистрибутивны, одна относительно другой:

(AvB)^C=(A^C)v(B^C), (A^B)vC=(AvC)^(BvC)

7⁰.Законы поглощения: (АvB)^A=A; (A^B)vA=A.

Док-во:

1⁰,3⁰,4⁰,5⁰ – докажем при помощи таблицы истинности.

Докажем сначала 3⁰,4⁰,5⁰:

А	AvA	A^A	Avи	Avл	А^и	A^л
и	и	и	и	и	и	л
л	л	л	и	л	л	л

*

Два высказ-ния наз-ся равными, если у них одинаковые таблицы истинности.

Видим, что: AVA=A (3⁰ для V) A^A=A (3⁰ для ^)

AVл=A (л – нейтральный эл-т V, 4⁰) A^и=A (и – нейтральный эл-т ^, 4⁰)

AVи=A (5⁰ для V, и – поглощ. эл-т) A^л=A (5⁰ для ^, л – поглощ. эл-т)

Док-во 1⁰:

А	В	AvB	BvA	A^B	B^A
и	и	и	и	и	и
и	л	и	и	л	л
л	и	и	и	л	л
л	л	л	л	л	л

Док-во 2⁰: (AvB)vC=Av(BvC); (A^B)^C=A^(B^C)

А	В	С	(AvB)	(AvB)vC	(BvC)	Av(BvC)	(A^B)	(A^B)^C	(B^C)	A^(B^C)
и	и	и	и	и	и	и	и	и	и	и
и	и	л	и	и	и	и	и	л	л	л
и	л	и	и	и	и	и	л	л	л	л
л	и	и	и	и	и	и	л	л	и	л
л	л	л	л	л	л	л	л	л	л	л
л	л	и	л	и	и	и	л	л	л	л
л	и	л	и	и	и	и	л	л	л	л
и	л	л	и	и	л	и	л	л	л	л

Док-во 6⁰: (AvB)^C=(A^C)v(B^C)-кон-ция относит диз-ции, (A^B)vC=(AvC)^(BvC) докажем иначе.

Первое из них: Пусть С равно «и». Тогда л.ч.= (ля-ля и истина равно ля-ля) AvB; п.ч.=(A^и)v(B^и)=AvB(т.к. и – нейтр эл-т) = л.ч.

Если же С=л, то л.ч.= (AvB)^л=(5⁰)л; п.ч.= (A^л)v(B^л)= (5⁰)лvл=л=л.ч.

Видим, что л.ч. всегда равна п.ч.

Второе рав-во (A^B)vC=(AvC)^(BvC):

Пусть С равно «и». Тогда л.ч.= (ля-ля или истина равно истине) «и»; п.ч.=(Avи)^(Bvи)=и^и(т.к. и – погл эл-т) = и =л.ч.

Если же С=л, то л.ч.= (A^B)vл =(4⁰)л; п.ч.= (Avл)^(Bvл)= (4⁰)л^л=л=л.ч.

Видим, что л.ч. всегда равна п.ч.

Докажем второе равенство и при помощи таблицы истинности:

А	В	С	(A^B)	(A^B)vC	(AvC)	(BvC)	п.ч.
и	и	и	и	и	и	и	и
и	и	л	и	и	и	и	и
и	л	и	л	и	и	и	и
л	и	и	л	и	и	и	и
л	л	л	л	л	л	л	л
л	л	и	л	и	и	и	и
л	и	л	л	л	л	и	л
и	л	л	л	л	и	л	л

7⁰ Законы поглощения (AvB)^A=A (A^B)vA=A

Разделительной дизъюнкцией (БАО или ля-ля, или тру-ля-ля) выск-ий А и В называется выск-ние А◊В (или, или) с таблицей истинности:

А	В	А◊В
и	и	л
и	л	и
л	и	и
л	л	л

Теорема о св-вах: ВСЕГДА

1⁰.Коммутативна 2⁰.Неассоциативна 3⁰.Неидемпотентна

Док-во:

1⁰.Видно по таблице истинности

2⁰.Докажем, что неассоциативна (А◊В) ◊С=А◊ (В◊С)

Возьмем (А,В,С)=(и,и,л), тогда л.ч.=л, а п.ч.=и

(Возьмем (А,В,С)=(и,и,и), тогда л.ч.=и, п.ч.=и)

3⁰.Т.к. А◊А=не А

Отрицанием высказывания (УАО) наз-ся высказывание не А с таблицей истинности:

А	Не А
и	л
л	и

ВСЕГДА:

1⁰.Не не А = А (инволютивность)

Не не A (Двойное отрицание - отрицание отрицания)

2⁰.Не АvВ(отрицание диз-ции)=не А^ не В(кон-ция отрицаний)

3⁰.Не A^В=не Аv не В

4⁰.Обобщенные законы де Моргана Док-во: 1⁰.

А	Не А	Не не А
и	л	и
л	и	л

2⁰.П.ч.=и(редкое значение для д-ции) iff неА=и, неВ=и iff А=л, В=л, iff AvB=л, iff не AvB=и.

3⁰.Не A^В=не Аv не В

А	В	А^B	Не А^B	Не А	Не В	не Аv не В
и	и	и	л	л	л	л
и	л	л	и	л	и	и
л	и	л	и	и	л	и
л	л	л	и	и	и	и

4⁰.Докажем, что * :

Попробуем воспользоваться ранее использованными св-ми:

*

(скобки убирать нельзя)

Штрихом Шеффера (≈1900) высказываний А и В называется высказывание А|В с таблицей истинности:

А	В	А|B
и	и	л
и	л	и
л	и	и
л	л	и

Теорема о св-вах ШШ: ВСЕГДА

1⁰.A|B=B|A – коммутативность 2⁰.(A|B)|C=^?A|(B|C) – неассоц.

3⁰.A|A=^?A не А 4⁰.A|и=^?A не А A|л=^?A и

5⁰.Нет погл. эл-та, нет нейтр эл-та Док-во:

Можно понять, что ШШ – это отрицание конъюнкции, т.е. всегда:

0⁰. A|B=Не A^B

1⁰,3⁰,4⁰,5⁰:

А	В	A|B	B|A	A|A	A|и	A|л
и	и	л	л	л	л	и
и	л	и	и	л	л	и
л	и	и	и	и	и	и
л	л	и	и	и	и	и

Видим, что A|A=не А. Заносим в теорему: A|и=не А; А|л=и, т.е. А|л – тавтология.

2⁰:Ассоциативен ли ШШ? (A|B)|C=^?A|(B|C)

Возьмем (А,В,С)=(и,л,л), тогда л.ч.=и, а п.ч.=л

(Возьмем (А,В,С)=(и,и,л), тогда л.ч.=л; п.ч.=л)

Стрелкой Пирса (≈1900) выск-ий А и В наз-ся выск вида А↓В с табл ист-ти:

А	В	А↓B
и	и	л
и	л	л
л	и	л
л	л	и

Теорема о св-вах:

1⁰.A↓В=В↓А – коммут. 2⁰.(A↓В)↓С=А↓(В↓С) – неассоц.

3⁰.А↓А не равно А – неидемпот. 4⁰.А↓и=л – нет нейтр.эл-та

5⁰.Нет поглощ эл-та Док-во:

1⁰,3⁰ - Видно по таблице

2⁰ - Возьмем (А,В,С)=(и,и,л), тогда л.ч.=и, а п.ч.=л

(Возьмем (А,В,С)=(л,и,л), тогда л.ч.=и, п.ч.=и)

0⁰.Видим, что: А↓В=не AvB. А как это озвучивать? А вот так: А↓В=не AvB=неА^не В=>А↓В озвучивается, как: «ни то, ни сё».