Логические и арифметические основы и принципы работы ЭВМ

Функция конъюнкции истинна тогда, когда истинны одновременно оба высказывания.

Дизъюнкция

Это сложное высказывание истинно тогда, когда истинно хотя бы одно высказывание, входящее в него.

Читается X1 ИЛИ X2: Некоторое отличие от смысла союза «или», принятого в русском языке: в данном случае этот союз употребляется в смысле объединения, а не разъединения.

Логическая равнозначность

Это сложное высказывание истинно тогда, когда истинны или ложны одновременно оба высказывания.

Отсюда следует, что вне зависимости от смысла, равнозначными являются как истинные, так и ложные высказывания.

Например,

А=<дважды два - пять>

B=<один плюс два - шесть>

А~В равнозначны.

Импликация

Это сложное высказывание ложно только тогда, когда X1 – истинно, а X2 – ложно.

Читается: если X1, то X2. При этом X1 – посылка, X2 – следствие.

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

Но в действительности, все верно, т.к. содержанием высказываний в алгебре логики не интересуются.

Тогда из ложной посылки может следовать ложное следствие и это можно считать верным:

<если Киев – столица Франции>,

то <2-квадрат 3>.

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

В некоторых случаях сложное и длинное высказывание можно записать более коротким и простым без нарушения истинности исходного высказывания. Это можно выполнить с использованием некоторых эквивалентных соотношений.

Дизъюнкция:

х х х х... х х х= х,

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

x v x = 1

1 x = 1

– постоянно истинное высказывание.

0 x = x

x1 x2 = x2 x1

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

x1 х2 х3 = (x1 х2) х3 = x1 (х2 х3)

- сочетательный закон.

Конъюнкция:

х х х х... х х х= х

правило приведения подобных членов:

1 x = х

0 x = 0 - постоянно ложное высказывание

x x = 0 - постоянно ложное высказывание

Сложение по mod 2

1 х = x

0 x = x

x x = 1

x x x ... x = х – при нечетном числе членов, 0 - при четном числе членов

Правило де Моргана

x1 x2 ... xn = x1 & x2&... & xn

x1 x2 ... xn = x1 & x2 &... & xn

Докажем для двух переменных с помощью таблицы истинности:

Х1	Х2	Х1 Х2	X1 & X2

Операция поглощения:

Х XY = X или в общем виде X X*f(X,Y,Z...) = X;

Операция полного склеивания:

XY XY = X (по Y)

XY XY = Y (по Х)

Операция неполного склеивания:

XY XY = Х XY XY

Введем понятие степени:

Х

=Х, если =1;

=Х, если =0.

Рассмотрим конъюнкцию вида:

Х1 1 * Х2 2 * Х3 3... Хn n

Существует 2n наборов вида < 1, 2,... n >. Поставим в соответствие каждой конъюнкции (*) номер набора i и образуем дизъюнкцию всех конъюнкций:

i A(Х1 1 * Х2 2 * Х3 3... Хn n)

Теорема (без доказательства):

Любая ФАЛ, зависящая от 'n' аргументов, может быть представлена в форме:

F(Х1, Х2,... Хi... Хn)= Х1 1 * Х2 2... Хi i F( 1, 2,... i, Xi+1,...Xn)

Из этой теоремы вытекает ряд важных следствий:

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

2. Устанавливает так называемую функциональную полноту связок (базиса) " , , -", т.к. позволит построить в этом базисе произвольную ФАЛ от произвольного числа аргументов.

Примечание:

1. Если i n, то соответствующая форма функции называется дизъюнктивной нормальной (ДНФ).

2. Если i=n, то каноническая форма функции носит название совершенной ДНФ (СДНФ). Дизъюнкции берутся по тем наборам, на которых функция f(X1,X2,...,Xn)=1

Пример: ДНФ

f(Х1, Х2, Х3)= Х1 Х2 Х3 Х1Х2 Х3

Пример: СДНФ

f(Х1, Х2, Х3)= Х1Х2 Х3 Х1Х2 Х3

В ДНФ в каждый член любая переменная входит в прямом виде или с отрицанием.

Аналогичная теорема справедлива и для представления функции в конъюктивной нормальной форме (КНФ):

f(Х1, Х2,..., Хn)=&(Х1 1 Х2 2 ... Хi i) f( 1, 2,... i, Xi+1...Xn)

или при представлении в совершенной КНФ (СКНФ):

f(Х1, Х2,…, Хn)=&(Х1 1 Х2 2 Х3 3 ... Хn n)

где: & означает, что конъюнкции берется по тем наборам, на которых

f(Х1, Х2,... Хn)=0.

Дадим на основании этих теорем правило перехода от табличной формы функции к СДНФ и СКНФ.

Переход от табличной формы функции к СДНФ или правило записи функции по единицам:

1. Выбрать те наборы аргументов, на которых f(Х1, Х2,... Хn)=1.

2. Выписать все конъюнкции для этих наборов. Если при этом Хi имеет значение '1', то этот множитель пишется в прямом виде, если '0', то с отрицанием.

3. Все конъюнктивные члены соединить знаком дизъюнкции .

Пример:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2

Правило перехода от табличной формы задания функции к СКНФ или правило записи функции по нулям.

1. Выбрать те наборы аргументов, на которых f(Х1, Х2,... Хn)=0.

2. Если при этом Хi имеет значение '0', то остается без изменений. Если '1', то с отрицанием.

3. Все дизъюнктивные члены соединить знаком конъюнкции .

Пример:

f(Х1, Х2)= (Х1 Х2) (Х1 Х2)

Пример:

СДНФ f(Х1, Х2, Х3)= Х1Х2Х3 Х1Х2Х3 Х1Х2Х3 Х1Х2Х3 Х1Х2Х3

СКНФ f(Х1, Х2, Х3)= (Х1 Х2 Х3) & (Х1 Х2 Х3) & (Х1 Х2 Х3)

Рассмотрим способ получения СДНФ из СКНФ и обратно.

Из таблицы 2.1 с помощью способа записи функции по нулям следует, что СКНФ той же функции дизъюнкции будет иметь вид:

f(Х1, Х2)= Х1 Х2

Итак, имеем две формы одной и той же функции:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2 =Х1 Х2

Итак, видно, что общее число членов в этих двух формах равно сумме нулей и единиц функции, то есть равно 2n.

Если в исходной форме функции, записанной в СКНФ или СДНФ, содержится z членов, то в другой ее форме (т.е. СДНФ или СКНФ) их будет (2n- z).

Поскольку в функцию мы включаем дизъюнктивные или конъюнктивные члены и берем их по наборам, на которых функция или обращается в '0', или в '1', то для перехода от одной формы задания функции к другой нужно выписать все недостающие члены и поставить над каждой переменной отрицание, а также заменить знаки конъюнкции на дизъюнкцию и обратно.

f(Х1, Х2)= Х1 Х2

f(Х1, Х2)СДНФ= Х1Х2 Х1Х2 Х1Х2

т.е. получили СДНФ.

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