Билет 16 закон двойного отрицания

Этим именем называется закон логики, позволяющий отбрасывать двойное отрицание. Этот закон можно сформулировать так: отрицание отрицания даёт утверждение, или: повторенное дважды отрицание даёт утверждение. Например: «Если неверно, что Вселенная не является бесконечной, то она бесконечна».

Закон двойного отрицания был известен ещё в античности. В частности, древнегреческие философы Зенон Элейский и Горгий излагали его следующим образом: если из отрицания какого-либо высказывания следует противоречие, то имеет место двойное отрицание исходного высказывания, то есть оно само.

В символической форме закон записывается так:

~~ А -> А,

если неверно, что не-А, то верно А.

Другой закон логики, говорящий о возможности не снимать, а вводить два отрицания, принято называть обратным законом двойного отрицания: утверждение влечёт своё двойное отрицание. Например: «Если Шекспир писал сонеты, то неверно, что он не писал сонеты».

Символически:

A -> ~~ A

если А, то неверно что не—А.

Объединение этих законов даёт так называемый полный закон двойного отрицания:

~~ А <-> А,

неверно, что не-А, если и только если верно А.

4. Сочетательный закон.

   

    (а + в) + с = а + (в + с);                                 (а·в) ·с = а· (в·с)

 

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

 

Распределительный закон записывается в виде:

а) для дизъюнкции

(3.5)

т. е. дизъюнкция переменной и конъюнкции равносильна конъюнкции дизъюнкций этой переменной с сомножителями;

б) для конъюнкции

(3.6)

т. е. конъюнкция переменной и дизъюнкции эквивалентна дизъюнкции конъюнкций этой переменной со слагаемыми.

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

БИЛЕТ 17

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

а) для дизъюнкции

(3.1)

б) для конъюнкции

(3.2)

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

 

Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Открыты шотландским математиком Огастесом де Морганом

Обычная запись этих законов в формальной логике:

или

БИЛЕТ 18

Табличное представление значений ЛФ для всех наборов входных переменных называется   таблицей истинности. В общем виде переход от табличного представления к алгебраическому может осуществляться по формуле (12), одной из основных в алгебре логики.

Выражение (12) называется совершенной дизъюнктивной нормальной формой ЛФ (СДНФ). mi - минтерм или логическое произведение всех переменных i-го двоичного набора, входящих в прямом виде, если значение этой переменной в наборе равно 1, и  в инверсном виде, если ее значение равно 0. fi - значение ЛФ на i - ом наборе. Доказательство (12) базируется на теореме разложения, в соответствии с которой любую ЛФ f(..) от n-переменных можно разложить по переменной xi в виде: f(x(n-1),...,xi,. ..,x0)  = ~xi*f(x(n-1),...,0,..,x0) + xi*f(x(n-1),..,1,..,x0). Это выражение для xi=0 равно ~0*f(x(n-1),...,0,..,x0) + 0*f(x(n-1),..,1,..,x0) = f(x(n-1),...,0,..,x0). При xi=1 оно будет равно ~1*f(x(n-1),..,1,..,x0) + 1*f(x(n-1),..,1,..,x0) = f(x(n-1),...,1,..,x0), т.е. при любых значениях xi теорема разложения справедлива. Теорему разложения можно применить n раз и тогда ЛФ будет разложена по всем своим переменным.

В виде примера рассмотрим функцию F=f(x1,x0) от двух переменных. Разложение этой функции по переменной x1 даст: F= ~x1*f(0,x0) + x1*f(1,x0) . Продолжая эту операцию для переменной x0, получим:

F =~x1*(~x0*(f(0,0) + x0*(f(0,1)) + x1*(~x0*(f(1,0) + x0*(f(1,1)) = ~x1*~x0*f(0,0) + ~x1*x0*f(0,1) + x1*~x0*f(1,0) + x1*x0*f(1,1).                  (12.1)

Выражение (12.1) позволяет записать все переключательные функции от двух переменных, используя только три основных логических операции.

Рассмотрим разложение функций F7-"ИЛИ" и F1-"И", для чего необходимо обратиться к соответствующим строчкам таблицы 1. Функция И на двоичных наборах входных переменных x1 и x0 (00,01,10,11) принимает значения 0,0,0,1. Записывая выражение (12.1) для этих значений получим: F1(x1,x0 ) = ~x1*~x0*0 + ~x1*x0*0 + x1*~x0*0 + x1*x0*1 = x1*x0, что согласуется с ее определением. Таким же образом, находим алгебраическое выражение функции F7-"ИЛИ", которая, соответственно, на тех же входных наборах принимает значения: 0,1,1,1. Тогда, в соответствии с (12.1), F7(x1,x0) = ~x1*~x0*0 + ~x1*x0*1 + x1*~x0*1 + x1*x0*1. Вынося за скобки в двух последних слагаемых x1, получим F7 = ~x1*x0*1 + x1*(~x0*1 + x0*1). На основании аксиомы (8), выражение в скобке равно "1" и F7 = ~x1*x0*1 + x1. Применяя распределительный закон, найдем (~x1+x1) * (x0+x1) = x1+x0.

Возвращаясь к таблице 2, получим Y = 0*~x1*~x0 + 1*~x1*x0 + 1*x1*~x0 + 0*x1*x0 = ~x1*x0 + x1*~x0 = x1 (+) x0 = F6 (функция неравнозначности).

С помощью формулы (12) любую, сколь угодно сложную, логическую функцию можно представить в виде трех основных ЛФ: "И", "ИЛИ", "НЕ", представляющих собой логический базис.

БИЛЕТ 19