Правила для одной переменной.

1.АÙ 1=А; 2.АÙ 0=0; 3.АÙ А=А; 4.АÙ А^/=0; 5.АÚ 1=1; 6.АÚ 0=А; 7.АÚ A=A 8.AÚ A^/=1

9.A^//=A 10.A^///=A^/

(2.3)

Правила 1-10 доказываются простой подстановкой вместо А единицы и нуля. Как следствие из правил 3 и 7 имеем закон тавтологии:

 

(2.4)

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

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

(2.5)

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

(2.6)

Правила 11-14 определяют конъюнкцию и дизъюнкции в отдельности.

В силу справедливости для логического умножения и логического сложения сочетательного и переместительного законов выражения, в которые входят конъюнкция и дизъюнкция, можно писать без скобок. При этом связь посредством знака “Ù ” считают более тесной, чем посредством знака “Ú ”. Тем самым в алгебре логики устанавливается правило записи выражений, аналогичное принятому в обычной алгебре (в процессе вычислений “старшие” действия выполняются раньше “младших”). Это позволяет вместо (АÙ В)Ú С писать просто АÙ ВÚ С.

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

15. АÙ (ВÚ С)=(АÙ В)Ú (АÙ С) (2.7)

и распределительный закон дизъюнкции относительно конъюнкции:

16. АÚ (ВÙ С)=(АÚ В)Ù (АÚ С), (2.8)

который в обычной алгебре не имеет места. Действительно,

a+bc¹ (a+b)(a+c).

Отметим, что все три названных закона обладают “симметрией” в том смысле, что из любого закона для дизъюнкции (конъюнкции) можно получить путем замены знаков дизъюнкции на знаки конъюнкции соответствующий закон для конъюнкции (дизъюнкции) и наоборот. Действительно, проведя замену знаков, например в выражении (2.7), получим:

АÚ (ВÙ С)=(АÚ В)Ù (АÚ С).

Следующий закон, известный как закон двойственности, или закон инверсий, позволяет заменять отрицание конъюнкции дизъюнкцией отрицаний и отрицание дизъюнкции конъюнкцией отрицаний:

(2.9)

Если к выражениям (2.9) применить правило 9 (2.4), то получим:

(2.10)

Правила (2.10), названные в честь одного из основоположников математической логики формулами де Моргана, позволяют логическое умножение выразить через отрицание логической суммы из инверсных высказываний, а логическую сумму – через отрицание логического произведения из инверсных высказываний. Формулы (2.10) легко обобщаются на произвольное число логических переменных:

(2.11)

, (2.12)

где логические переменные обозначены буквой х с различными индексами i=1, 2,..., n, а знаки конъюнкции и дизъюнкции аналогичны знакам произведения и суммы в обычной алгебре.

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

Познакомимся прежде всего с операциями поглощения и склеивания.

Операция поглощения (absorption) определяется соотношениями:

(2.13)

Операция склеивания (merging) определяется соотношениями:

(2.14)

Упростим теперь выражение АÙ (А^/Ú В). На основании распределительного закона конъюнкции относительно дизъюнкции по правилу 15 имеем:

АÙ (А^/Ú В)=(АÙ А^/)Ú (АÙ В ).

По правилу 4 АÙ А^/=0, следовательно,

АÙ (А^/Ú В)=0Ú (АÙ В).

Используя правило 6, окончательно получаем:

25. АÙ (А^/Ú В)=АÙ В. (2.15)

На основании распределительного закона дизъюнкции относительно конъюнкции по правилу 16 имеем:

АÚ (А^/Ù В)=(АÚ А^/)Ù (АÚ В).

По правилу 8 АÚ А^/=1, следовательно,

АÚ (А^/Ù В)=1Ù (АÚ В).

Используя правило 1, окончательно получаем:

26. АÚ (А^/Ù В)=АÚ В. (2.16)

Операция обобщенного склеивания определяется соотношениями:

(2.17)

Доказательство (2.17) проводится в первом выражении путем логического умножения первого слагаемого на 1Ú С, а второго – на 1Ú А и последующего применения правил 15 и 23, во втором выражении - путем прибавления к первому сомножителю слагаемого 0Ù А, а ко второму - 0Ù С и применения правил 16 и 24.

Проиллюстрируем это доказательство в матричной форме записи для правила 27:

2.3. Основные определения и принятые обозначения

 

Введем в рассмотрение понятие степень аргумента х, которую будем обозначать , где - двоичная переменная величина. Положим, что

(2.18)

Условимся переменные х_i и их отрицания (i=1, 2,..., n) называть буквами, а i – номером или индексом переменной.

Определение 1. Выражение вида

(2.19)

называется элементарной конъюнкцией (К) ранга r. В силу того, что и все буквы элементарной конъюнкции различны.

Определение 2. Выражение вида

К₁Ú К₂Ú...Ú К_s, (2.20)

где K_i – элементарные конъюнкции различных рангов, называется дизъюнктивной нормальной формой (ДНФ). Например, функция:

записана в ДНФ, так как все три слагаемых являются элементарными конъюнкциями.

Определение 3. Если функция f(x₁,..., x_n) записана в ДНФ, причем ранг каждой элементарной конъюнкции равен n, то такая ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ), а конъюнкции членами СДНФ или конституентами единицы.

Определение 4. Выражение вида

(2.21)

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

Определение 5. Две элементарные конъюнкции называются ортогональными, если их произведение равно нулю. Например, произведение элементарных конъюнкций и равно нулю, так как одна из них содержит , а другая х₂ и, следовательно, они ортогональны.

Определение 6. ДНФ называется ортогональной дизъюнктивной нормальной формой (ОДНФ), если все ее члены попарно ортогональны.

В соответствии с этим определением СДНФ является ОДНФ, так как все ее члены попарно ортогональны. Но СДНФ является самой неэкономной из всех ОДНФ, так как она содержит максимальное число букв.

Определение 7. Бесповторной ДНФ (БДНФ) называется такая ДНФ, в которой все буквы имеют разные номера. Буквы х_i и имеют один и тот же номер, поэтому они не могут одновременно входить в БДНФ.

Определение 8. Бесповторной формой ФАЛ называется такая форма, в которой все буквы имеют разные номера. Частным случаем бесповторной формы ФАЛ является БДНФ. Например, функция:

записана в бесповторной форме, так как все буквы имеют разные номера.

Определение 9. Вероятностной функцией (ВФ) будем называть вероятность истинности ФАЛ

(2.22)

Определение 10. Функции алгебры логики, допускающие непосредственный переход к ВФ заменой логических переменных вероятностными, а логических операций соответствующими арифметическими операциями, будем называть формами перехода к замещению (ФПЗ).

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

Особенность СФФВ состоит в том, что в ней все зависимости от аргументов определены в явной форме, через используемые элементарные операции (логические и арифметические). Она не может содержать операторов типа , если не известно явное выражение таких функций в виде ВФ и СФФВ. Смешанная форма имеет простой вероятностный смысл. Если в функции f после замещения некоторых логических переменных остались незамещенными переменные вектора Х, то . Это выражение имеет смысл условной вероятности того, что , причем условия записаны с помощью незамещенных логических переменных. После задания значения вектора Х вероятность Р(Х) превращается в условную вероятность, записанную в обычной для теории вероятностей форме.

Определение 12. Форма ФАЛ, допускающая переход от СФФВ путем замены части логических переменных соответствующими вероятностями и логических операций арифметическими и перевода незамещенных логических переменных в показатели степени вероятностей, называется формой перехода к частичному замещению (ФПЧЗ).

ФПЧЗ является частным случаем ФПЗ наряду с формой перехода к полному замещению (ФППЗ), в котором производится замещение одновременно всех логических переменных.

Определение 13. Равнозначность, или эквивалентность, высказываний А и В обозначается символом “~”. Значение истинности эквивалентных высказываний А и В определяется в зависимости от значений истинности исходных высказываний по следующим соотношениям:

0~0=1; 0~1=0; 1~0=0; 1~1=1. (2.23)

Определение 14. Разноименность, или отрицание равнозначности (чаще эту операцию называют логическим сложением по модулю 2), высказываний А и В обозначается символом “ ” или “Å ”.

Значение истинности разноименных высказываний А и В определяется в зависимости от значений истинности исходных высказываний по следующим соотношениям:

0Å 0=0; 0Å 1=1; 1Å 0=1; 1Å 1=0. (2.24)

Иногда эту операцию называют еще строгой дизъюнкцией и обозначают “Ú Ú ” (или ). Связка, соединяющая высказывания А и В, в этом случае понимается не в смысле “или”, а в смысле “либо-либо”. Из соотношений (2.23) видно, что строго разделительное суждение А В истинно лишь тогда, когда А ложно, В истинно и когда А истинно, В ложно.

Для логической операции сложения по модулю 2 имеют место переместительный и сочетательный законы, а также распределительный закон относительно операции конъюнкции:

29. АÅ В = ВÅ А; (2.25)

30. АÅ (ВÅ С) = (АÅ В)Å С; (2.26)

31. АÙ (ВÅ С) = (АÙ В)Å (АÙ С). (2.27)

Имеют место также очевидные соотношения

(2.28)

Перечисленные логические операции связаны с операцией сложения по модулю 2 следующими формулами:

(2.29)

 

Определение 15. Булевой разностью (или логической разностью) функции f(x₁,..., x_n) по аргументу x_i называется результат логического сложения по модулю 2 исходной функции и функции, полученной из исходной путем замены аргумента x_i на его отрицание

(2.30)

Определение 16. Функцию

(2.31)

будем называть симметричной функцией по х_i по отношению к исходной

Определение 17. Функции, полученные заменой в исходной ФАЛ аргумента х_i на 1 и 0, будем называть единичной и нулевой функцией по аргументу х_i и обозначать соответственно:

(2.32)

(2.33)

Определение 18. Функция называется монотонной, если для любых наборов и , таких что , имеет место соотношение:

. (2.34)

Определение 19. Функцию, записанную в виде матрицы, в которой конъюнкции обозначаются расположением логических символов в строке, а дизъюнкцию – их расположением в столбце, будем называть логической матрицей.

К логическим матрицам применимы все известные преобразования алгебры логики. Так, переместительный закон конъюнкции допускает перестановку символов в строке, а переместительный закон дизъюнкции – перестановку строк логической матрицы.

Пусть ФАЛ имеет вид

(2.35)

В матричной форме уравнение (2.35) можно представить в виде:

(2.36)

Вторая матрица уравнения (2.36) записана в ДНФ.

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

Применяя закон инверсий к логической матрице (2.36), получим:

(2.37)

 

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

Поделиться: