PhilosophyDay
Современная философия
Равносильность формул исчисления высказываний. конъюнктивная нормальная
формаДругая философия / Логика высказываний / Равносильность формул исчисления высказываний. конъюнктивная нормальная
формаСтраница 1
Формулы φ и ψ называются равносильными, если формула φ ≡ ψ тождественно истина. Например, формула (p Ù`p) Ú q равносильна q, потому что формула (p Ù`p) Ú q ≡ q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю).
Равносильность формул может быть использована для упрощения формул, т.е. для замены какой-то формулы другой формулой, ей равносильной, (эквивалентной), но содержащей либо меньшее число связок, либо меньшее число переменных, либо другие переменные, либо и то, и другое, и третье вместе взятой.
Из определения равносильности формул следует, что тождества (3) - (9) дают нам правила преобразования исходной формулы в новую, ей равносильную к этим правилам добавим и другие правила. Так, любую формулу можно заменить эквивалентной (равносильной) формулой, в которой не содержится знаки «→», «≡» и в которой отрицание опущено лишь на элементарные высказывания. С помощью таблиц истинности можно убедиться в эквивалентности следующих формул:
(р ≡ q) ≡ (р → q) Ù (q→р) (10)
р → q ≡`p Ú q (11)
(р ≡ q) ≡ (`p Ú q) Ù (`qÚр) (12)
(р ≡ q) ≡ (p Ù q) Ú (`рÙ`q) (13)
_
(р → q) ≡ р Ù`q (14)
р Ù1 ≡ р (15)
р Ù0 ≡ 0 (16)
р Ú0 ≡ р (17)
рÚ 1 ≡ 1 (18)
р Ùq ≡`р Ú `q (19)
р Ú q ≡`рÙ`q (20)
Итак, подобно тому, как в алгебре мы имеем возможность преобразовывать, одно выражение в другое, с какой-то точки зрения более простое (скажем, приводить алгебраическое выражение к удобному для логарифмирования виду, заменять таблицу, задающую определитель, числом и т.д.), мы можем преобразовать составные высказывания. Важное значение в алгебре высказываний имеет преобразование любого составного высказывания к конъюнктивной нормальной форме. Эта нормальная форма состоит из конъюнкции дизъюнкций, где каждый дизъюнктивный член является либо элементарным высказыванием, либо его отрицанием.
На основании установленных эквивалентностей вводим следующие правила:
а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) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:
Смотрите также
5.5 Интенционалистские теории языка
(П.Грайс, Дж.Серль)
Интенционализм
— одно из крупных направлений в современной аналитической философии языка.
Основная претензия интенционализма — доказать, что концептуально первичным и
ключевым для философ ...
12.4 Аналитическая философия и
герменевтика (К.-О.Апель)
Один
из наиболее значимых немецких философов ХХ столетия Карл-Отто Апель (р. 1922) в
своем философском становлении претерпел влияние целого ряда течений как
немецкой, так и англо-американ ...
13.4 Физикализм
Материалистическое понимание сознания в
основном представлено тезисом тождество ментального и физического. Это тождество,
в свою очередь, может пониматься или не пониматься редукционистски ...