Контрольная работа: Логика высказываний
На основании установленных эквивалентностей вводим следующие правила:
а1) Со знаками Ú и Ù можно оперировать как в алгебре, пользуясь ассоциативным, коммутативным и дистрибутивным законами;
а2) `р можно заменить р;
а3) р Ùq можно заменить выражением`р Ú
`q, а р Ú
q - выражением`рÙ`q
;
а4) р → q можно заменить выражением `p Ú q, а р ≡ q – выражением (`p Ú q) Ù(`qÚр).
Например, привести к конъюнктивной нормальной форме формулу:
((р Ú q) Ù`q ) Ú
(rÙq).
Последовательным
применением правила а3) получаем :
((р Ú q) Ù`q ) Ú
(rÙq) ≡((р
Ú q) Ù`q ) Ù (rÙq) ≡((р Ú q) Ú`q ) Ù
(`rÚ`q)
≡
≡ ((`рÙ`q) Ú`q ) Ù (`rÚ`q).
Применяя к последней формуле закон дистрибутивности, получаем формулу:
(`р Ú `q )Ù( qÙ`q) Ù (`rÚ`q).
Наконец, применяя правило а2) получаем конъюнктивную нормальную форму:
(`р Ú q )Ù( qÚ`q) Ù (`rÚ`q).
Очевидно, что эта форма определяется не однозначно. Так, используя то, что qÚ`q ≡ 1 и (15), получаем другую конъюнктивную нормальную форму первоначальной формулы: (`pÚq) Ù (`rÚ`q)
Запишем обобщения законов поглощения (7):
рÙ( р Ú q1 Ú q2 Ú … Ú qп ) ≡ р (21)
рÚ ( р Ù q1Ù q2 Ù… Ù qп ) ≡ р (211)
рÙ( р Ú q1 ) Ù( рÚ q2 ) Ù …Ù (рÚ qп ) ≡ р (22)
рÚ ( р Ù q1 ) Ú (рÙ q2 ) Ú … Ú (р Ù qп ) ≡ р (221)
Из них, а также (9), (3), (15)-(18) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:
рÚ ( qÙ`q) ≡ р (23)
рÙ ( qÚ`q) ≡ р (24)
рÚ ( qÚ`q) ≡ 1 (25)
рÙ ( qÙ`q) ≡ 0 (26)
Используя, справа налево дистрибутивный закон (6), получаем два новых соотношения:
(р Ùq ) Ú (р Ù r) ≡ р Ù (q Ú r) (27)
(р Ú q )Ù (р Ú r) ≡ р Ú (q Ù r) (28)
Например, упростить выражение:
(р Ú q Ú r) Ù (рÚ qÚ`r ).
Применяя (28), учитывая, что rÙ`r ≡ 0 и (17) получаем:
(р Ú q Ú r) Ù (рÚ qÚ`r ) ≡ (р Ú q) Ú (rÙ`r ) ≡ р Ú q.
Иногда оказывается полезным для упрощения формулы повторить в ней какие-то выражения, используя, справа налево законы поглощения (21)-(22).
Например, упростить выражение
(р Ú q )Ù (`рÚ q) Ù (`рÚ`q).
Повторим `рÚ q и, используя (6), (2), (17), (4) получаем:
(р Ú q )Ù (`рÚ q) Ù (`рÚ q) Ù (`рÚ`q) ≡ (qÚ(рÙ`р)) Ù (`рÚ (q Ù`q)) ≡ (qÚ0) Ù (`рÚ 0) ≡ qÚ`р ≡ `рÚ q.
Иногда для каких-то целей необходимо вводить в формулу новые переменные (буквы). Это делается с учетом тождеств (24) и (25) и законов дистрибутивности (6). Так, в выражение р Ú q можно ввести букву r. В самом деле, используя (3), а также (6), получаем:
р Ú q≡(р Ú q) Ú (r Ù`r ) ≡ (р Ú q Ú r) Ù (рÚ qÚ`r )
4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ
Для каждой формулы наряду с конъюнктивной нормальной формой существует дизъюнктивная нормальная форма. Она состоит из дизъюнкции конъюнкций, в которой каждый конъюнктивный член является элементарным высказыванием или его отрицанием.
Преобразование формулы к дизъюнктивной нормальной форме происходит следующим образом: отрицанием первоначальную формулу и приведем ее к конъюнктивной нормальной форме, а затем вновь отрицанием полученное выражение согласно правилу а3).
Например, привести к дизъюнктивной нормальной форме формулу:
р Ù (р®q).
Отрицаем эту формулу и приводим полученное выражение к конъюнктивной нормальной форме:
р Ù (р®q) ≡`рÚ (р ®q) ≡`рÚ (`рÚ q) ≡`рÚ
(`рÙ
`q) ≡(`рÚ`р) Ù(`р Ú`q) ≡
≡(`рÚр) Ù(`р Ú`q)
Отрицаем последнее выражение:
______________ ____ ______ _ _ _
(`рÚр) Ù(`р Ú`q) ≡(`рÚр) Ú (`р Ú`q) ≡ (`р Ù`р) Ú (`р Ù`q) ≡(р Ù`р) Ú (р Ùq)
Приведение формулы к нормальной форме дает иной, чем таблицы истинности метод решения проблемы разрешимости.
Чтобы формула была тождественно истинной необходимо и достаточно, чтобы в ее конъюнктивной нормальной форме каждый конъюнктивный член содержал элементарное высказывание вместе со своим отрицанием.
Доказательство получаем из (25)(91) и (15), а также определения конъюнкции. Так формула (р Ú `рÚ q) Ù( р Ú `qÚ q) тождественно истинна.
Чтобы формула была тождественно ложной необходимо и достаточно, чтобы в ее дизъюнктивной нормальной форме каждый дизъюнктивный член содержал элементарное высказывание вместе со своим отрицанием. Так формула:
(р ÙrÙ`р) Ú ( р Ù r Ù`r ) тождественно ложна.
Доказательство получаем из того, что р Ù`р≡0, (16) и определения дизъюнкции.
Формула будет выполнимой, если в ее дизъюнктивной нормальной форме есть хотя бы один дизъюнктивный член, который не содержит элементарное высказывание вместе со своим отрицанием.
В самом деле, если это условие для какой-то формулы выполнено, то для этого дизъюнктивного члена существует такой набор значения переменных, для которого он равен 1. Тогда согласно (18) для этого набора значений переменных формула принимает значение, равное1.
Например, докажем, что формула р≡ q выполнима. Приводим эту формулу к дизъюнктивной нормальной форме:
(р≡ q ) ≡(р® q) Ù(q ®р) ≡ (`р Ú q) Ù(`q Úр) ≡((`р Ú q) Ù`q) Ú((`р Ú q) Ùр) ≡ ≡ (`р Ù`q) Ú (q Ù`q) Ú (`р Ù р) Ú (q Ùр) ≡ (`р Ù`q) Ú (q Ùр) ≡ (q Ùр) Ú(`р Ù`q).
Каждый дизъюнктивный член не содержит элементарное высказывание вместе со своим отрицанием. А значит формула р≡ q выполнима.
5 СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
Мы знаем, что одна и та же формула может быть представлена различными дизъюнктивными нормальными формами. Среди этих форм имеется совершенная дизъюнктивная нормальная форма, которая удовлетворяет условиям:
a) в ней нет двух одинаковых дизъюнкций;
b) ни одна дизъюнкция не содержит двух одинаковых конъюнкций;
c) ни одна дизъюнкция не содержит переменного высказывания вместе со своим отрицанием;
d) каждая дизъюнкция содержит в качестве дизъюнктивных членов все переменные, входящие в формулы.
Имеется два метода приведения формулы к дизъюнктивной нормальной форме.
Первый состоит в следующем: составляется истинностная таблица формулы и находятся все наборы значений переменных высказываний, при которых формула принимает значение «истина». Затем выписываются конъюнкции элементарных высказываний, отвечающие этим наборам, знаки отрицания расставляются над этими высказываниями, так, чтобы эти конъюнкции были истинными; наконец, конъюнкции соединяются знаком дизъюнкции.
Исходная формула будет равносильна выписанной дизъюнктивной нормальной форме.
В самом деле, при соблюдении требований расстановки знаков отрицания над переменными все выписанные конъюнкции будут истинными, а потому совершенная дизъюнктивная нормальная форма будет иметь тоже истинностное значение, что и исходная формула.
Например, чтобы привести формулу (р®q)Úq®rÚq к дизъюнктивной нормальной форме, составляем таблицу истинности этой формулы. Она имеет вид:
| р | q | r | р®q | (р®q)Úq | rÙ q | (р®q)Úq®rÚq |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
По сформулированному алгоритму получаем:
(р®q)Úq®rÚq º (`рÙ qÙ r) Ú( р Ù`qÙ`r ) Ú ( р Ù`qÙr)Ú ( р ÙqÙr).
Другой метод приведения формулы к совершенной дизъюнктивной нормальной форме заключается в следующем: приводим формулу к дизъюнктивной нормальной форме, а затем приписываем в каждом дизъюнктивном члене недостающие переменные согласно правилу (24).
Так , для формулы (р®q)Úq®rÚq
имеем следующую цепочку преобразований
_____________ _____ ____
(р®q)Úq®rÚq º(`рÚ qÚ q) Ú (rÙ q) º `р Úq Ù r Ù q º (`рÚ q)Ù(`qÚ`r ).
Отрицаем последнее выражение:
______________ _ _ _
(`р Ú q)Ù(`qÙ`r ) º(`рÙ`q) Ú (`qÙ`r ) º( р Ù`q) Ú (qÙr).
Затем, пользуясь (24), имеем:
( ( р Ù`q) Ù (r Ú`r)) Ú (( рÚ` р) Ù( qÙr)) º ( р Ù`q Ù r) Ú ( р Ù`q Ù`r) Ú (`рÙ qÙ r) Ú( рÚ q Úr ) º(`рÙ qÙ r) Ú ( р Ù`qÙ`r) Ú( р Ù`qÙr) Ú ( р ÙqÙr).
Аналогичным образом определяется совершенная конъюнктивная нормальная форма какой-то формулы. Она удовлетворяет условиям:
a) в ней нет двух одинаковых конъюнкций;
b) ни одна конъюнкция не содержит двух одинаковых дизъюнкций;
c) ни одна конъюнкция не содержит переменного высказывания вместе со свои отрицанием;
d) в каждой конъюнкции содержится в качестве дизъюнктивных членов все переменные входящие в формулу.
Правила приведения произвольной формулы к совершенной конъюнктивной нормальной форме аналогичны тем, которые были описаны для нахождения совершенной дизъюнктивной нормальной форме и выражаются в двойственных терминах. Так, для формулы (р®q)Úq®rÙq пользуясь ее таблицей истинности и правилом двойственности сразу можно записать совершенную конъюнктивную нормальную форму. Для этого выписываем дизъюнкции переменных, при которых формула истинна, затем расставляем знаки отрицания, чтобы при этих значениях выписанные дизъюнкции обращались в ложь. И наконец соединяем все дизъюнкции знаком конъюнкции. Для предыдущей формулы получаем:
(р®q)Úq®rÙqº( р Ú `qÚ` r) Ù(` р Úq Ú r ) Ù (`рÚqÚ `r) Ù (`рÙ`qÙ `r)
Чтобы привести формулу к совершенной конъюнктивной нормальной форме по другому методу, надо привести ее к конъюнктивной нормальной форме, а затем восстановить в каждом конъюнктивном члене недостающие переменные, пользуясь правилом (23). Так для формулы (р®q)Úq®rÙq имеем следующую цепочку преобразований:
(р®q)Úq® (rÙq) º( `р Ú qÚ q) Ú (rÙq) º (`рÙ`q) Ú(rÙq) º (рÙ`q) Ú(rÙq).
По закону двойственности имеем:
_
(рÙ`q) Ú(rÙq) º (`рÚ`q) Ù (`r Ú`q) º (`рÚq) Ù (`r Ú`q).
В полученной конъюнктивной нормальной форме восстанавливаем недостающие переменные, пользуясь (23).
(`рÚq) Ù (`r Ú`q) º((` р Úq) Ú (rÙ`r)) Ù (( рÚ` р) Ú (`r Ú`q)) º (`рÚ qÚ r) Ù (` рÚ q Ú `r) Ù( рÚ`qÚ`r ) Ù (`рÙ`q Ù` r ).
Во многих случаях представление формулы в совершенных нормальных формах является способом систематического ее упрощения. Однако этот метод не является наиболее коротким и не приводит к простейшему выражению.
Литература
1. Логическое суждение. Руфулаев О.Н. К. – 2005 г.
2. Логика исскуство мышления. Тимирязев А.К.– К. 2000 г.
3. Философия и жизнь журнал- К. 2004 г.
4. История логики и мышления – Касинов В.И. 1999.
5. Логика и человек М. 2000.
6. Философия жизни. Матюшенко В.М. – Москва – 2003 г.
7. Философия бытия. Марикова А.В. – К. 2000 г.
