а) Любое полностью упорядоченное множество, например, множество целых чисел, можно превратить в решётку, определив для любых , что и .
б) Определим на множестве натуральных чисел отношение частичного порядка следующим образом: , если является делителем . Тогда есть наименьшее общее кратное этих чисел, а их наибольший общий делитель.
Решётка, в которой пересечение и объединение существуют для любого подмножества её элементов, называется полной. Конечная решётка всегда полна.
Математическая логика – разновидность формальной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения.
Определение.Высказыванием называется предложение, к которому возможно применить понятия истинно или ложно.
В математической логике не рассматривается сам смысл высказываний, определяется только его истинность или ложность, что принято обозначать соответственно И или Л.
Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.
Таким образом, операции с высказываниями можно описывать с помощью некоторого математического аппарата.
Вводятся следующие логические операции (связки) над высказываниями
1) Отрицание. Отрицанием (логическим “не”) высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.
Обозначается Р или .
Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:
P
Р
И
Л
Л
И
2) Конъюнкция.Конъюнкцией (логическим “и”) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.
Обозначается P&Q или РÙQ.
P
Q
P&Q
И
И
И
И
Л
Л
Л
И
Л
Л
Л
Л
3) Дизъюнкция.Дизъюнкцией (логическим “или”) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.
Обозначается PÚQ.
P
Q
PÚQ
И
И
И
И
Л
И
Л
И
И
Л
Л
Л
4) Импликация.Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.
Обозначается PÉQ (или РÞQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.
P
Q
PÞQ
И
И
И
И
Л
Л
Л
И
И
Л
Л
И
5) Эквиваленция.Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.
Обозначается Р~Q или РÛQ.
P
Q
P~Q
И
И
И
И
Л
Л
Л
И
Л
Л
Л
И
С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.
Замечание. В дальнейшем мы познакомимся с принципиально иной, более широкой трактовкой тех понятий, которые мы определили в данной лекции. Мы будем их рассматривать уже не как операции над высказываниями, но как некоторые функции. Поясним на следующем примере. Запись можно рассматривать как обозначение бинарной операции умножения переменных и , а, с другой стороны, так же обозначается функция двух переменных .
Пример 1. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.
Составим таблицы истинности для каждой формулы:
p
r
(pÙr)
И
И
Л
И
И
И
Л
Л
Л
И
Л
И
И
Л
Л
Л
Л
И
Л
Л
p
r
И
И
Л
Л
Л
И
И
Л
Л
И
И
И
Л
И
И
Л
И
И
Л
Л
И
И
И
И
Данные формулы не являются эквивалентными.
Пример 2. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.
Составим таблицы истинности для заданных формул.
p
q
r
pÛq
(pÛq)Úr
И
И
И
И
И
И
И
Л
И
И
И
Л
И
Л
И
И
Л
Л
Л
Л
Л
И
И
Л
И
Л
И
Л
Л
Л
Л
Л
И
И
И
Л
Л
Л
И
И
p
q
r
pÞq
qÞp
(pÞq)Ú(qÞp)
(pÞq)Ú(qÞp)Úr
И
И
И
И
И
И
И
И
И
Л
И
И
И
И
И
Л
И
Л
И
И
И
И
Л
Л
Л
И
И
И
Л
И
И
И
Л
И
И
Л
И
Л
И
Л
И
И
Л
Л
И
И
И
И
И
Л
Л
Л
И
И
И
И
Из составленных таблиц видно, что данные формулы не равносильны.
Основные равносильности.
Для любых формул А, В и С справедливы следующие равносильности:
A & B º B & A; A & A º A; A & (B & C) º (A & B) & C;
A Ú B º B Ú A; A Ú A º A; A Ú (B Ú C) º (A Ú B) Ú C;
A Ú (B & C) º (A Ú B) & (A Ú C); A & (B Ú C) º (A & B) Ú (A & C);
A & (A Ú B) º A; A Ú (A & B) º A; ØØA º A; Ø(A & B) º ØA Ú ØB;