IX.- законы де Моргана.

VIII.- законы дистрибутивности (распределительности).

VII.- законы ассоциативности (сочетательности).

Равносильности I—III выражают в математико-логической форме основные законы формальной логики, сформулированные Аристотелем.

Закон тождества утверждает, что мысль, заключенная в неко­тором высказывании, остается (считается) неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия гово­рит о том, что никакое предложение не может быть истинным одновременно со своим отрицанием. Утверждать, что какое-либо высказывание истинно вместе с его отрицанием, значит утверждать заведомую ложь. Так, например, предложения x=y и x≠y не могут быть истинными одновременно, т.е. при одних и тех же значениях переменных x и y. Если мы знаем, что в предложениях «Эта функция - периодическая» и «Эта функция – непериодическая» речь идет об одной и той же функции и пер­вое предложение истинно, то, согласно закону противоречия, второе предложение ложно.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание истинно или ложно; третьего не дано.

Согласно закону двойного отрицания, от­рицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание. Например, высказы­вание «Неверно, что 2·2≠4» означает то же, что и «2X2=4».

Законы коммутативности и ассоциативности конъюнкции и дизъюнкции аналогичны од­ноименным законам умножения и сложения чисел. Иног­да дизъюнкцию таки называют логическим сложением, а конъюнкцию — логическим умножением. Имея в виду законы ассоциативности, будем иногда опускать скобки в формулах вида (X/\Y)/\Z, X/\(Y/\Z), (X\/Y)\/Z, X\/(Y\/Z). В отличие от сложения и умножения чисел логические сложение и умножение равноправны по от­ношению к дистрибутивности: не только конъюнкция ди­стрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

B силу законов идемпотентности в алгебре логики нет «показателей степеней» и «коэффициентов»; конъюнкция одинаковых «сомножителей» равно­сильна одному из них; дизъюнкции одинаковых «слагае­мых» равносильна одному из них.

Смысл законов де Моргана можно выразить в кратких словесных формулировках: отрицание конъ­юнкции равносильно дизъюнкции отрицаний; отрицание дизъюнкции равносильно конъюнкции отрицаний.

3. Равносильные преобразования. Упрощение фор­мул. Если в равносильные формулы всюду вместо ка­кой-нибудь переменной подставить одну и ту же формулу, то вновь полученные формулы также окажутся равносильными (почему?). Таким способом из каждой равно­сильности можно получить сколько угодно новых равно­сильностей. Например, если в равносильность подставить вместо X и вместо Y, то получим новую равносильность: . Если какую-нибудь формулу F₁ являющуюся частью формулы F, заменить формулой F₂, равносильной F₁, то полученная формула окажется равносильной F (почему?). На этом основании имеем:

(по закону двойного отрицания);

(по закону де Моргана);

(по закону двойного отрицания);

(по закону ассоциативности);

(по закону идемпотентности).

Транзитивность отношения равносильности позволя­ет объединить первое и последнее звенья цепочки этих рассуждений в виде равносильности . Замену формулы другой, ей равносильной, будем называть равносильным преобразованием данной формулы. Под упрощением формулы, не содержащей знаков → и ↔, условимся понимать равносильное преобразование, приводящее к формуле, которая не содержит отрицаний неэлементарных формул (в частности, двойных отрица­ний) или содержит в совокупности меньшее число знаков \/ и /\, чем исходная.

К перечисленным законам логики добавим еще не­сколько равносильностей, часто используемых при упро­щении формул:

X.

XI.