1.2. Законы эквивалентности
Законы эквивалентности позволяют заменить в высказывании любую его компоненту на логически эквивалентное ей высказывание. Полученное в результате такой замены высказывание будет логически эквивалентно исходному, поскольку истинностное значение высказывания зависит исключительно от истинностных значений составляющих его компонент (но не от их формы или сложности).
Теорема 1.1. Некоторые законы логической эквивалентности
а) Законы идемпотентности
A˄A = A,
A˅A = A
б) Закон двойного отрицания
˥(˥A) = A
в) Законы де Моргана
˥ (A˅B) = ˥ A ˄ ˥B;
˥(A˄B) = ˥A ˅ ˥B
г) Свойства коммутативности
A ˅ B = B ˅ A
A ˄ B = B ˄ A
д) Свойства ассоциативности
A ˅ (B ˅C) = (A ˅B)˅ C;
A ˄ (B ˄ C) = (A ˄ B) ˄ C.
е) Свойства дистрибутивности
A ˄(B ˅C) = (A ˄B) ˅(A ˄C)
A ˅(B˄ C) = (A ˅B) ˄(A ˅C)
ж) Закон контрапозиции
A
B
= ˥B
˥A
з)
A B = ˥A ˅ B
и)
A B = (A B) ˅ (B A)
Докажем правомерность знака равенства между правыми и левыми частями с помощью таблиц истинности. Рассмотрим первый из законов де Моргана, остальные останутся в качестве упражнений
˥ (A˅B) = ˥ A ˄ ˥B;
A |
B |
A˅B |
˥ (A˅B) |
˥ A |
˥B |
˥ A ˄ ˥B |
И |
И |
И |
Л |
Л |
Л |
Л |
И |
Л |
И |
Л |
Л |
И |
Л |
Л |
И |
И |
Л |
И |
Л |
Л |
Л |
Л |
Л |
И |
И |
И |
И |
Как мы видим, правая и левая части утверждения ложны и истинны одновременно, стало быть, утверждение о равенстве верно.
Определения 1.2.
Высказывание, истинное во всех случаях, называется логически истинным, или тавтологией. Теоремы в математике являются примерами тавтологий.
Высказывание «Вася сдаст экзамен по математике или Вася не сдаст экзамен по математике» является примером тавтологии, хотя и не очень информативным
Высказывание, построенное так, что оно ложно в каждом случае, называется логически ложным, или противоречием. «Вася сдаст экзамен по математике и Вася не сдаст экзамен по математике» является примером такого утверждения.
Покажите с помощью логических таблиц, что высказывание (A˄(A B)) B является тавтологией, а высказывание ˥((A˄(A B)) B), соответственно, противоречием.
1.3. Понятие умозаключения. Правильные умозаключения
Математики в большинстве своем имеют дело с теоремами и их доказательствами. Теоремы представляют собой "истинные" утверждения относительно рассматриваемых математических систем. Например, утверждение о том, что гипотенуза прямоугольного треугольника длиннее любого из катетов — это известная из геометрии теорема Евклида. Это утверждение считается истинным, поскольку оно "выводимо" из ранее принятых или выведенных истин геометрии Евклида.
Математическая система начинается с неопределяемых понятий и утверждений, точно описывающих фундаментальные характеристики или истинные утверждения относительно этих понятий, которые математики используют для образования системы. Эти фундаментальные характеристики называются аксиомами или постулатами. Утверждения, выведенные (доказанные) только на основе этих фундаментальных свойств (аксиом и постулатов) и ранее доказанных утверждений с помощью логических правил, называются теоремами.
Таким образом, в математических системах вся информация, необходимая для доказательства теоремы, должна содержаться в аксиомах и ранее доказанных теоремах. Развивая конкретный раздел математики, можно не включать в него все аксиомы и доказанные теоремы. Вместо этого можно принять доказанные теоремы в качестве аксиом. Например, аксиомы для целых чисел и аксиомы Пеано для положительных целых чисел неявным образом предполагают выполнение аксиом теории множеств, но, поскольку в теории чисел акцент делается на свойствах целых чисел, было бы излишним стремиться в ней одновременно к полному развитию теории множеств.
Важно, что логические правила, которые используются для вывода новых теорем из аксиом, постулатов и ранее доказанных в данной системе теорем, не порождают в качестве "теорем" ложные высказывания. Эти логические правила называются правилами вывода. Умозаключение состоит из совокупности утверждений, называемых гипотезами, или посылками, и утверждения, называемого заключением. Правильным умозаключением называется такое умозаключение, заключение которого истинно всякий раз, когда истинны его гипотезы. Правила вывода выбираются так, чтобы они были правильными умозаключениями. Умозаключения часто представляют в виде
H1
H2
…
Hn
_________
Следовательно, С
H1, ,H2 ,… - гипотезы (от “hypothesis” – гипотеза), посылки
C – заключение (“conclusion” – заключение)
Определение 1.3. (2)
Умозаключение правильно, если всякий раз, когда H1, ,H2 ,… Hn
истинны, то истинно и С или, что равносильно, всякий раз, когда H1, ˄H2 ˄… ˄Hn истинно, истинно и С.