Исчисление высказываний

style="border-left:none;border-top:none;border-right:solid windowtext .75pt;border-bottom:solid windowtext .75pt;">T T

Нетрудно видеть, что число строк в таблице истиности растет как степень 2 от числа переменных в выражении. Один из способов сокращать число строк - опускать те состояния, которые не влияют на результат. Например, в выражении pÚq , если p=T, то не важно какое значение у q, - значение всего выражения будет T. В таблице 5.5. показано применение этого приема.

Таблица 5.5.

Вычисление значения выражения (pÙq) Þ(rÚ(pÞS)),

не используя незначащие состояния.

p q r s (pÙq) Þ (rÚ (pÞs))
F - - - F T - -
- F - - F T - -
T T T - T T T -
T T F T T T T T
T T F F T F F F

Нетрудно видеть, вычисление “в лоб” таблицы истиности для этого выражения потребовало бы таблицы из 24=16 строк. Используя прием незначащих состояний, удается сократить число рассматриваемых состояний до 5.

Тавтология.

Высказывания, которые истинны при любом состоянии своих переменных, играют особую роль и называются общезначимыми или тавтологиями.

Определение 5.2. Тавтология - высказывание, значение которого - Т на любом состоянии переменных этого выражения. Противоречие - высказывание, значение которого - F, на любом состоянии переменных этого выражения.

Для доказательства утверждения, что некоторое выражение - тавтология, у нас пока есть только таблицы истиности. Докажем, что pÚØp - тавтология. Ниже показана таблица истиности для pÚØp (Таблица 5.6.)

Таблица 5.6.

Таблица истиности для pÚØp

p Øp pÚØp
T F T
F T T

Эта таблица подтверждает наше интуитивное представление о том, что утверждение и его отрицание не могут быть истинны одновременно. Эта тавтология в исчислении высказываний называется законом исключения третьего.

Рассуждения с помощью исчисления высказываний.

Прежде всего, надо обеспечить способ сравнения двух высказываний на эквивалентность, для того, чтобы, при необходимости, заменять одно другим. Так же, нам потребуется техника для обнаружения тавтологий, более мощная, чем таблица истиности. И, наконец, мы рассмотрим методы рассуждений, которые могут быть полезны для разрешения логических проблем, сформулированных на естественном языке. Все это нам потребуется для анализа различных свойств как алгоритмов, так и программ на языке программирования Pascal.

Эквивалентность.

   Рассмотрим высказывание

(pÚq)Ù(pÚØq).

Его таблица истиности представлена в таблице 5.7.

Таблица 5.7.

Таблица истиности для (pÚq)Ù(pÚØq)

p q (pÚq)Ù(pÚØq)
T T T
T F T
F T F
F F F

нетрудно заметить, что последний столбец в этой таблице совпадает со столбцом для p. Поэтому, можно сказать, что с этой точки зрения выражение (pÚq)Ù(pÚØq) эквивалентно p, и везде, где мы встретим это выражение, мы можем его заменить на p.

Как мы уже отмечали, одной из наших забот является упрощение сложных высказываний. Поэтому, для упрощения выражений, мы определим, что означает для двух выражений быть эквивалентными и заменим более сложное на менее сложное.

Определение 5.3. Два высказывания называются эквивалентными, если они на одних и тех же состояниях своих переменных принимают одни и те же значения.

Другими словами, если эти высказывания имеют одинаковые таблицы истиности, то они эквивалентны. Таким образом, один способ установить эквивалентность двух высказываний - вычислить их таблицы истиности и сравнить. Мы, однако, воспользуемся другим способом.

Теорема 5.1. Два высказывания p и q - эквивалентны (обозначается pºq) тогда и только тогда, когда pÛq  - общезначимо.

Доказательство:

Пусть pºq.  Значит таблицы истиности для p и q совпадают. Следовательно, на тех состояниях, где  p=Т,  q=Т  также, а где p=F, то и q=F. Отсюда следует, что pÛq всегда Т (поскольку мы имеем либо ТÛТ, либо FÛF), т.е. pÛq   -  общезначимо или тавтология.

Пусть pÛq   -общезначимо. Тогда если p=Т, то q должно быть Т, а если p=F, то и q должно быть F.

Таким образом, на одних и тех же состояниях эти выражения принимают одинаковые значения. Следовательно, таблицы истиности для p и q совпадают. Последнее означает по определению , что pºq.

(Доказательство закончено.)

Эта теорема показывает, что установить эквивалентность можно, доказав общезначимость специального высказывания.

Свойства эквивалентности.

Основные, часто используемые свойства эквивалентности приведены в таблице 5.8.

Таблица 5.8.

Свойства эквивалентности

