Еквивалентността на формулите - studopediya
Различни формули могат да бъдат едно и също истина масата. Така възниква понятието еквивалентност формули.
Две формули на алгебрата F1 и F2 се наричат отчети, еквивалентен на (еквивалент), ако те са една и съща истина масата. Еквивалентността на формули е обозначен с F1 ≡F2. Необходимо е да се прави разлика между символи и ↔ ≡. ↔ символ е символ на официален език, който е конструиран с помощта на формулата; ≡ символ замества думата "еквивалентно". Имайте предвид, че съотношението на равностойност е връзка равностойност. Освен това, следните твърдения:
1. Ако двамата са равностойни PF и един от тях включва променливи, които не са в другата, ПФ от тези променливи не зависи от (такива променливи се наричат фиктивни).
2. Ако двамата са равностойни PF, тяхното отричане е еквивалент.
3. Ако двете еквивалентни PF всички случаи на променлива се заменя с всяка формула, полученият нов PF ще бъде еквивалентен.
За всяка от формули X, Y, Z имаме следните еквивалентността (законите на Пропозиционални алгебра):
6. (Акт двойно отрицателен);
7 .. (закони Де Морган);
8 .. , , , , (Закони, регулиращи действия с константи);
9 .. (С изключение на отражение и равностойност);
10. (изключение дизюнкция);
11. (изключение връзка).
Всеки равностойност може лесно да се докаже, или чрез използване на истината маси или еквивалентни преобразувания. Нека докажем, например, един от законите на Де Морган.
За да направите това, изготвят таблица истината за ПФ, стои на лявата и дясната страна на изразите и да ги сравните.
Познаване на законите на Пропозиционални алгебра позволява размер да конвертирате всякакви логически формули, като запазва своите стойности за всеки набор от Пропозиционални променливи. Следващите примери се считат за равносилни да конвертирате основни логически операции.
операция Т.е. равностойност винаги е възможно да се замени дейността на отражение и връзка и дизюнкция и отрицание.
Пример. X «Y º Ù ÚX ÙY º.
Реализирани примери показват, че всяко булева го формула могат да бъдат заменени от еквивалентни формула съдържащ вместо еквивалентност или косвено само две логически операции: дизюнкция и отрицание или връзка и отрицание. Този факт показва, че множество логически connectives дизюнкция и отрицание, връзка и отрицание форма функционално пълна алгебрични системи. Те са достатъчни, за да изразят всяка логическа функция
Ако формулата F съдържа обща формула Fi. заместване във формула обща формула Fi F на еквивалент на S-ING формула Fj не се променя стойността на формула F с всеки набор от Пропозиционални променливи. Ако имате нужда от смяна във формулата F вместо формула Fi новата формула Fj. необходимостта от извършване на тази операция в цялата Fi символ.
Условия за заместване и заместване Empower еквивалентни-валентните сложни трансформации формули отчети.
Конвертиране да опрости алгебрични изрази.
1) Ясно навсякъде логически съединителната ®:
2) Това е отрицание на закона на де Морган:
3) превръщане на разпределителни практика: F = (X1 Ú ) Ù ÚX2 Ù Ú X3;
4) Премахване на елемент (X1 Ú ) Както (X1 Ú ) = 1:
5) реализация на разпределителния закона: F = Ú(X2 ÚX3) Ù ( Ú X3);
7) Нанесете асоциативен закон: F = ( ÚX2)ÚX3;
8) се равнява на "истинска" стойност на формула X. Т. К. ( ÚX2) = 1: F = 1ÚХ3 = 1.
Пример. Като се има предвид аргумента ", или вярно, че Петър заминава за университета (A), нито е вярно, че Петър не е пристигнал, и не е въведен Андрю, или Петър влезе и Симон се присъедини (C), или дори Питър направил, и Саймън отиде, и Андрю направи (В) ".
Формула сложни отчети е както следва:
1) трансформиране на формулата, като се използва закона на де Морган, ние се получи Ù(А ÚВ)ÚА ÙC ÚА ÙНай- ÙС;
2) приложимото право idempotency на:
3) Нанесете разпределителни закона на променлива A:
4) разпределителни законът е приложим за променлива C:
5) въвеждане на постоянен 1:
6) Нанесете разпределителни закона за обща формула (А ÚБ), получаваме:
7) изтриване (1ÚC), получаваме:
8) прилага правото на усвояване, получаваме: А.
Ето защо, в това твърдение, потвърждава само, че Петър отиде в университета, и за Андрей и Симон няма информация.
Пример. Шест деца в училищна възраст - Андрей, Борис, Григорий Дмитрий, Eugene, Симон - участвали в конкурса. Две от тях са решени всички проблеми. На въпрос, който решава всички проблеми на отговор: 1) Андрю и Дмитрий; 2) и Eugene Boris; 3) Eugene и Andrew; 4) Boris и Gregory; 5) Симона и Андрея. В четири от тези отговори една част е лъжа, а другият е вярно. В едно - и двете страни не са прави. Кой решава всички проблеми?
А = «той реши всички проблеми";
B = "Борис реши всички проблеми";
T = "Грегъри реши всички проблеми";
D = "Дмитрий реши всички проблеми";
E = "Юджийн реши всички проблеми";
C = "Саймън реши всички проблеми."
Тъй като една от възможностите за двете страни не са прави, а останалите - по един, то е необходимо да се създадат пет формули, които да отразяват пет различни твърдения:
Ù Ù ( ÙE ÚB Ù ) Ù ( ÙА ÚE Ù ) Ù ( ÙD ÚB Ù ) Ù
Ù ( ÙА ÚC Ù );
Ù Ù ( ÙD ÚА Ù ) Ù ( ÙА ÚE Ù ) Ù ( ÙD ÚB Ù ) Ù
Ù ( ÙА ÚC Ù );
Ù Ù ( ÙD ÚА Ù ) Ù ( ÙE ÚB Ù ) Ù ( ÙD ÚB Ù ) Ù
Ù ( ÙА ÚC Ù );
Ù Ù ( ÙD ÚА Ù ) Ù ( ÙE ÚB Ù ) Ù ( ÙА ÚE Ù ) Ù
Ù ( ÙА ÚC Ù );
Ù Ù ( ÙD ÚА Ù ) Ù ( ÙE ÚB Ù ) Ù ( ÙА ÚE Ù ) Ù
Ù ( ÙD ÚB Ù ).
Ако приемем, че º1 и º1, първата формула може да се запише като:
Ù Ù ( ÙE ÚB Ù ) ÙE Ù Ù ( ÙD ÚB Ù ) ÙC Ù ,
т. За. Членът ÙА º0.
Ако приемем, че º1 и º1 втората формула може да се запише като:
Ù Ù ( ÙD ÚА Ù ) Ù ÙА Ù ÙD Ù ( ÙА ÚC Ù )
т. За. Членовете на E Ù º0 и B Ù º0.
Ако приемем, че º1 и º1, третата формула може да се запише като:
Ù Ù ÙDÙBÙ Ù ( ÙDÚBÙ )ÙCÙ ,
т. За. Всеки член Ù º0, ÙЕ = 0, и ÙА º0.
Ако приемем, че º1 и º1, четвъртата формула може да се запише като:
Ù Ù( ÙD ÚА Ù )Ù ÙE Ù( ÙА ÚE Ù )Ù( ÙА ÚC Ù ), Т. За. В член B Ù º0.
Ако приемем, че º1 и º1, пети формула може да се запише като:
Ù Ù ÙD Ù ( ÙE ÚB Ù ) Ù E Ù Ù ( ÙD ÚB Ù )
т. За. Всеки член Ù º0.
Прилагането на разпределителни право, idempotency и придобивания, тези формули могат да бъдат опростени, както следва:
Ù Ù ÙE ÙD ÙС;
Ù Ù Ù ÙА ÙТ;
Ù Ù ÙD ÙC ÙБ;
Ù Ù ÙD ÙE ÙС;
Ù Ù ÙD ÙE ÙР.
Според условията на проблема само двама участници решават всички проблеми. Ето защо, формули, съдържащи три Пропозиционални променливи без отрицание, не отговарят на определени условия, както и един съдържащ само две променливи без отрицание, отговаря на условията на този проблем. това Ù Ù Ù ÙА ÙG. Следователно, всички цели за Олимпиадата решиха Андрей (A) и Грегъри (D).