Теоремы для двух и трех переменных
7. Коммутативные (переместительные) законы: а Ù b = b Ù а а Ú b = b Ú а От перемены мест слагаемых сумма не меняется.
8. Ассоциативные (сочетательные) законы: а Ù (b Ù c) = (a Ù b) Ù c ассоциативность конъюнкции. а Ú (b Ú c) = (а Ú b) Ú c ассоциативность дизъюнкции. Для записи умножения или сложения скобки можно опустить. 9. Дистрибутивные (распределительные) законы: а) умножение относительно сложения а Ù (b Ú c) = а Ù b Ú а Ú c а (b + с) = аb + ас (в обычной алгебре) б) сложение относительно умножения a Ú b Ù c = (a Ú b) Ù (a Ú c) a+bc ¹ (a+b) (a+c) (в обычной алгебре) 10. Законы инверсии (правило де Моргана) 11. Обобщение законов де Моргана, предложенное Шенноном: т.е. инверсия дизъюнкции и конъюнкции получается заменой каждой переменной ее инверсией и одновременно взаимной заменой символов суммы и произведения. 12. Законы поглощения 13. Закон контрапозиции 14. Закон транзитивности импликации (закон силлогизма). (а Þ b) Ù (b Þ с) Þ(а Þ с) 15. Закон транзитивности эквиваленции. (а Û b) Ù (b Û с) Þ(а Û с) 16. Закон противоположности. (а Û b)Û (Øа ÛØb) 17. Законы склеивания (распространения). Тавтологии. Равносильные формулы
ПФ, значения которых для любого набора переменных есть 1 (соответственно 0) будем называть тождественно истинными формулами, или тавтологиями (тождественно-ложными ПФ или противоречием).
Тавтологии играют в логике особо важную роль как формулы, отражающие логическую структуру предложений, истинных в силу одной только этой структуры. Для доказательства того, что ПФ является тавтологией достаточно построить таблицу истинности для этой ПФ. Перечислим некоторые основные тавтологии или законы логики. Обозначим | = А, что А тавтология. Справедливость | = и º вытекает из определений: 1. | = х º х - закон тождества 2. | = 3. | = 4. | = 5. | = 6. 7. | = 8. | = 9. | = 10.| = Законы 1-3 выражают законы формальной логики, выведенные Аристотелем. Закон тождества требует, чтобы мысль, заключенная в высказывании не изменялась в течении всего рассуждения. Закон противоречия говорит, что одна и та же мысль не может быть одновременно и истинной и ложной. В силу законов идемпотентности в алгебре логики нет показателей степени и коэффициентов (idem - "то же", potentia - сила). Смысл законов де Моргана можно выразить так: отрицание дизъюнкции равно конъюнкции отрицаний и vice versa. Согласно закону контрапозиции два предложения вида Две ПФ Это обозначается АºВ и читается "А равносильно В" (равносильность рефлексивна, симметрична и транзитивна). Теорема 1. А º В тогда и только тогда, когда | = А Û В. Убедимся, что теорема верна, если докажем необходимость: если АºВ, то | = А Û В; достаточность: если | = А Û В, то А º В. Справедливость этих утверждений вытекает непосредственно из определений.
Принцип двойственности: Если две формулы, (не содержащие знаков Þ, и Û) равносильны, то двойственные ил формулы равносильны. Две формулы называются двойственными, если каждую из них можно получить из другой заменой Ù, Ú, 1, 0 соответственно на Ú, Ù, 0 и 1 (X Ú 0 = Х Ù 1). Обратные и противоположные теоремы. Для каждого предложения, формализованного импликацией А Þ В, можно составить три таких предложения В Þ А, Для всякой теоремы А Þ В, можно составить противоположное предложение Согласно закону контрапозиции два предложения вида
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|