Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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

⇐ ПредыдущаяСтр 9 из 32Следующая ⇒

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

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

Например,

А=<дважды два - пять>B=<один плюс два - шесть>А~В равнозначны.

Импликация

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

X1 X2 f1(X1,X2)
     
     
     
     

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

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

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

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

<если Киев – столица Франции>,то <2-квадрат 3>.

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

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

Дизъюнкция:

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

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

x v x = 11 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 х = x0 x = xx 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
3. Лекция: Совершенные дизъюнктивные и конъюнктивные нормальные формы ФАЛ
Страницы: 1 | 2 | 3 | вопросы |» | учебники | для печати и PDA | ZIP
Если Вы заметили ошибку - сообщите нам, или выделите ее и нажмите Ctrl+Enter
В лекции дано определение совершенной дизъюнктивной и конъюнктивной нормальных форм. Представлены правила записи функции по нулям и единицам. Дано понятие функциональной полноты, поставлена задача минимизации функции. Сформулирована теорема Квайна.

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

 

Х

=Х, если =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

X1 Х2 f(Х1, Х2)
     
     
     
     

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

  1. Выбрать те наборы аргументов, на которых f(Х1, Х2,... Хn)=0.
  2. Если при этом Хi имеет значение '0', то остается без изменений. Если '1', то с отрицанием.
  3. Все дизъюнктивные члены соединить знаком конъюнкции .

Пример:

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

X1 Х2 f(Х1, Х2)
     
     
     
     

Пример:

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

СДНФ 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

X1 Х2 f(Х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

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

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

 


⇐ Предыдущая45678910111213Следующая ⇒





Date: 2016-05-14; view: 555; Нарушение авторских прав


mydocx.ru - 2015-2025 year. (0.021 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию