Закон тождества ᅣP®P
Закон исключенного третьего ᅣPÚùP
3.Закон противоречия ᅣù(P&ùP)
Закон двойного отрицания ᅣùùP«P
5.Закон добавления антецедента (в популярной литературе: истина из чего угодно) ᅣP®(Q®P)
6.Из ложного что угодно ᅣ ùP®(P ®Q )
7. Закон отделения ᅣ (P®Q)&P®Q
(Если из некоторого P следует Q, и существует P, то существует Q)
Закон от противного ᅣ (P ®Q ) &ùQ®ùP
9.Закон силлогизма ᅣ (P ®Q ) &(Q®R) ®(P®R)
10.Закон контрпозиции ᅣ (P ®Q ) ®(ùQ®ùP)
Каждый из законов логики высказываний отображает в символической форме некоторую схему доказательства. Например:
1) В соответствии с законом отделения: если истинно, что из некоторого высказывания P следует высказывание Q, и, кроме того, P является истиной, то истиной будет и Q.
2) В соответствии с законом от противного. Закон от противного применяется при доказательстве от противного, а именно, желая доказать утверждение P, мы предполагаем, что P - ложно и доказываем (выводим, что из P следует некоторое высказывание Q, о котором известно, что оно ложно (значит, ùQ -истина)). Отсюда заключаем, что P должно быть истиной.
Утверждение, связывающее равносильность с эквиваленцией.
(ᅣА«В) «(А eq В)
Тавтологии можно получать из равносильной замены «eq» на ««» и наоборот.
1.6. Проблема разрешимости
Как было сказано ранее, каждую формулу можно отнести к одному из классу: или тождественно истинные, или тождественно ложные, или выполнимые. В связи с этим возникает вопрос, каким образом определить, к какому классу относится формула, не составляя таблиц истинности. Ведь практическое использование таблиц истинности для формул с большим количеством переменных весьма трудоемкий процесс.
Эта задача и носит название проблемы разрешимости. Возможно преобразовать формулу к некоторому стандартному виду, обеспечивающему простоту и эффективность проверки при определенности истинных значений всех входящих в формулу переменных.
Существует ряд методов решения сформулированной проблемы. Рассмотрим метод приведения к нормальным формам.
Нормальные формы.
Назовем элементарной конъюнкцией такую конъюнкцию, которая содержит только переменные и их отрицания.
Например, формула(X&ùY&P&ùX) является элементарной конъюнкцией.
Назовем элементарной дизъюнкцией такую дизъюнкцию, которая содержит только переменные и их отрицания.
Например, формула(XÚùYÚPÚùZ) является элементарной дизъюнкцией.
Формула, равносильная некоторой формуле Á и представляющая собой дизъюнкцию элементарных конъюнкций, называется дизъюнктивной нормальной форма (ДНФ) формулы Á.
Например, формула (X&ùY&Z)Ú(X&ùZ&P)Ú(ùY&Z&ùP) является дизъюнктивной нормальной формой.
Формула, равносильная некоторой формуле Á и представляющая собой конъюнкцию элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) формулы Á.
Например, формула (XÚùYÚZ)&(PÚùQÚùZÚY)&(XÚùPÚQ) является конъюнктивной нормальной формой.
Утверждения:
8 Для того чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы она содержала хотя бы одну пару - переменную и ее отрицание.
8 Для того чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы она содержала хотя бы одну пару переменной и ее отрицания
8 Любая формула исчисления высказываний имеет равносильную дизъюнктивную и конъюнктивную нормальные формы.
8 Для того чтобы ДНФ была тождественно ложной, необходимо, чтобы все входящие в нее элементарные конъюнкции были тождественно ложными. То есть каждая элементарная конъюнкция, входящая в ДНФ должна содержать хотя бы одну пару- переменную и ее отрицание.
8 Для того чтобы КНФ была тождественно истинной, необходимо чтобы все, входящие в нее элементарные дизъюнкции были тождественно истинными. То есть, каждая элементарная дизъюнкция, образующая КНФ должна содержать хотя бы одну пару- переменную и ее отрицание.
Если в каждом члене нормальной формы представлены все переменные прямо или с отрицанием, то она называется совершенной нормальной формой (СДНФ, СКНФ).
Утверждение: Для любой формулы существует одна и только одна СДНФ и одна СКНФ.
Существуют доказательства как выше приведенных утверждений, так и далее сформулированных утверждений, которые не будут приведены, так как основной задачей курса является использование аппарата формальной логики.
Дата добавления: 2019-10-16; просмотров: 554;