Логика высказываний (стр. 3 из 3)
Например, чтобы привести формулу (р®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 г.