1.4. Еквивалентност на формулите. Тавтологии. Законите на логиката. Двойственост
За всекиnброят наn-локалните взаимно различни булеви функции е ограничен. В същото време може да се покаже, че броят на възможните формули, съставени отnпроменливи, е изброим. От това следва, че функциите могат да бъдат представени чрез формули по неуникален начин.
Дефиниция.ФормулитеF1иF2са еквивалентни, ако функциите, които изпълняват, са еднакви, т.е. имат еднакви стойности на истината за едни и същи набори от променливи. Трансформацията на формулатаF1се наричаеквивалентна, ако новополучената формулаF2е еквивалентна на нея.
1. ФормулитеF1=xyиF2=xyне са еквивалентни, тъй като има набори от променливи стойности (напримерx=0,y=0),, където съответните функции приемат различни стойности .
2. ФормулитеF1=xyиF3=(xy) са еквивалентни, тъй като функциите, които изпълняват, са еднакви.
Най-лесният начин да проверите еквивалентността е да използвате таблици на истината. По-долу са таблици на истинност за функции, които изпълняват формулиF1,F2 иF3. Векторите на истината наF1 иF3 съвпадат, докато тези наF1 иF2 не съвпадат.
Дефиниция.Една формула се наричаидентично вярна(false), ако функцията, която изпълнява, е константа 1 (0).Идентично верните формули се наричат същотавтологии, идентично неверните функциипротиворечия.
Тавтологиите са теореми от алгебрата на логиката. Те задават правилните разсъждения, верни за всякакви стойности на твърденията, включени в тях.
Пример 2.Определете дали формулите са тавтологии:
Решение. От следнитеот таблици на истинност за функции, които изпълняват формулиF1,F2 иF3, следва, че формулитеF1,F2 са тавтологии (техните вектори на истинност се състоят само от единици),F3 не е тавтология, тъй като съответният вектор на истинност има нули.
Забележка. В процеса на установяване дали дадена формулаFе тавтология или противоречие всъщност се проверява нейната еквивалентност на константите 1 и 0.
Може да се покаже, че броят на всички възможни тавтологии е изброим за произволен бройnпроменливи, използвани в тях.
Дефиниция.Основните, най-често използвани тавтологии, които дефинират еквивалентни трансформации на формули, се наричат закони на алгебрата на логиката.
1. Комутативни закони за събиране и умножение:
2. Асоциативни закони за събиране и умножение:
3. Закони за разпределение:
4. Правилата на Де Морган за премахване на отрицание:
6. Правила за поглъщане:
7. Закон на противоречието:
8. Законът за изключването на третото:
9 Операции с константи:
Валидността на тези закони може да бъде проверена, както и обичайната еквивалентност на формулите.
Пример 3.Докажете първото правило на де Морган.
Решение. Нека конструираме вектори на стойности на истинност на функции за формули (xy) иxy. Както се вижда от таблиците по-долу, те напълно съвпадат (колони 4 и 7).
От това следва, че тази формула е валидна за всякакви стойности на включените в нея променливи и е тавтология.
Законите на логиката могат да се използват за аналитично опростяване на формули. Можете също да използвате принципа на дуалността, за да трансформирате формули.
Определение.Обратно(обърнат) са стойноститеnиnn-локален булев векторxn, в който всички компоненти се различават: i=iза всички 1 in. Нека ги обозначим катоn=n*.
По време на табличната задача противоположните множестваŠnиnса разположени на еднакви разстояния от началото и края на таблицата, тъй като съответните двоични числа ern и са свързани чрез съотношението pin + =2n-1.
Дефиниция.Симетричниса онезиn-локални булеви функцииf(xn), които приемат еднакви истинностни стойности на всички обратни множества, т.е.f(n) =f(n*) за всичкиnBn.
Истинният вектор на такива функции е симетричен по отношение на средата. Константите 0,1, сума по модул 2, еквивалентност и т.н. са симетрични. Всички прагови функции не са симетрични.
Определение.Двойствениса такиваn-арни функцииfиg, за които върху всички множества nВnравенствотоf(n)=g(n*), т.е. при обратни множестваfиgприемат различни истинностни стойности. Двойствеността се обозначава катоf =g*.
Решение. От отношенията
следва, че функциите са двойствени,f1 =f*2 .
Понятието за дуалност е симетрично, така чеf=g*винаги предполага:g=f *.
Функциятаfв това, което следва, ще се наричавъншни,функцииf1 ,.. ., fk―вътрешни.
Принципът на дуалносттае следната връзка:
Неговата валидност следва пряко от дефиницията на дуалността:
Прилагането на принципа на дуалността опростява много трансформации на формули. По-специално, той позволява аналитично доказване на някои закони на логиката въз основа на други. Тук се използва следното очевидно свойство на формулите: акоA=B, тогаваA*=B*.Например, първото правило на де Морган може да бъде представено катоA=B, къдетоA= (xy),B=xу.Преминавайки къмА*= (хy),В*=ху, получаваме втория закон.
1. Проверете еквивалентността на следните двойки формули:
2. Докажете справедливост:
а) асоциативният закон за събиране,
б) първият разпределителен закон,
в) първото правило за абсорбция.
3. Проверете дали ще има двойни функции:
4. Използвайки принципа на дуалността, намерете функции, двойствени на: а)xyуz; б)xy (хz)y; в)xy .
5. Докажете, че функцията, двойна на праговата функция, също ще бъде прагова.
6. Докажете, че за обобщените функции е вярно:
7. Използвайки принципа на дуалността, за да докажете справедливостта:
а) асоциативният закон за умножение, основан на асоциативния закон за събиране,
б) второто правило за абсорбция, базирано на първото.
8. Докажете еквивалентността на формулите:
9. Проверете дали следните формули са тавтологии:
10. Докажете, че:
11.A,B,C,D―са някои твърдения. Намерете истинността на съставните твърдения: