 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Определение (формулы над W)
|
|
1. Базис индукции. Любое выражение f(x1,x2,..,xn-1,xn),обозначающее функцию из W, называется формулой над W.
2. Общий шаг индукции. Если f(x1,x2,..,xn-1,xn) –формула над W, а A1,A2,..,An-1,An -формулы над W или обозначения переменных, то выражение f(A1,A2,..,An-1,An) называется формулой над W.
Пример1. Пусть W={ (x1&x2),(x1Úx2), 
}. Тогда (x1Ú(x2& 
)) -формула над W, так как - формула над W (получено из выражения подстановкой вместо x обозначения переменной x3), (x2 & ) - также формула над W (получено из выражения (x1&x2) подстановкой вместо x1 обозначения переменной x2, а вместо x2 – формулы, полученной раннее), а значит, и (x1Ú(x2 & )) – формула над W (получено из выражения (x1Úx2) подстановкой вместо переменной x2 – формулы).
Выражение (x1Ú 
)& - не является формулой над W(оно не может быть получено согласно данному выше определению).
Для упрощения записи функции договариваются опускать внешние скобки и некоторые внутренние, используя приоритет булевых операций. Считают, что самой сильной булевой операцией является отрицание (если нет скобок, она выполняется первой), затем конъюнкция. Остальные операции не различаются, порядок их выполнения определяется скобками. Кроме этого, в формулах символ & часто заменяют на символ ×, а символ × часто опускают.
С учетом указанных соглашений, формулу из рассмотренного выше примера можно записать как x1Úx2& 
.
Если при построении формулы U используются функции f1,…,fs, то этот факт обозначается следующим образом: U=U [ f1,…,fs ]. Если в формуле U переменными являются x1,x2,..,xn, то это обозначается: U(x1, x2,..,xn).
Так как тождественная функция f(x)=x принадлежит P2, то любая суперпозиция булевых функций может быть представлена в виде f0(f1,…,fn). Если вместо некоторых переменных нет подстановки функций, то можно условно считать, что подставляется тождественная функция.
Из определения формулы и определения суперпозиции функций следует, что любая формула является выражением результата суперпозиции функций, значит любой формуле U(x1,x2,..,xn) соответствует некоторая функция из P2. Эту функцию обозначают fU. Она определяется согласно следующей индуктивной процедуре:
1. Базис индукции. Пусть U(x1,x2,..,xn)=f(x1,x2,..,xn), где fÎ W, тогда формуле U(x1,x2,..,xn) сопоставляется функция f(x1,x2,..,xn).
2. Общий шаг индукции. Если U(x1,x2,..,xn)= f0(A1,A2,..,An-1,An), где А1,A2,..,An-1,An -формулы над W, которым на предыдущем шаге сопоставлены функции f1,…,fnÎP2, то формуле U сопоставляется функция f0(f1,…,fn).
Пример2. Пусть U(x1,x2,x3)= x1Ú(x2 & 
). Этапы построения функции, соответствующей заданной формуле, представлены в табл.2.6.
| Табл.2.6 | |||||
| x1 | x2 | x3 |
| x2 &
| x1Ú(x2 & )
|
Логической степенью переменной х называется выражение
Другими словами, логическая степень – выражение, которое обозначает переменную или ее отрицание.
| Табл.2.11 | ||
| x | s | x s |
Из определения логической степени следует, что 
. Данное утверждение можно пояснить табл.2.11.
На основании этого можно определить следующее общее свойство логической степени: xs= 1 тогда и только тогда, когда x=s (соответственно xs= 0Û x≠s).
Рассмотрим набор переменных {x1,..,xn}.
Конъюнкцией (дизъюнкцией) над множеством переменных {x1,..,xn} называетсялюбое выражение вида 
, в котором 
Î{x1,..,xn}, j= 
.
Рангом конъюнкции (дизъюнкции) над множеством переменных {x1,..,xn} называетсяколичество попарно различных переменных в конъюнкции (дизъюнкции).
Пример. Рассмотрим набор переменных {x1,x2,x3,x4}.
Тогда 
(
) – конъюнкция (дизъюнкция) ранга 3.
Конъюнкция (дизъюнкция) над множеством переменных {x1,..,xn} называется элементарной, если все переменные в ней попарно различны.
Элементарную конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xn}, называют совершенной, если она имеет ранг n.
Иными словами, совершенная конъюнкция (дизъюнкция) – это такая, в которой присутствуют все переменные из рассматриваемой совокупности, причем по 1 разу.
Пример.
– элементарная конъюнкция над множеством переменных {x1,x2,x3,x4}, но не совершенная; 
– совершенная конъюнкция над множеством переменных {x1,x2,x3,x4}.
Конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xm} можно обозначать K(D) или Ki(Di).
Дизъюнктивной (конъюнктивной) нормальной формой называется формула вида K1 Ú K2 Ú … Ú Kl или 
(D1 &D 2 & … &D l или 
).
Пример.
–дизъюнктивная нормальная форма. 
– конъюнктивная нормальная форма.
Дизъюнктивная (конъюнктивная) нормальная форма называется совершенной дизъюнктивной(конъюнктивной) нормальной формой или СДНФ(СКНФ),если каждая конъюнкция (дизъюнкция) в ней является совершенной.
Пример. Для набора переменных {x1,x2,x3} 
– совершенная дизъюнктивная нормальная форма, 
– совершенная конъюнктивная нормальная форма.
Теорема (о разложении функции алгебры логики по m переменным).
Каждую функцию алгебры логики f(x1,..,xn) для любого m ≤ n следующее можно представить в следующей форме:
| (2.1) |
Это представление называется разложением функции по m переменным x1,..,xn.
Доказательство. Подставим вместо переменных x1,..,xn любые конкретные значения a1,..,an ÎE2. Тогда в левой части равенства (2.1) получим f(a1,..,an), в правой 
. Выражение 
равно нулю, если существует i (1 ≤ i ≤ m), при котором ai≠si (по свойству логической степени и свойству конъюнкции x 
0=0).
Тогда рассматриваемое выражение можно преобразовать к виду
, так как
,а по свойству дизъюнкции 
. Мы видим,таким образом, что левая и правая части выражения (2.1) совпадают при подстановке вместо переменных любых значений.
Тем самым равенство доказано.
Следствие (разложение функции алгебры логики по всем переменным).
Для любой функции алгебры логики, не тождественно равной 0, справедливо разложение:
 .
| (2.2) |
Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1,..,xn).
Доказательство. В равенстве (2.1) положим m=n, получим:
.
Теорема позволяет функции с большим числом переменных выразить с помощью формул над функциями с меньшим числом переменных.
| Табл.2.12 | ||
| x | y | f(x1,x2) |
Пример.
Рассмотрим функцию эквиваленцию (табл.2.12). Найдем ее разложение по переменной x1 и по всем переменным.
Согласно (2.1), получим
– разложение по переменной x1.
По табл.2.12 функции f(x1,x2) определяем, что f принимает значение 1 на двух наборах (s1,s2) значений переменных – на наборах (0,0) и (1,1). Отсюда, согласно (2.2),
– СДНФ для 
.
Дата публикования: 2014-12-10; Прочитано: 264 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
