Закон тождества; в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

Закон непротиворечия: невозможно, чтобы одно и то же в одно то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утвер­ждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

Последний закон говорит о том, что доказательство чего-либо предпо­лагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «Ошибаться свойствен­но всякому человеку, но настаивать на ошибке свойственно только глуп­цу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли мо­гут быть использованы истинные суждения, фактический материал, стати­стические данные, законы науки, аксиомы, доказанные теоремы.

Законы алгебры высказываний

Алгебра высказываний (алгебра логики) — раздел математической логики, изучающий логические операции над высказываниями и правила преобразования сложных высказываний.

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

В алгебре высказываний логические законы выражаются в виде ра­венства эквивалентных формул.

Среди законов особо выделяются такие, которые содержат одну пе­ременную.

Первые четыре из приведенных ниже законов являются основными законами алгебры высказываний.

Закон тождества: , ,, .. , , ,

А=А. Всякое понятие и суждение тождественно самому себе. '^Sf^'

Закон тождества означает, что в процессе рассуждения нельзя подме­нять одну мысль другой, одно понятие другим. При нарушении этого за­кона возможны логические ошибки.

Например, рассуждение Правильно говорят, что язык до Киева до­ведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.

Врассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемеще­нию в пространстве), что приводит к ложному выводу.

Часть 1. Элементмматематуи^кой логики

Глава 6. Законы логики

Закон щпротиворечия: ,

л&1 = 1. ; ^:"^>!; "

Не могут быть одновременно истинными суждение и его отрицание. То есть если высказывание А — истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным:

А& А=0.

Именно это равенство часто используется при упрощении сложных логических выражений.

Иногда этот закон формулируется так: два противоречащих друг дру­гу высказывания не могут быть одновременно истинными.

-> Примеры невыполнения закона непротиворечия:

1. На Марсе есть жизнь и на Марсе жизни нет.

2. Оля окончила среднюю школу и учится в Xклассе.

Закон исключенного третьего:

AvA=l.