I. Коммутативность II. Ассоциативность
1. pÙq º qÙp 1. pÙ(qÙr) º (pÙq)Ùr
2. pÚq º qÚp 2. pÚ(qÚr) º (pÚq)Úr
III. Дистрибутивность IV. Закон Де Моргана
1. pÙ(qÚr) º (pÙq)Ú(pÙr) 1. Ø(pÚq) º ØpÙØq
2. pÚ(qÙr) º (pÚq)Ù(pÚr) 2. Ø(pÙq) º ØpÚØq
V. Закон импликации VI. Закон прямого и обратного условий
1. pÞq º ØpÚq 1. pÛq º (pÞq)Ù(qÞp)
VII. Cвойство отрицания VIII. Закон идентичности
1. Ø(Øp) º p 1. p º p
IX. Закон исключения третьего X. Закон противоречия
1. pÚØp º Т 1. pÙØp º F
XI. Свойства дизъюнкции XII. Коньюнкция
1. pÚp º p 1. pÙp º p
2. pÚÒ º Т 2. pÙÒ º p
3. pÚF º p 3. pÙF º F
4. pÚ(pÙq) º p 4. pÙ(pÚq) º p

Нетрудно углядеть сходство многих свойств эквивалентности в исчислении высказываний с аналогичными свойствами операций в арифметике. Например, законы ассоциативности, дистрибутивности и коммутативности, позволяющие упрощать арифметические операции и аналогичные законы из таблицы 5.8., позволяющие упрощать высказывания.

Мы будем использовать эти свойства в разных целях. Коммутативность, например, позволяет нам менять местами элементы высказывания , в целях его упрощения. Ассоциативность позволяет снимать скобки. Например, т.к. pÙ(qÙr) º (pÙq)Ùr , то мы можем просто писать pÙqÙr. Дистрибутивность позволяет собирать подобные члены, подобно тому как мы это делаем в арифметическом выражении. Закон импликации позволяет уходить от операции Þ , используя только операции Ø, Ú, Ù. Для того, чтобы убедиться в правильности этих свойств, достаточно построить их таблицы истиности. Например, в таблице 5.9. показана корректность закона импликации. Остальные свойства читателю предлагается доказать в качестве упражнения.

Таблица 5.9.

Доказательство корректности закона импликации

p q pÞq ØpÚ q
T T T T
T F F F
F T T T
F T T T

Теперь сосредоточимся на упрощении выскзываний, используя свойства эквивалентности. Под упрощением мы будем понимать такое преобразование высказывания, которое принимает форму, удобную для нас в каком-то смысле. Например, содержит меньше переменных, операций Ú или Ù.

Рассмотрим несколько примеров.

(pÚØq)ÙrÙ(ØpÚq)

(pÚØq)Ù(ØpÚq)Ùr                    I.1

(ØqÚp)Ù(ØpÚq)Ùr                    I.2

(qÞp)Ù(pÞq)Ùr                                   V.1

(pÛq)Ùr                                                VI.1

Таким образом

(pÚØq)ÙrÙ(ØpÚq) º (pÛq)Ùr

Другой пример, упростить

pÚ(ØqÞp)ÚØq

pÚ(Ø(ØqÚp)ÚØq                                  V.1

pÚ(qÚp)ÚØq                             VII.1

pÚ(qÚp)ÚØq                             I.2

(pÚp)Ú(qÚØq)                           II.2

pÚ(qÚØq)                                              XI.1

pÚT                                            IX.1

T                                                            XI.2

Тем самым, мы доказали, что

pÚ(ØqÞp)ÚØq º Т  -  тавтология.

Упростить

((pÞq)Þp)Þp

(Ø(pÞq)Úp)Þp                                    V.1

(Ø(ØpÚq)Úp)Þp                                   V.1

((Ø(Øp)ÙØq)Úp)Þp                 IV.1

((pÙØq)Úp)Þp                         VII.1

(pÚ(pÙØq))Þp                         I.2

pÞp                                           XI.4

ØpÚp                                         V.1

pÚØp                                         I.2

T                                                            IX.1

Таким образом

((pÞq)Þp)Þp  -  тавтология.

5.2.3. Доказательство:  правила вывода.

Основной целью всякого рассуждения является установление истины в форме некоторого общезначимого утверждения, т.е. тавтологии. Для простых случаев, у нас есть метод таблиц истиности. Однако, он становится громоздким при числе переменных больше четырех.

Есть другой метод, называемый доказательством, который представляет собой последовательность логических выводов, правильность каждого из которых строго логически обоснован. Таким образом, рассуждение в этом методе принимает форму последовательности логических выводов.

Процесс доказательства, по существу, является развитием метода, который мы использовали для упрощения высказываний. Однако, доказательство включает важный дополнительный компонент: вывод из предположения. Вывод в доказательстве основан на небольшом числе правил вывода, корректность которых вне сомнений. Эти правила устанавливают, что одни высказывания могут следовать из других, истиность которых либо уже была установлена, либо считаются таковыми по предположению. Эти правила приведены в таблице 5.10.

Таблица 5.10.

Правила вывода

I. Введение Þ II. Введение Û
[p] pÞq
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: