Закон тождества ᅣ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; просмотров: 40; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2020 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.