В один и тот же момент времени высказывание может быть либо ис­тинным, либо ложным, третьего не дано. Истинно либо А, либо не А.

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

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо — либо», «истина — ложь». Там же, где встречается неопределенность (на­пример, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.

Рассмотрим следующее высказывание: Это предложение ложно.

Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нару­шается закон исключенного третьего.

Парадокс (греч. paradoxos — неожиданный, странный) в этом при­мере возникает из-за того, что предложение ссылается само на себя.

Другим известным парадоксом является задача о парикмахере:

В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?

В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтвер­ждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы.

Покажем, как на основании определения эквивалентности высказы­ваний могут быть получены остальные законы алгебры высказываний.

Например, определим, чему эквивалентно (равносильно) А (двой­
ное отрицание А, т. е. отрицание отрицания А). Для этого построим таб­
лицу истинности: ,,-!,„

А	А	А

5 ' ч >4S' »L

По определению равносильности мы должны найти тот столбец, зна­
чения которого совпадают со значениями столбца А ■ Таковым является
столбец А. Таким образом, мы можем сформулировать закон двойного
отрицания:' ^а*' ■' -'''- ''

А = А.

Если отрицать дважды некоторое, высказывание, то в результате по­лучается исходное высказывание. J

Часть 1. Элементы математической логики

Глава 6. Законы логики

Например, высказывание А = Матроскин — кот эквивалентно выс­казыванию А = Неверно, что Матроскин не кот.

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удоб­нее всего провести с помощью таблицы истинности:

	0=1		1 = 0
	(отрицание лжи ■' •	•	(отрицание истины
,.\ '	есть истина);	, * ,	есть ложь);
V	А\>0=А;	. .* '* ',	А & 0 = 0;
	Avl = l;		Л&1=Л.
Законы идемпотентности: " 'tf.-'t,,'. ' V.lj		• 1' >
•-Я. -	AvA=A	( '* 4i *.	А&А=А
	(отсутствие		(отсутствие
	коэффициентов);		степеней).

Сколько бы раз мы ни повторяли: телевизор включен или телевизор включен или телевизор включен ... значение высказывания не изменится.

Аналогично от повторения на улице тепло, на улице тепло,... ни на один градус теплее не станет.

А	В	с	в&с (2)&(3)	Av(B8cQ (l)v(4)	AvB (l)v(2)	AvC (l)v(3)	(AvB)& &(AvQ (6)&(7)	Av(B&Q^ &(AvB)& &(AvQ (5)<=*8)

■а ''"!. ч-' ■	м к ■:<•■.<
ait. ,i '<-'- -••	■о,п.
	„ У
А&.В = A v В

Законы коммутативности: AvB=BvA;

A&B = BfrA.

Операнды А и В в операциях дизвфгсции и конъюнкции можно ме­
нять ме стами. • «4

'...гл.

Законы ассоциативности:

•п A v (В v С)= (A v В) v С; А &(В & С)= (А& В)& С.

Если в выражении используется только операция дизъюнкции или
только операция конъюнкции, то можно пренебрегать скобками или про­
извольно их расставлять. . ,' (.,.,• , ,_{/tii >;}

Законы поглощения: .

A v (A & B)= A\ »fc «K A & (A v B) = A. ?•

\ I !■

Проведите доказательство законов поглощения самостоятельно. Законы де Моргана:

Aw В = А& В..,.,.

(отрицание вариантов вместе), . , (отрицание одновременной

истинности).

Законы дистрибутивности:

Av(B&Q = (AvB)&(AvQ

(дистрибутивность дизъюнкции относительно конъюнкции);

A&(BvQ = (A&B)v(A&Q

(дистрибутивность конъюнкции относительно дизъюнкции).

Словесные формулировки законов де Моргана:

	-Г
^ дизъюнкции конъюнкция Отрицание--------------- есть--------------- отрицании. конъюнкции дизъюнкция

Часть 1. Элементы математической логики

Глава 6. Законы логики

_. или

Отрицание истинности А В тождественно тому,

и

i ^и

что неверно А неверно В.

__________________ или__________

Мнемоническое правило:в левой части тождества операция от­рицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказыва­ний, но одновременно меняется операция: дизъюнкция на конъюнк­цию и наоборот.

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю ки­тайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двой­ку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

>.< .-1. . /ияГ

Замена операций импликации • . ,

и эквивалентности

Операций импликации и эквивалентности иногда нет среди логичес­ких операций конкретного компьютера или транслятора с языка програм­мирования. Однако для решения многих задач эти операции необходимы. Существуют правила замены данных операций на последовательности операций отрицания, дизъюнкции и конъюнкции.

Так, заменить операцию импликации можно в соответствии со следу­ющим правилом:

А=>В= A vB.
Для замены операции эквивалентности существует два правила:
At=>B = (A&B)v(A & В);
-.l.. Ae>B = (Av B)&(AvB).

В справедливости данных формул легко убедиться, построив табли­цы истинности для правой и левой частей обоих тождеств.

; Знание правил замены операций импликации и эквивалентности по­могает, например, правильно построить отрицание импликации.

!

¹ <

Рассмотрим следующий пример. Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получущшз.. _t '

] Пусть А= Я выиграю конкурс, В = Я получу приз.

\

Тогда I

; E = A=*B=AvB=A&B=A&B,

т. е. Е = Я выиграю конкурс, но приз не получу.

,-! •' -\Г

Интерес представляют и следующие правила:

Г , А =*£= В => А ; j

■ я

• .!.W А^В = (А=$В)&(В=>А). ' ~' "^ч "' ' ' i

Доказать их справедливость можно также с помощью таблиц истин­ности.

i Интересно их выражение в естественном языке. «■ Например, фраза

Если Винни-Пух съел мед, то он сыт

тождественна фразе

Если Винни-Пух не сыт, то меда он не ел. ,

! i

| Учащиеся, как правило, с удовольствием придумывают фразы-гцяй
|меры на данные правила. \

Часть 1. Элементы математической-логики

Глава 6. Законы логики

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Основные законы логики

А=А —закон тождества; •■ "'••-'» ;

А & А = 0 —вторая форма закона непротиворечия; ' ^,i(i'' ' • A v А = 1 — закон исключенного третьего;

А = А — закон двойного отрицания. ' '

» Свойства констант

,, '-к.,-, 0 = 1; "■ •- ' Т=0;

г-., ■- .-, Л vO = /l; ,_ч .. Л&0 = 0;

.......... Л v 1 = 1; ¹" ^> ' ' -■'•• А&\=А.

Законы идемпотентности

AvA=A; - А &А=А.

Законы коммутативности

^vfi=5vi; .,,,, , _; А&В = В&А.

Законы ассоциативности

Av(BvQ = (AvB)vC; А & {В & Q = (А & В) & С. '" |

Законы дистрибутивности

Av(B&Q = (AvB)&(AvC); A &(B v Q = (А &B)v (A &C).

Законы поглощения

Av(A&B)=A; A&(AvB)=A.

Законы де Моргана

AvB = A&B; A&B~AvB j <: