metod_15.03.04_atppp_moas_2016 (1016590), страница 2
Текст из файла (страница 2)
При этом под знаком отрицания находятся те итолько те переменные, которые в первом члене конъюнкции имеют значение0.Ясно, что формула (1) полностью определяет функцию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений переменных xi. Например, если x1 принимает значение 0, а остальныепеременные принимают значение 1, то функция F принимает значение F(0,1, 1, …, 1). При этом логическое слагаемое F(0, 1, …, 1) x1 x2 … xn =F(0, 1, …, 1) 0 1 … 1, входящее в формулу (1), принимает такжезначение F(0, l,..., l), а все остальные логические слагаемые формулы (1)имеют значение 0.
Действительно, в них знаки отрицания перед переменными распределяются иначе, чем в рассмотренном слагаемом. Таким образом, приподстановке вместо переменных тех же значений в конъюнкцию войдет символ 0без знака отрицания, а символ 1 под знаком отрицания. В таком случае один изчленов конъюнкции будет иметь значение 0, и поэтому вся конъюнкция также будет иметь значение 0. В связи с этим на основании закона x 0 = x значениемформулы (1) является F(0, l,..., l).Ясно, что вид формулы (1) может быть значительно упрощен, если в нейотбросить те логические слагаемые, в которых первый член конъюнкции имеетзначение 0 (и, следовательно, вся конъюнкция имеет значение 0).
Если же в логическом слагаемом первый член конъюнкции (то есть определенное значениефункции F) имеет значение 1, то, пользуясь законом 1 х = x, этот член конъюнкции можно не выписывать.Таким образом, в результате получается формула (1), которая содержиттолько элементарные переменные высказывания и обладает следующими свойствами:каждое логическое слагаемое формулы содержит все переменные,входящие в функцию F(x1, x2, …, xn),все логические слагаемые формулы различны,ни одно логическое слагаемое формулы не содержит одновременнопеременную и ее отрицание,ни одно логическое слагаемое формулы не содержит одну и ту же пе-ременную дважды,Перечисленные свойства будем называть свойствами совершенства или,коротко, свойствами. Из приведенных рассуждений видно, что каждой не тождественно ложной функции соответствует единственная формула указанного вида.Если функция F(x1, x2, …, xn) задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто.
Действительно,для каждого набора значений переменных, на котором функция F(x1, x2, …, xn)принимает значение 1, записывается конъюнкция элементарных переменных высказываний, взяв за член конъюнкции хk, если значение xk на указанном наборезначений переменных функции F есть 1 и х, если значение xk есть 0. Дизъюнкция всех записанных конъюнкций и будет искомой формулой.Пусть, например, функция F(x1, x2, x3) имеет следующую таблицу истинности:x1X2x3F(x1,x2 , x3 )00010010010101101000101111011110Для наборов значений переменных (1, 1, 0), (1,0,1), (0,1,0), (0, 0, 0), на которых функция принимает значение 1, запишем конъюнкции x1 x2 x3, x1 x2 x3, x1 x2 x3, x1 x2 x3.
а искомая формула, обладающаясвойствами совершенства, будет иметь вид:x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3.Дизъюнктивная нормальная форма и совершенная дизъюнктивнаянормальная формаЭлементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарныхконъюнкций.Для любой формулы алгебры логики путем равносильных преобразований можно получить ее ДНФ, причем не единственную.Например, для формулы А = х (х y) имеем:А = х ( х y) = (х х) (х y) = х y, то естьДНФ А = (х х) (х y) иДНФ А = х y.Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства.
ТакаяДНФ А называется совершенной дизъюнктивной нормальной формой формулы А(СДНФ А).Как уже указывалось, СДНФ А может быть получена с помощью таблицыистинности.Другой способ получения СДНФ формулы А основан на равносильныхпреобразованиях формулы и состоит в следующем:1.путем равносильных преобразований формулы А получают одну изДНФ А.2.если в полученной ДНФ А входящая в нее элементарная конъюнк-ция В не содержит переменную xi, то, используя закон B (xi xi) = B, элементарную конъюнкцию B заменяют на две элементарных конъюнкции (B xi) и (B xi), каждая из которых содержит переменную xi.3.если в ДНФ А входят две одинаковых элементарных конъюнкции В,то лишнюю можно отбросить, пользуясь равносильностью В В = В.4.если некоторая элементарная конъюнкция В, входящая в ДНФ А,содержит переменную xi и ее отрицание xi, то, на основании закона xi xi= 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой члендизъюнкции.5.если некоторая элементарная конъюнкция, входящая в ДНФ А, со-держит переменную xi дважды, то одну переменную можно отбросить, пользуясь законом xi xi = xi.Ясно, что после выполнения описанной процедуры будет полученаСДНФ А.
Например, для формулы А = x y (x y) ДНФ А = x (x y) (y y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x y) и (x y), В результате получим ДНФ А = x y x y x y y y.Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x y, то отбросим лишнюю. В результате получим ДНФ A = x y x y y y.Так как элементарная конъюнкция y y содержит переменную у и ееотрицание, то y y = 0, и ее можно отбросить как нулевой член дизъюнкции.Таким образом, получаем СДНФ А = x y x y.Конъюнктивная нормальная форма и совершенная конъюнктивнаянормальная формаЭлементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний.Конъюнктивной нормальной формой (КНФ) формулы А называетсяравносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.Для любой формулы алгебры логики путем равносильных преобразований можно получить ее КНФ, причем не единственную.Например, для формулы А = (х у) х у имеем:А = ( (х у) х у) (х у (х у)) == (х у х у) ( (х у) (х у)) == (х х у) (х у у) ( х у х) ( х у у) , то естьКНФ А = (х х у) (х у у) ( х у х) ( х у у).Но так как х х = х, у у = у, х х = х, у у = у, тоКНФ A = (х у) (х у) ( х у) ( х у).А так как (х у) (х у) = х у, ( х у) ( х у) = ( х у), тоКНФ A = (х у) ( х у).КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:Все элементарные дизъюнкции, входящие в КНФ А , раз-личны.Все элементарные дизъюнкции, входящие в КНФ А, содержатвсе переменные.Каждая элементарная дизъюнкция, входящая в КНФ А, не со-держит двух одинаковых переменных.Каждая элементарная дизъюнкция, входящая в КНФ А, не со-держит переменную и ее отрицание.Можно доказать, что каждая не тождественно истинная формула имеетединственную СКНФ.Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы А.
Действительно, получив с помощью таблицы истинности СДНФ А, мы получим СКНФ А, взяв отрицание (СДНФ А), тоесть СКНФ А = (СДНФ А).Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:1.Путем равносильных преобразований формулы А получают одну изКНФ А.2.Если в полученной КНФ А входящая в нее элементарная дизъюнк-ция В не содержит переменную хi, то, используя закон В (xi xi) = В, элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В xiи В xi, каждая из которых содержит переменную xi.3.Если в КНФ А входят две одинаковых элементарных дизъюнкцииВ, то лишнюю можно отбросить, пользуясь законом В В = В.4.Если некоторая элементарная дизъюнкция, входящая в КНФ А, со-держит переменную xi дважды, то лишнюю можно отбросить, пользуясь законом xi xi = xi.5.Если некоторая элементарная дизъюнкция, входящая в КНФ А, со-держит переменную xi, и ее отрицание, то xi xi = 1 и, следовательно, всяэлементарная дизъюнкция имеет значение 1, а поэтому ее можно отбросить,как истинный член конъюнкции.Ясно, что после описанной процедуры будет получена СКНФ А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
